關(guān)于局部扭立方體的反饋數(shù)

張思佳，徐喜榮＊，劉 聰，曹 楠，楊元生

（1.大連理工大學(xué) 電子信息與電氣工程學(xué)部，遼寧 大連 116024；2.中國(guó)科學(xué)技術(shù)大學(xué) 數(shù)學(xué)系，安徽 合肥 230026）

0 引 言

在組合網(wǎng)絡(luò)理論中，若一個(gè)簡(jiǎn)單圖刪除某些節(jié)點(diǎn)后構(gòu)成的導(dǎo)出子圖不存在回路，則稱(chēng)被刪去的節(jié)點(diǎn)集合為該簡(jiǎn)單圖的反饋點(diǎn)集.階數(shù)最小的反饋點(diǎn)集稱(chēng)為最小反饋點(diǎn)集，最小反饋點(diǎn)集的階數(shù)叫做反饋數(shù).

確定圖的最小反饋點(diǎn)集問(wèn)題，因其在諸多領(lǐng)域內(nèi)的廣泛應(yīng)用而受到重視.例如在互聯(lián)網(wǎng)中，如果網(wǎng)絡(luò)有回路，廣播消息會(huì)一直在網(wǎng)橋環(huán)網(wǎng)中傳遞，形成“廣播風(fēng)暴”，阻塞網(wǎng)絡(luò).解決這個(gè)問(wèn)題的做法就是想辦法盡可能少地關(guān)閉一些網(wǎng)橋，使剩下的網(wǎng)絡(luò)不再有回路［1］.再如：任何一個(gè)具有自動(dòng)化功能的工作單位，都需要不斷地發(fā)出指令，再分析指令執(zhí)行的結(jié)果，然后發(fā)出新的指令，用以調(diào)整或改變工作狀態(tài).持續(xù)不斷的反饋是自動(dòng)化得以實(shí)現(xiàn)的關(guān)鍵.另外，在操作系統(tǒng)和超級(jí)計(jì)算機(jī)的分布式計(jì)算中避免死鎖產(chǎn)生的問(wèn)題，同樣也是確定網(wǎng)絡(luò)反饋點(diǎn)集的問(wèn)題［2］.

因?yàn)榇_定一般網(wǎng)絡(luò)（或圖）的最小反饋點(diǎn)集問(wèn)題屬NP 難問(wèn)題［3］，所以現(xiàn)階段還不能對(duì)這一問(wèn)題給出令人滿意的結(jié)論.盡管在一些文獻(xiàn)中，對(duì)某些特殊拓?fù)浣Y(jié)構(gòu)圖（如mesh網(wǎng)絡(luò)、toroids網(wǎng)絡(luò)、butterflies網(wǎng)絡(luò)、立方連通網(wǎng)絡(luò)、超立方體網(wǎng)絡(luò)和星圖等）的反饋數(shù)的上界和下界都已經(jīng)陸續(xù)得到［4－19］，但即使是得到了具體的圖，要確定其最小反饋集仍不是容易的事.

本文根據(jù)局部扭立方體頂點(diǎn)集合中最后一位字節(jié)不同的特點(diǎn)，將其頂點(diǎn)集合劃分為兩個(gè)不相交的子集，并構(gòu)造極大無(wú)圈子圖得到反饋數(shù)的上界，從而研究局部扭立方體的反饋數(shù)問(wèn)題.

1 定義和引理

n維局部扭立方體（locally twisted cube）簡(jiǎn)稱(chēng)為Qltn（n≥2），由Yang等［14］于2005年提出.Qltn網(wǎng)絡(luò)是超立方體網(wǎng)絡(luò)Qn的變形.與n維超立方體Qn類(lèi)似，Qltn是一個(gè)具有2n個(gè)頂點(diǎn)的n－正則圖，頂點(diǎn)集由n維的｛0，1｝字符串組成.但Qltn相比Qn有許多好的性質(zhì)，例如在維數(shù)相同的情況下，Qltn具有比Qn更小的半徑；Qltn能嵌入所有長(zhǎng)度為l（4≤l≤2n）的圈，圈嵌入能力優(yōu)于Qn.有關(guān)局部扭立方體的其他性質(zhì)，可參閱文獻(xiàn)［3，4，10－13，15 －19］.

