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

【摘要】：圖的反饋數(shù)問(wèn)題是在實(shí)際應(yīng)用中提出來(lái)的。計(jì)算機(jī)操作系統(tǒng)中解決“死鎖”問(wèn)題、網(wǎng)絡(luò)攻擊中最小攻擊點(diǎn)集問(wèn)題等都可以轉(zhuǎn)化為在圖中求一個(gè)最小反饋點(diǎn)集的問(wèn)題。求圖的反饋數(shù)問(wèn)題已被證明是NP困難問(wèn)題,其每一個(gè)進(jìn)展都十分艱辛。到目前為止,只有少數(shù)的圖類得到了其反饋數(shù),已經(jīng)得到反饋數(shù)界的圖類也不多。本文對(duì)與互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)方法(笛卡兒乘積方法、線圖方法、Cayley方法)密切相關(guān)的幾個(gè)重要的圖類的反饋數(shù)進(jìn)行了研究,分別給出了Flower Snark相關(guān)圖Jn、Knodel圖W△,n。和循環(huán)圖Gn(1,k)的反饋數(shù)、增廣立方體AQn反饋數(shù)的上下界、局部扭立方體LTQn反饋數(shù)的上界以及Kautz有向圖K(d,n)反饋數(shù)的上界。(1)對(duì)Flower Snark相關(guān)圖Jn、Knodel圖W3,n和W4,n、循環(huán)圖Cn(1,K)的反饋數(shù)進(jìn)行了研究。利用Jn、W3,n、W4,n和Gn(1,k)的循環(huán)結(jié)構(gòu),分別找到了相應(yīng)的帶循環(huán)節(jié)的無(wú)圈子圖頂點(diǎn)集的構(gòu)造方法,基于這些頂點(diǎn)集分別得到了如下結(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時(shí)的Cn(1,k)反饋數(shù)：f(Cn(1,k))=(?)(2) 對(duì)增廣立方體AQn、局部扭立方體LTQn兩種變型超立方體網(wǎng)絡(luò)的反饋數(shù)進(jìn)行了研究。利用AQn和LTQn頂點(diǎn)遞推結(jié)構(gòu)和邊集性質(zhì),分別構(gòu)造出了相應(yīng)的可遞推的無(wú)圈子圖頂點(diǎn)集函數(shù),基于這些函數(shù),分別給出如下結(jié)論。①給出了AQn反饋數(shù)緊的上下界為：2n-3×2n-3≤f(AQ)≤2n-(2n-2+2(?))；②給出了LTQn反饋數(shù)的上界為：f(LTQn)≤2n-1。(3)對(duì)有向Kautz圖K(d,n)的反饋數(shù)進(jìn)行了研究。給出了Kautz有向圖K(d,n)的一種新的反饋點(diǎn)集頂點(diǎn)短表達(dá)式模式,基于該模式得到了更小的反饋點(diǎn)集,給出K(d,n)漸進(jìn)估計(jì)從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 鈮，

本文編號(hào)：1917591