本文選題：反饋數(shù) + Flower�。� 參考：《大連理工大學(xué)》2016年博士論文

【摘要】：圖的反饋數(shù)問題是在實際應(yīng)用中提出來的。計算機操作系統(tǒng)中解決“死鎖”問題、網(wǎng)絡(luò)攻擊中最小攻擊點集問題等都可以轉(zhuǎn)化為在圖中求一個最小反饋點集的問題。求圖的反饋數(shù)問題已被證明是NP困難問題,其每一個進展都十分艱辛。到目前為止,只有少數(shù)的圖類得到了其反饋數(shù),已經(jīng)得到反饋數(shù)界的圖類也不多。本文對與互連網(wǎng)絡(luò)拓撲結(jié)構(gòu)設(shè)計方法(笛卡兒乘積方法、線圖方法、Cayley方法)密切相關(guān)的幾個重要的圖類的反饋數(shù)進行了研究,分別給出了Flower Snark相關(guān)圖Jn、Knodel圖W△,n。和循環(huán)圖Gn(1,k)的反饋數(shù)、增廣立方體AQn反饋數(shù)的上下界、局部扭立方體LTQn反饋數(shù)的上界以及Kautz有向圖K(d,n)反饋數(shù)的上界。(1)對Flower Snark相關(guān)圖Jn、Knodel圖W3,n和W4,n、循環(huán)圖Cn(1,K)的反饋數(shù)進行了研究。利用Jn、W3,n、W4,n和Gn(1,k)的循環(huán)結(jié)構(gòu),分別找到了相應(yīng)的帶循環(huán)節(jié)的無圈子圖頂點集的構(gòu)造方法,基于這些頂點集分別得到了如下結(jié)論。①給出了Flower Snark相關(guān)圖Jn反饋數(shù)為：f(Jn)=n+1；②給出了W3,n反饋數(shù)：f(W3,n)=(?)；③給出了W4,n反饋數(shù)：f(W4,n)=(?)；④ 給出了偶數(shù)n≥5+1+2(?)+mod3)且3≤奇數(shù)kn/2時的Cn(1,k)反饋數(shù)：f(Cn(1,k))=(?)(2) 對增廣立方體AQn、局部扭立方體LTQn兩種變型超立方體網(wǎng)絡(luò)的反饋數(shù)進行了研究。利用AQn和LTQn頂點遞推結(jié)構(gòu)和邊集性質(zhì),分別構(gòu)造出了相應(yīng)的可遞推的無圈子圖頂點集函數(shù),基于這些函數(shù),分別給出如下結(jié)論。①給出了AQn反饋數(shù)緊的上下界為：2n-3×2n-3≤f(AQ)≤2n-(2n-2+2(?))；②給出了LTQn反饋數(shù)的上界為：f(LTQn)≤2n-1。(3)對有向Kautz圖K(d,n)的反饋數(shù)進行了研究。給出了Kautz有向圖K(d,n)的一種新的反饋點集頂點短表達式模式,基于該模式得到了更小的反饋點集,給出K(d,n)漸進估計從O(dn-4)下降到O(d2)。
[Abstract]:The problem of feedback number of graphs is put forward in practical application. The problem of "deadlock" in computer operating system and the problem of minimum attack point set in network attack can be transformed into the problem of finding a minimum feedback point set in graph. The problem of finding the feedback number of graphs has been proved to be NP-hard, and every progress is very difficult. Up to now, only a few graph classes have obtained their feedback numbers, and there are few graph classes which have obtained feedback number bounds. In this paper, the feedback numbers of several important graph classes which are closely related to the design method of topological structure of interconnection networks (Cartesian product method, line graph method) are studied. The Flower Snark correlation graph Jnn Knodel graph is given respectively. The feedback number of the AQn feedback number of the augmented cube, the upper bound of the LTQn feedback number of the local twisted cube and the upper bound of the LTQn feedback number of the Kautz directed graph are studied. By using the cyclic structure of JnGW _ 3N _ 4N _ 4N and G _ n ~ (1) k), the corresponding construction method of vertex set of circular graph with cyclic nodes is found respectively. Based on these vertex sets, the following conclusions are obtained respectively .1 the Flower Snark correlation graph J _ n feedback number is given as: F ~ (n) J _ n _ n ~ (1) ~ 2 and W _ 3n feedback number: W _ 3n feedback number F / W _ 4n feedback number F: W _ 4N ~ (1 / n ~ 4) mod3) and 3 鈮，

本文編號：1917591