定義1Qltn的邊集由這樣的邊組成：對(duì)任意兩個(gè)頂點(diǎn)x＝x1x2…xn和y＝y(tǒng)1y2…yn，它們之間進(jìn)行連邊，當(dāng)且僅當(dāng)它們滿足如下要求之一：

（1）存在一個(gè)整數(shù)k（1≤k≤n－2）滿足yk是xk的補(bǔ)點(diǎn)，xk∈｛0，1｝），yk＋1＝（xk＋1＋xn）mod 2，x和y的其余字節(jié)均相同（x和y僅有連續(xù)兩位字節(jié)不同），此時(shí)（x，y）稱(chēng)為非匹配邊；

（2）存在一個(gè)整數(shù)k∈｛n－1，n｝，x和y僅在第k位不同，其余字節(jié)全相同，則x和y存在連邊，并稱(chēng)（x，y）為匹配邊.

由上述定義不難發(fā)現(xiàn)，Qlt2由標(biāo)記為00、01、10和11的4個(gè)頂點(diǎn)以及4條邊（00，01）、（00，10）、（01，11）、（10，11）組成.

當(dāng)n≥3，Qltn由兩個(gè)不相交的Qltn－1圖添加2n－1條邊組成，其按照如下步驟構(gòu)建：在其中一個(gè)Qltn－1的所有頂點(diǎn)的二進(jìn)制串前面加上一個(gè)前綴0，用0Qltn－1表示；其中的另外一個(gè)Qltn－1的所有頂點(diǎn)的二進(jìn)制串前面加上一個(gè)前綴1，用1Qltn－1表示；用一條邊連接圖形0Qltn－1中的頂點(diǎn)x＝0x2x3…xn和圖形1Qltn－1中的頂點(diǎn)x＝1（x2＋xn）x3…xn，這里“＋”表示模2 加法.通常，記為Qltn＝LR，其中L0Qltn－1，R1Qltn－1.如圖1所示.

定義2 圖G中兩兩互不相鄰的頂點(diǎn)構(gòu)成的集合S稱(chēng)為圖G的獨(dú)立集.

Beineke等［15］證明了一般圖G＝（V，E）的反饋數(shù)的下界為

其中Δ＝Δ（G），為圖G的最大度.由于Qltn是n－正則圖，Qltn的最小度Δ＝n且所以得到如下Qltn的反饋數(shù)的下界.

引理1 令f（n）表示Qltn的反饋數(shù)，則有

2 局部扭立方體的反饋數(shù)的上界

定義3 對(duì)于局部扭立方體Qltn，頂點(diǎn)x＝x1x2…xn∈V（Qltn）.定義：

顯然，AQn是Qltn的所有奇頂點(diǎn)構(gòu)成的集合，BQn是Qltn的所有偶頂點(diǎn)構(gòu)成的集合，且V（Qltn）＝AQn∪BQn，AQn∩BQn＝.

定義4 把頂點(diǎn)集合V（Qltn）與字符串b＝y(tǒng)1y2…yj（yi∈｛0，1｝，1≤i≤j）連接，定義為Qbltn＝｛xb｜x∈V（Qltn）｝，bQltn＝｛bx｜x∈V（Qltn）｝.把二進(jìn)制字符串b和含有二進(jìn)制字符串元素的集合Q連接，定義為Qb＝｛xb｜x∈Q｝，bQ＝｛bx｜x∈Q｝，其中xb代表字符串x與字符串b連接組成的一個(gè)新字符串，bx代表字符串b與字符串x連接組成的一個(gè)新字符串.

通常，由Qltn＝0Qltn－11Qltn－1知，可根據(jù)第一位字節(jié)的不同將Qltn的頂點(diǎn)劃分為兩個(gè)不相交的子集.

本文給出一種新的劃分方法：根據(jù)最后一位字節(jié)的不同將Qltn的頂點(diǎn)劃分為兩個(gè)不相交的子集.

取T0n－1＝｛x＝xn－1xn－2…x10｜x∈V（Qltn）｝，則有

即T0n－1與M1n－1為Qltn的頂點(diǎn)劃分的兩個(gè)不相交的子集.

由Qltn的定義，任意選取x＝xn－1xn－2…x10∈T0n－1，存在唯一一個(gè)點(diǎn)y＝xn－1xn－2…x11 ∈M1n－1，使得x與y之間有邊相連.

