学位论文 > 优秀研究生学位论文题录展示

W_（3，n）的支配问题与二部图的弧的公有性研究

作　者: 薛峰
导　师: 杨元生
学　校: 大连理工大学
专　业: 计算机应用技术
关键词: 支配数 Packing数 Kn(o ¨)del图有向二部图公有弧
分类号: O157.5
类　型: 硕士论文
年　份: 2008年
下　载: 11次
引　用: 1次
阅　读: 论文下载

内容摘要

图论是研究由线连接的点集的理论。图论是组合数学的一个重要分支，同时也是离散数学的一个重要组成部分。随着计算机科学与数学的发展，图论已经成为人们研究自然科学以及社会科学的一个重要工具。图的支配问题是近年来图论中一个比较活跃的研究领域。图的支配问题的研究不仅具有很重要的理论意义，在优化理论、通讯网络的设计与分析、社会科学、计算复杂性和算法设计等许多领域也有很重要的应用背景。图的支配数问题在网络设计中有许多应用。比如在一个通讯网络的一些节点上放置发射器，要求每个发射器的节点一定和某个发射器的节点有一个直接的通讯线路。如何选择节点，使得放置的发射器的数目最小，这就是一个支配数问题。计算图的支配数问题属于NP-完全问题，因此至今只有少数图的支配数被找到并证明。本文对Kn（?）del图W_3,n的支配数γ(W_3,n)及其密切相关的Packing数ρ(W_3,n)进行了较深入的研究。证明了：A．Hubenko[On a cyclic connectivity property of directed graphs．Discrete Math．，2008，308：1018-1024]证明了每个圈连通的有向完全二部图有一条公有弧并提出两个问题：（1）假设C是一个圈连通的有向完全二部图G中的一个最大圈，C中所有的弧都是公有弧吗?（2）假设D是一个圈连通的简单有向二部图，D中是否存在一条公有弧?本文对这两个问题进行了研究，证明了：（1）存在圈连通的有向完全二部图，它的最大圈中至少有一条弧不是公有弧。（2）存在圈连通的简单有向二部图，它的最大圈中所有弧都是公有弧。（3）存在圈连通的简单有向二部图，它的最大圈中至少有一条弧不是公有弧。

全文目录

摘要  4-5
Abstract  5-8
1 绪论  8-22
  1.1 前言  8-9
  1.2 图的基本概念  9-14
  1.3 支配问题简介  14-19
    1.3.1 支配问题基本概念  14-16
    1.3.2 支配研究发展过程  16-18
    1.3.3 支配集及Packing集的应用  18
    1.3.4 支配数及Packing数的计算复杂性  18-19
  1.4 Kn(o|¨)del图W_(Δ,n)  19-21
  1.5 本文工作  21-22
2 Kn(o|¨)del图W_(3,n)的支配数  22-27
  2.1 Kn(o|¨)del图W_(3,n)支配数上界  23-24
  2.2 Kn(o|¨)del图W_(3,n)支配数下界  24-27
3 Kn(o|¨)del图W_(3,n)的Packing数  27-45
  3.1 Kn(o|¨)del图W_(3,n) Packing数下界  27-28
  3.2 Kn(o|¨)del图W_(3,n) Packing数上界  28-45
4 圈连通有向二部图中最大圈的弧的公有性  45-52
  4.1 相关术语  45
  4.2 研究背景  45
  4.3 主要结果  45-52
结论  52-54
参考文献  54-58
攻读硕士学位期间发表学术论文情况  58-59
致谢  59-60

W_（3，n）的支配问题与二部图的弧的公有性研究

内容摘要

全文目录

相似论文