本文選題：廣義de　切入點：Bruijin有向圖　出處：《上海大學(xué)》2016年博士論文

【摘要】：在過去的半個世紀,隨著計算機科學(xué)和網(wǎng)絡(luò)通訊技術(shù)的飛速發(fā)展,圖論的研究也呈現(xiàn)出了異�；钴S的趨勢,特別是控制數(shù)理論研究.控制數(shù)理論作為圖論的一個重要研究方向,在計算機科學(xué),組合優(yōu)化,通信網(wǎng)絡(luò),編碼理論以及監(jiān)視系統(tǒng)等領(lǐng)域具有廣泛的應(yīng)用.本文著重研究了兩類重要的網(wǎng)絡(luò)拓撲圖-廣義de Bruijn和Kautz有向圖以及超圖上的控制集問題.廣義de Bruijn有向圖GB(n,d)和廣義Kautz有向圖GK(n,d)是由deBruijn有向圖和Kautz有向圖推廣而來的,它們作為新一代互聯(lián)網(wǎng)的重要拓撲圖,具有良好的結(jié)構(gòu)和性能.因此對其各類網(wǎng)絡(luò)參數(shù)的研究受到極大關(guān)注.首先,研究了廣義de Bruijn有向圖的最小控制集問題.圖G的最小控制集所含頂點的數(shù)目定義為圖的控制數(shù),記作r(G).2003年,日本學(xué)者Kikuchi和Shibata給出了廣義de Bruijn有向圖的控制數(shù)的上、下界,他們證明了同時他們提出一個猜想：任何廣義de Bruijn有向圖均存在一個連貫的最小控制集.我們通過直接構(gòu)造連貫的最小控制集,證明了廣義de Bruijn有向圖的控制數(shù)只可能有兩個值：[n/d+1]或者[n/d+1]+1.這意味著完全證明了Kikuchi和Shibata提出的猜想.同時,我們利用數(shù)論的經(jīng)典結(jié)果,給出了GB(n,d)的或者[n/d+1]+1的完全刻畫.這樣使得廣義de Bruijn有向圖的最小控制集問題被完全確定.其次,我們討論了GB(n,d)和GB(n,d)的距離l-控制數(shù).G的距離l-控制數(shù)是指它的最小距離l-控制集所含的頂點數(shù),記為rl(G).通過直接構(gòu)造距離l-控制集的方法證明了或者GK(n,d)的上界為[n/((dl-1+dl)].同時,給出取得等式的一些充分條件.本文也討論了GB(n,d)和GK(n,d)的雙向控制數(shù).有向圖G的雙向控制數(shù)r*(G)是G的最小雙向控制集所含點的數(shù)目.本文改進了GB(n,d)和GK(n,d)的雙向控制數(shù)的已有上界.最后,討論了超圖上的控制集問題.超圖是普通圖的一類推廣,超圖的控制集問題是最近幾年剛提出來并進行研究的.我們將一般圖控制集問題推廣到超圖來討論,這里主要考慮超圖的控制數(shù).超圖的控制數(shù)r(H),匹配數(shù)v(H)和橫貫數(shù)Υ(H)是超圖的幾個重要參數(shù).Ryser猜想：對每個r-部超圖,有τ(H)≤(r-1)ν(H),這個猜想已被公認是極其困難的,對r≥4至今沒有任何進展.本文討論了類-Ryser關(guān)系,我們證明了秩為r的超圖的控制數(shù)和匹配數(shù)之間的關(guān)系：γ(日)≤(γ-1)ν(H).一般情況下,滿足γ(H)=(γ-1)ν(H)的超圖的刻畫是非常困難的.我們給出了秩為3時極值超圖的完全刻畫.此外,我們也給出了秩為4,控制數(shù)為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