首先給出新劃分的兩個(gè)不相交的子集T0n－1與M1n－1的性質(zhì).

引理2 令G0＝G（Tn0－1），G1＝G（Mn1－1），那么G0＝G（Qn0－1）且G1＝G（Qn1－1）.

證 明 顯 然，V（G0）＝Q0n－1＝｛x0｜x∈V（Qn－1）｝，只需證明E（G0）＝E（G（Qn0－1））.

因?yàn)镚0是Qltn中Tn0－1的導(dǎo)出子圖，x，y∈且x和y的最后一位字節(jié)都為0.由Qltn定義知，當(dāng)且僅當(dāng)x和y只有一位字節(jié)不同時(shí)存在連邊，這與Q0n－1的定義等同，因此E（G0）＝E（G（Q0n－1））.

同理，可證G1＝G（Q1n－1）.證畢.

由M1n－1＝｛x＝xn－1xn－2…x11｜x∈V（Qltn）｝，可以得到：

例如：M12＝｛001，011，101，111｝，則有M2＝｛00，01，10，11｝；

M13＝ ｛0001，0011，0101，0111，1001，1011，1101，1111｝，則有M3＝｛000，001，010，011，100，101，110，111｝.

定義5 令R2＝｛00，01｝，S2＝｛10，11｝，定義集合Rn和Sn如下：

按定義5的規(guī)則易得到集合Rn和Sn與Mn之間有如下結(jié)果：

根據(jù)歸納 可 得Rn∪Sn＝0Rn－1∪1Rn－1∪0Sn－1∪1Sn－1＝0Mn－1∪1Mn－1＝Mn.

因?yàn)镸n＝Rn∪Sn，則M1n＝R1n∪S1n.

現(xiàn)在討論R1n與S1n所誘導(dǎo)的子圖之間的關(guān)系.

引理3 令G2＝G（R1n），G3＝G（S1n），則G2和G3分別只含有匹配邊.

證明 采用歸納法證明.由R2＝｛00，01｝，S2＝｛10，11｝，可得

如圖2所示，當(dāng)n＝3時(shí)，G（R13）和G（S13）只含有匹配邊.同理，當(dāng)n＝4時(shí)，G（R14）和G（S14）也只含有匹配邊.

圖2 無(wú)圈子圖G（R13）、G（S13）、G（R14）和G（S14）Fig.2 The acyclic subgraphs G（R13），G（S13），G（R14）and G（S14）

對(duì)n分為奇數(shù)和偶數(shù)兩種情形來(lái)歸納證明.

第1種情形：假設(shè)當(dāng)n為偶數(shù)時(shí)，即當(dāng)n＝2k時(shí)，G（R12k）和G（S12k）含有匹配邊，則證明當(dāng)n＝2k＋1時(shí)，G（R12k＋1）和G（S12k＋1）只含有匹配邊.

因?yàn)镽2k＋1＝0R2k∪1R2k，則R12k＋1＝0R12k∪1R12k.由假設(shè)G（R12k）含匹配邊，則G（0R12k）和G（1R12k）含匹配邊.

為證明G（R12k＋1）含有匹配邊，只需證明0R12k與1R12k之間各點(diǎn)無(wú)連邊.用反證法證明，假設(shè)0R12k與之間有點(diǎn)相連接，即a∈0R12k，b∈1R12k，a與b有連邊，（a，b）∈E（G（R12k＋1））.因?yàn)镽2k＝0R2k－1∪1S2k－1，則0R2k＝00R2k－1∪01S2k－1，1R2k＝10R2k－1∪11S2k－1；R12k＝0R12k－1∪1S12k－1，則0R12k＝00R12k－1∪01S12k－1，1R12k＝10R12k－1∪11S12k－1.因 此a∈00R12k－1或01S12k－1，b∈10R12k－1或11S12k－1.

由Qltn定義，若（a，b）為非匹配邊，則a和b僅有連續(xù)兩位字節(jié)不同，其余全相同.顯然，a和b的第一位字節(jié)不同，若（a，b）為非匹配邊，則第二位字節(jié)必不相同.那么，分兩種情況考慮：

情況1 如果a∈00R12k－1，則b∈11R12k－1.顯然，R12k－1≠S12k－1，則b11S12k－1和b10R12k－1，與假設(shè)矛盾；

