论文部分内容阅读
在过去的半个世纪,随着计算机科学和网络通讯技术的飞速发展,图论的研究也呈现出了异常活跃的趋势,特别是控制数理论研究.控制数理论作为图论的一个重要研究方向,在计算机科学,组合优化,通信网络,编码理论以及监视系统等领域具有广泛的应用.本文着重研究了两类重要的网络拓扑图-广义de Bruijn和Kautz有向图以及超图上的控制集问题.广义de Bruijn有向图GB(n,d)和广义Kautz有向图GK(n,d)是由deBruijn有向图和Kautz有向图推广而来的,它们作为新一代互联网的重要拓扑图,具有良好的结构和性能.因此对其各类网络参数的研究受到极大关注.首先,研究了广义de Bruijn有向图的最小控制集问题.图G的最小控制集所含顶点的数目定义为图的控制数,记作r(G).2003年,日本学者Kikuchi和Shibata给出了广义de Bruijn有向图的控制数的上、下界,他们证明了同时他们提出一个猜想：任何广义de Bruijn有向图均存在一个连贯的最小控制集.我们通过直接构造连贯的最小控制集,证明了广义de Bruijn有向图的控制数只可能有两个值：[n/d+1]或者[n/d+1]+1.这意味着完全证明了Kikuchi和Shibata提出的猜想.同时,我们利用数论的经典结果,给出了GB(n,d)的或者[n/d+1]+1的完全刻画.这样使得广义de Bruijn有向图的最小控制集问题被完全确定.其次,我们讨论了GB(n,d)和GB(n,d)的距离l-控制数.G的距离l-控制数是指它的最小距离l-控制集所含的顶点数,记为rl(G).通过直接构造距离l-控制集的方法证明了或者GK(n,d)的上界为[n/((dl-1+dl)].同时,给出取得等式的一些充分条件.本文也讨论了GB(n,d)和GK(n,d)的双向控制数.有向图G的双向控制数r*(G)是G的最小双向控制集所含点的数目.本文改进了GB(n,d)和GK(n,d)的双向控制数的已有上界.最后,讨论了超图上的控制集问题.超图是普通图的一类推广,超图的控制集问题是最近几年刚提出来并进行研究的.我们将一般图控制集问题推广到超图来讨论,这里主要考虑超图的控制数.超图的控制数r(H),匹配数v(H)和横贯数Υ(H)是超图的几个重要参数.Ryser猜想：对每个r-部超图,有τ(H)≤(r-1)ν(H),这个猜想已被公认是极其困难的,对r≥4至今没有任何进展.本文讨论了类-Ryser关系,我们证明了秩为r的超图的控制数和匹配数之间的关系：γ(日)≤(γ-1)ν(H).一般情况下,满足γ(H)=(γ-1)ν(H)的超图的刻画是非常困难的.我们给出了秩为3时极值超图的完全刻画.此外,我们也给出了秩为4,控制数为3的线性交超图的刻画.