广义de Bruijn有向图和超图的控制集问题

发布时间：2018-04-02 18:57

  本文选题：广义de　切入点：Bruijin有向图　出处：《上海大学》2016年博士论文

【摘要】：在过去的半个世纪,随着计算机科学和网络通讯技术的飞速发展,图论的研究也呈现出了异常活跃的趋势,特别是控制数理论研究.控制数理论作为图论的一个重要研究方向,在计算机科学,组合优化,通信网络,编码理论以及监视系统等领域具有广泛的应用.本文着重研究了两类重要的网络拓扑图-广义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的线性交超图的刻画.
[Abstract]:In the past half century, with the rapid development of computer science and network communication technology, the research of graph theory has shown an extremely active trend, especially the theory of domination number.As an important research direction of graph theory, control number theory has been widely used in computer science, combinatorial optimization, communication network, coding theory and surveillance system.In this paper, we focus on two important classes of network topology graphs-generalized de Bruijn and Kautz digraphs and control set problems on hypergraphs.The generalized de Bruijn digraphs GBK / n ~ d) and the generalized Kautz digraph G ~ (K) are generalized by deBruijn digraphs and Kautz digraphs. As important topology graphs of the new generation of Internet, they have good structure and performance.Therefore, great attention has been paid to the study of various network parameters.Firstly, the minimum control set problem of generalized de Bruijn digraphs is studied.The number of vertices contained in the minimal dominating set of graph G is defined as the domination number of a graph. In 2003, Japanese scholars Kikuchi and Shibata gave the upper and lower bounds of the domination number of generalized de Bruijn digraphs.They proved that at the same time they proposed a conjecture that there exists a coherent minimum control set for any generalized de Bruijn digraph.By directly constructing a coherent minimum control set, we prove that the domination number of generalized de Bruijn digraphs can only have two values: [n / d 1] or [n / d 1] 1.This means that the conjecture put forward by Kikuchi and Shibata is completely proved.At the same time, by using the classical results of the number theory, we give a complete characterization of [n / d _ 1] _ 1, or [n / d _ 1] _ 1.In this way, the minimum dominating set problem of generalized de Bruijn digraphs is completely determined.Secondly, we discuss the distance l- control number. G of the distance l-domination number. The distance l-domination number is the number of vertices contained in its minimum distance l-domination set.It is proved that the upper bound of the distance L- control set is [n/((dl-1 dl].At the same time, some sufficient conditions for obtaining equality are given.In this paper, we also discuss the bi-directional control numbers of GBN (n) and GK (n).The bidirectional domination number of directed graph G is the number of points contained in the minimum bidirectional domination set of G.In this paper, we improve the upper bounds of the bidirectional domination numbers of GBN) and GKN (d).Finally, the control set problem on hypergraph is discussed.Hypergraph is a kind of generalization of ordinary graph. The control set problem of hypergraph has been put forward and studied in recent years.We generalize the problem of general graph control set to hypergraph. Here we mainly consider the domination number of hypergraph.In this paper, we discuss the Ryser like relation. We prove the relation between the domination number and the matching number of the hypergraph with rank r: 纬 (day) 鈮，

本文编号：1701682