情況2 如果a∈01S12k－1，則b∈10S12k－1.顯然，S12k－1≠R12k－1，則b10R12k－1和b11S12k－1，與假設(shè)矛盾.

因此，0R12k與1R12k之 間 各 點(diǎn) 無(wú) 連 邊，即只含有匹配邊.同理，可證G（S12k＋1）只含有匹配邊.

第2種情形：假設(shè)當(dāng)n為奇數(shù)時(shí)，即n＝2k＋1時(shí)，G（R12k＋1）和G（S12k＋1）含有匹配邊，則證明當(dāng)n＝2k＋2時(shí)，G（R12k＋2）和G（S12k＋2）只含有匹配邊.

因?yàn)镽2k＋2＝0R2k＋1∪1S2k＋1，則R12k＋2＝0R12k＋1∪1S12k＋1.由 假 設(shè)G（R12k＋1）含 匹 配 邊，則G（0R12k＋1）和G（1R12k＋1）含匹配邊.

為證明G（R12k＋2）含有匹配邊，只需證明0R12k＋1與之間各點(diǎn)無(wú)連邊.用反證法證明，假設(shè)與1S12k＋1之 間 有 點(diǎn) 相 連 接，即a∈0R12k＋1，b∈1S12k＋1，a與b有連邊，（a，b）∈E（G（R12k＋2））.

因 為R2k＋1＝0R2k∪1R2k，則0R12k＋1＝00R12k∪01R12k；S2k＋1＝0S2k∪1S2k，則1S12k＋1＝10S12k∪11S12k.因此a∈00R12k或01R12k，b∈10S12k或11S12k.

由Qltn定義，若（a，b）為非匹配邊，則a和b僅有連續(xù)兩位字節(jié)不同，其余全相同.顯然，a和b的第一位字節(jié)不同，若（a，b）為非匹配邊，則第二位字節(jié)必不相同.那么，分兩種情況考慮：

情況1 如果a∈00R12k，則b∈11R12k.顯然，≠S12k，則b11S12k和b10S12k，與假設(shè)矛盾；

情況2 如果a∈01R12k，則b∈10R12k.顯然，≠R12k，則b10S12k和b11S12k，與假設(shè)矛盾.

因此，0R12k＋1與1S12k＋1之間各點(diǎn)無(wú)連邊，即只含有匹配邊.同理，可證G（S12k＋2）只含有匹配邊.證畢.

由引理2知，T0n－1＝Q0n－1＝AT0n－1∪BT0n－1，其中AT0n－1為Q0n－1的奇數(shù)點(diǎn)集合，BT0n－1為Q0n－1的偶數(shù)點(diǎn)集合.AT0n－1和BT0n－1分別是Q0n－1的獨(dú)立集.

引理4G（AT0n－1∪R1n－1）是Qltn的無(wú)圈子圖.

證明AT0n－1是Q0n－1的獨(dú)立集，也是Qltn的獨(dú)立集，則G（AT0n－1）是不含圈的.由引理3 得，只含有匹配邊，則是不含圈的.

因?yàn)锳T0n－1T0n－1，R1n－1M1n－1，由Qltn定義知，頂點(diǎn)x∈AT0n－1與頂點(diǎn)y∈R1n－1當(dāng)且僅當(dāng)最后一位字節(jié)不同，其余字節(jié)相同時(shí)兩點(diǎn)之間有連邊.即若x與y相連，則x＝xn－1xn－2…x10∈AT0n－1，至多存在一個(gè)y＝y(tǒng)n－1yn－2…y11∈R1n－1.因此，G（AT0n－1∪R1n－1）的導(dǎo)出子圖是不含圈的.證畢.

由引理4和反饋點(diǎn)集的定義，得下面引理.

引理5V（Qltn）＼（AT0n－1∪R1n－1）是Qltn的反饋點(diǎn)集.

定理1 令f（n）為Qltn的反饋數(shù)，則f（n）≤2n－1.

證明 因?yàn)閯t有即2n－1，所以f（n）≤V（Qltn）＼（AT0n－1∪R1n－1）＝2n－2n－1＝2n－1.證畢.

由定理1和引理1，得下面定理.

定理2 任意正整數(shù)n≥2且c∈（0，1）時(shí)，Qltn的反饋數(shù)為

注：事實(shí)上，可證G（BT0n－1∪S1n－1）是不含圈的，V（Qltn）＼（BT0n－1∪S1n－1）也是Qltn的反饋點(diǎn)集.因?yàn)榭?得f（n） ≤V（Qltn）＼（BT0n－1∪S1n－1）＝2n－2n－1＝2n－1，即結(jié)合引理1也可得到定理2.

3 結(jié) 語(yǔ)

對(duì)一般圖確定最小反饋點(diǎn)集是一個(gè)NP難問(wèn)題，準(zhǔn)確計(jì)算出圖的最小反饋點(diǎn)集是很困難的.至今，人們只對(duì)一些特殊的圖給出了求最小反饋點(diǎn)集的多項(xiàng)式時(shí)間的算法.本文根據(jù)n維局部扭立方體頂點(diǎn)集合中最后一位字節(jié)不同的特點(diǎn)，將其頂點(diǎn)集合劃分為兩個(gè)不相交的子集，構(gòu)造極大無(wú)圈子圖并得到了局部扭立方體網(wǎng)絡(luò)的反饋數(shù)的上界.

［1］ 周書(shū)明.六角形蜂窩網(wǎng)絡(luò)的反饋數(shù)［J］.工程數(shù)學(xué)學(xué)報(bào)，2011，28（2）：260－264.ZHOU Shu－ming.Feedback number of honeycomb networks ［J］.Chinese Journal of Engineering Mathematics，2011，28（2）：260－264.（in Chinese）

［2］ 吳葉舟.線圖的反饋數(shù)［D］.合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2006.WU Ye－zhou.Feedback numbers of line graphs［D］.Hefei：University of Science and Technology of China，2006.（in Chinese）

［3］ Garey M R，Johnson D S.Computers and Intractability［M］.San Francisco：Freeman，1979.

［5］ Bafna V，Berman P，F(xiàn)ujito T.A 2－approximation algorithm for the undirected feedback vertex set problem ［J］.Discrete Mathematics，1999，12（3）：289－297.

［6］ Bau S，Beineke L W，Liu Z，etal.Decycling cubes and grids［J］.Utilitas Mathematica，2001，59：129－137.

［7］ Bar－Yehuda R，Geiger D，Naor J S，etal.Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference ［J］.SIAM Journal on Computing，1998，27（4）：942－959.

［8］ Focardi R，Luccio F L，Peleg D.Feedback vertex set in hypercubes［J］.Information Process Letters，2000，76（1－2）：1－5.

［9］ Liang Y D.On the feedback vertex set problem in permutation graphs ［J］.Information Processing Letters，1994，52（3）：123－129.

［10］ Luccio F L.Almost exact minimum feedback vertex set in meshes and butterflies ［J］.Information Processing Letters，1998，66（2）：59－64.

［11］ Smith G W，Walford R B Jr.The identification of a minimal feedback vertex set of a directed graph［J］.IEEE Transaction on Circuits and Systems，1975，22（1）：9－15.

［12］ Wang C C，Lloyd E L，Soffa M L.Feedback vertex sets and cyclically reducible graphs［J］.Journal of the ACM，1985，32（2）：296－313.

［13］ Wang F H，Hsu C J，Tsai J C.Minimal feedback vertex sets in directed split－stars［J］.Networks，2005，45（4）：218－223.

［14］ YANG Xiao－fan，Evans D J，Megson G.The locally twisted cubes［J］.International Journal of Computer Mathematics，2005，82（4）：401－413.

［15］ Beineke L W，Vandell R C.Decycling graphs［J］.Graph Theory，1997，25（1）：59－77.

［16］ Kralovic R，Ruzicka P.Minimum feedback vertex sets in shuffle－based interconnection networks［J］.Information Processing Letters，2003，86（4）：191－196.

［17］ XU Jun－ming，WU Ye－zhou，HUANG Jia，etal.Feedback numbers of Kautz digraphs［J］.Discrete Mathematics，2007，307（13）：1589－1599.

［18］ XU Jun－ming.Topological Structure and Analysis of Interconnection Networks ［M］.London：Kluwer Academic Publishers，2001.

［19］ Riordan J.Introduction to Combinatorial Analysis［M］.Princeton：Princeton University Press，1978.