關(guān)于折疊超立方體的反饋數(shù)

徐 喜 榮， 曹 楠， 吉 日 木 圖， 董 學(xué) 智， 王 保 才， 王 磊

（1.大連理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，遼寧 大連 116024；2.中國科學(xué)技術(shù)大學(xué) 數(shù)學(xué)系，安徽 合肥 230026；3.內(nèi)蒙古民族大學(xué) 數(shù)學(xué)學(xué)院，內(nèi)蒙古 通遼 028043）

0 引 言

對簡單圖（有向或無向）G＝ （V，E），F(xiàn)是頂點集合V（G）的子集，如果從頂點集合V中刪除子集F后，剩余頂點的導(dǎo)出子圖不含（有向或者無向）圈，則稱F是G的反饋點集.點數(shù)最小的子集F稱為最小反饋點集.

圖的最小反饋點集問題來源于實際問題.例如，在互聯(lián)網(wǎng)中，終端電腦作為節(jié)點，終端之間的連線作為邊，則可以用圖來建立互聯(lián)網(wǎng)的數(shù)學(xué)模型，網(wǎng)絡(luò)中的某些性質(zhì)可以用圖論的參數(shù)來刻畫.如果網(wǎng)絡(luò)中某些節(jié)點發(fā)生故障，則極易使網(wǎng)絡(luò)陷入癱瘓狀態(tài)，為了避免此情況的發(fā)生，網(wǎng)絡(luò)設(shè)計中允許存在一些回路.由于不同的網(wǎng)段之間是以網(wǎng)橋相互連接，廣播消息通過網(wǎng)橋從一個網(wǎng)段傳播到下一個網(wǎng)段.若網(wǎng)絡(luò)中存在回路，則廣播消息會在網(wǎng)橋環(huán)網(wǎng)中一直傳遞下去，形成“廣播風(fēng)暴”.為了避免形成網(wǎng)絡(luò)中的“廣播風(fēng)暴”，則需要盡可能少地關(guān)閉一些網(wǎng)橋，使剩余的網(wǎng)絡(luò)不再含有回路.用圖論術(shù)語來說，就是要確定該網(wǎng)絡(luò)對應(yīng)圖的一個最小反饋點集.

在操作系統(tǒng)和超級計算機的分布式計算中經(jīng)常出現(xiàn)死鎖問題.操作系統(tǒng)中的死鎖可以用狀態(tài)圖來描述.若狀態(tài)圖中包含回路，則系統(tǒng)中的進(jìn)程將出現(xiàn)資源互相等待的狀態(tài)，極易產(chǎn)生死鎖問題.一個著名的解決死鎖問題的方法是在對應(yīng)的狀態(tài)圖中放棄盡可能少的進(jìn)程，等價于在狀態(tài)圖中找到盡可能少的點，去掉這些點后，剩余的狀態(tài)圖中不包含回路，去掉最少的頂點的集合就是狀態(tài)圖的一個最小反饋點集.給定一個光纖網(wǎng)絡(luò)，安裝盡可能少的波長轉(zhuǎn)換器，使得網(wǎng)絡(luò)中的每一條路由所需要的波長數(shù)等于網(wǎng)絡(luò)的擁塞界（用于安裝波長轉(zhuǎn)換器的頂點集合被稱為充分集），擁塞界就是網(wǎng)絡(luò)中經(jīng)過任一條邊的路的最大數(shù)目.此問題也等價于在所對應(yīng)的有向圖中求圖的最小反饋點集問題.

因為確定一般網(wǎng)絡(luò)（或圖）的最小反饋點集問題屬NP問題[1]，所以現(xiàn)階段還不能對這一問題給出令人滿意的結(jié)論.大多數(shù)的工作是在多項式時間內(nèi)解決某些特殊圖的反饋數(shù)問題，以及確定特殊圖的最小反饋數(shù)的上下界.

文獻(xiàn)[2]證明了一般圖G＝（V，E）的反饋數(shù)的下界為

其中Δ＝Δ（G）為圖G的最大度.這個下界給出了一般圖G＝（V，E）的反饋數(shù)與圖的最大度的關(guān)系.

大網(wǎng)絡(luò)的構(gòu)造通常是利用小網(wǎng)絡(luò)的笛卡兒乘積方法構(gòu)造而得到[3].由笛卡兒乘積方法構(gòu)造出來的網(wǎng)絡(luò)保留小網(wǎng)絡(luò)的諸多優(yōu)點，比如正則性、Euler性、Hamilton性、點可遷性等性質(zhì).超立方體網(wǎng)絡(luò)是一類著名的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).n維超立方體（n－dimensional hypercube），記為Qn，是由n個K2的笛卡兒乘積K2×K2×…×K2構(gòu)造而得.

對于超立方體以及超立方體的變形網(wǎng)絡(luò)（如交叉立方體、局部扭立方體、增廣立方體）的最小反饋點集問題的結(jié)論目前還比較少，F(xiàn)ocardi等[4]給出了超立方體Qn的反饋數(shù)的漸進(jìn)界為.王彥輝等[5]給出了折疊超立方體Qfn的反饋數(shù)的漸進(jìn)界為等[6]研究了有向圖的反饋點集問題；文獻(xiàn)[7～9]對網(wǎng)格圖和置換圖的反饋點集問題進(jìn)行了研究.文獻(xiàn)[10～13]給出 了 Directed split－stars、Kautz digraphs、Shuffle－based interconnection networks 等 著 名的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的反饋數(shù)的較好的上界.Xu等[14～16]對與線圖相關(guān)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，如de Bruijn有向圖和de Bruijn無向圖的反饋數(shù)進(jìn)行了研究，得到了較好的反饋數(shù)的漸進(jìn)界.

本文通過構(gòu)造剩余子圖G[V（Qfn）－F]的極大無圈子圖得到極小反饋點集，從而得到反饋數(shù)的上界的方法，來研究折疊超立方體網(wǎng)絡(luò)Qfn的反饋數(shù)問題.

1 定義和引理

n維折疊超立方體網(wǎng)絡(luò)Qfn的概念是El－Amawy等[17]提出的.Qfn的頂點集合為

頂點x＝x n x n－1…x1與y＝y(tǒng) ny n－1…y1有邊相 連 當(dāng) 且 僅 當(dāng)y＝y(tǒng) ny n－1…y1＝x n x n－1…x i＋1珚x ix i－1…x1，1≤i≤n（此時（x，y）稱為正常邊）或者y＝y(tǒng) ny n－1…y1＝珚x n珚x n－1…珚x1（此時（x，y）稱為補邊），頂點y稱為頂點x的補點.

由此可見，n維折疊超立方體網(wǎng)絡(luò)是超立方體變形網(wǎng)絡(luò)，其通過在n維超立方體網(wǎng)絡(luò)Q n中添加2n－1條補邊構(gòu)造生成，如圖1所示.

圖1 折疊超立方體Q f3和Q f4Fig.1 Folded hypercube Q f3 and Q f4

由于Qfn具有下述優(yōu)良的性質(zhì)，被認(rèn)為是替代超立方體Qn的挑戰(zhàn)性網(wǎng)絡(luò)結(jié)構(gòu).

（1）Qfn有2n個頂點，（n＋1）2n－1條邊，且是n＋1正則圖；

（2）Qfn直徑為

（3）Qfn的連通度為n＋1；

（4）Qfn是點可遷圖和邊可遷圖，因而是Cayley圖；

（5）當(dāng)n為奇數(shù)時Qfn是二部分圖，當(dāng)n為偶數(shù)時，Qfn是非二部分圖.

定義1 給定n維折疊超立方體Qfn的頂點，若則稱x為偶頂點；若，則稱x為奇頂點.

設(shè)為折疊超立方體Qfn中所有奇頂點構(gòu)成的集合，為折疊超立方體Qfn中所有偶頂點構(gòu)成的集合，則Qfon和Qfen是Qfn的頂點集合的一個劃分，故V（Qfn）＝Qfon∪Qfen.

定義2 給定超立方體Qn的兩個頂點x和y， 設(shè)x＝xnxn－1…x1，y＝y(tǒng)nyn－1…y1， 稱為兩個頂點x和y之間的Hamming距離.

定義3 設(shè)S為超立方體Qn頂點子集，若對于任意頂點x，y∈S，均有DH（x，y）大于k（k為自然數(shù)），則稱S為超立方體Qn的k分離集.

引理1[4]對任何整數(shù)n≥2，超立方體Qn中含有一個4分離集.設(shè)這個4分離點集合為R，R至少由2n－2/（n－1）個偶頂點組成，則R和Qn中所有的奇頂點的并導(dǎo)出的子圖不含圈.

定義4 對于點集Q每個元素后面加上數(shù)串b形成的點集記為Qb.

例如R0為二進(jìn)制編碼點集合R的基礎(chǔ)上后面加0形成的點集合，為二進(jìn)制編碼點集合Qn的基礎(chǔ)上后面加00的點集合.

為中所有奇頂點的集合，為偶頂點集合.顯然R0、、中的頂點的長度是n＋1.

2 折疊超立方體的反饋數(shù)的上界

由于當(dāng)n為奇數(shù)時，n維折疊超立方體Qfn是二部分圖，然而當(dāng)n為偶數(shù)時n維折疊超立方體Qfn是非二部分圖，下面分別討論折疊超立方體的反饋數(shù)的上界.

2.1 折疊超立方體的階為奇數(shù)的情況

定理1 當(dāng)n為奇數(shù)時，折疊超立方體Qfn＋2中由頂點子集合導(dǎo)出的子圖不含圈.

證明 因為n為奇數(shù)，n＋2也為奇數(shù)，故Qfn＋2是二部分圖.又因為Qfn＋2中的奇頂點集合Qfon＋2及偶頂點集合Qfen＋2各為一半且各自為Qfn＋2的獨立集，所以任意兩個偶頂點之間沒有邊關(guān)聯(lián)，任意兩個奇頂點之間也沒有邊關(guān)聯(lián).

因為內(nèi)都為奇頂點且是獨立集，所以Q00fon內(nèi)部任意兩個頂點之間均沒有邊關(guān)聯(lián).

現(xiàn)在討論與之間的關(guān)系.

由引理1知R00∪Q00fon導(dǎo)出的子圖不含圈，且最后一位都為00，所以R00∪Q00fon導(dǎo)出的子圖的邊均為正常邊.

（2）與以及與的關(guān)系

由定義4可知是由Qfon后加00組成的集合，而是由Qfen后加01組成的集合，所以之間有正常邊，且為一一對應(yīng)的，沒有補邊.

換句話說對于任意一個屬于Qfon的字串α∈Qfon，有，則α00與α01、α10兩個頂點相關(guān)聯(lián)，均為正常邊，故不含圈.

同理，對于任意一點α∈Q11fen，其補點珔α必然在Q00fon中，則Q00fon與Q11fen構(gòu)成了一個雙射函數(shù).即之間有2n條補邊包含且只包含一個中的點.

R00Q01Q10Q11Q00導(dǎo)出的子圖不含圈.

定理2 對任意n≥4的奇數(shù)，Qfn的反饋數(shù)的上界為f（n）≤2n－1（1－1/8（n－3））.

Q11fen∪Q00fon在n＋2維折疊超立方體Qfn＋2導(dǎo)出的子圖不含圈，因此

所以n＋2維折疊超立方體Qfn＋2的反饋數(shù)的上界為f（n＋2）≤｜Qfn＋2｜－

即n維折疊超立方體Qfn的反饋數(shù)的上界為f（n）≤2n－1（1－1/8（n－3））.

2.2 折疊超立方體的階為偶數(shù)的情況

定理3 當(dāng)n為奇數(shù)時，Qfn＋3是偶階的，由Qfn＋3中的點R000∪Qfon＋3導(dǎo)出的子圖不含圈.

證明 分正常邊和補邊兩種情況進(jìn)行討論.

（1）R000∪Qfon＋3的補邊

當(dāng)n為奇數(shù)時，n＋3是偶數(shù)，一個點和其補點是同奇偶的，所以R000和Qfon＋3之間沒有補邊.R000后三位均為000，故其內(nèi)部點之間沒有補邊.

又因為Qfon＋3為Qfn＋3的全部奇頂點，所以由定義可知Qfon＋3內(nèi)部有2n＋1條補邊.將Qfon＋3按照后三位進(jìn)行子集合分解可以得到8個子集的并集如下：

于是Q000fon的補點在Q111fon中，則Q000fon與Q111fon之間有2n－1條補邊，且Q000fon中的點與Q111fon中的補點是一一對應(yīng)的.

同理Q001fon與Q110fon、Q010fon與Q101fon、Q011fon與Q100fon之間具有相同的性質(zhì).

（2）R000∪Qfon＋3的正常邊

因為折疊超立方體中正常邊的兩條邊不能同奇偶，顯然R000內(nèi)部沒有正常邊，Qfon＋3內(nèi)部也不包含正常邊.所以只需計算R000和Qfon＋3之間的正常邊即可.

由引理1可得，R000∪Q000fon構(gòu)成一個無圈子圖.

因為對于任意一個R中的元素α∈R，在α后加子串000形成R000，而在α后分別加子串001、010、100形成3個點集，分別為Q001fon、Q010fon、Q100fon的子集，則R000與Q001fon、Q010fon、Q100fon的子集有連邊且為一一對應(yīng)關(guān)系.又因為Q000fon、Q001fon、Q010fon、Q100fon之間沒有補邊相關(guān)聯(lián)，即沒有任何邊，所以由R000∪Q000fon∪Q001fon∪Q010fon∪Q100fon導(dǎo)出的子圖為無圈子圖.

綜上，構(gòu)成的R000∪Qfon＋3在Qfn＋3導(dǎo)出的子圖為無圈子圖.

定理4 對任意n≥4的偶數(shù)，Qfn的反饋數(shù)的上界為f（n）≤2n－1（1－1/16（n－4））.

證明 由定理3可知，R000∪Qfon＋3在Qfn＋3導(dǎo)出的子圖不含圈，故得到

所以n＋3維折疊超立方體Qfn＋3的反饋數(shù)的上界為

所以n維折疊超立方體Qfn的反饋數(shù)的上界為

3 無圈導(dǎo)出子圖的連通性分析

定理5 如果n為奇數(shù)，則構(gòu)造的Qfn＋2的無圈導(dǎo)出子圖的連通分支個數(shù)和Qn的無圈子圖R∪Qfon中連通分支個數(shù)一致.

證明 設(shè)H＝G[R00∪Q01fen∪Q10fen∪Q11fen∪Q00fon]，考慮無圈導(dǎo)出子圖H的邊的情況.實際上，H的邊是在R∪Qfon邊的基礎(chǔ)上增加與Q01fen∪Q10fen∪Q11fen的點之間的邊，也即，在R∪Qfon基礎(chǔ)上，增加Q01fen∪Q10fen∪Q11fen這些點，并沒有增加實際的連通分支.

定理5表明，當(dāng)n為奇數(shù)時，構(gòu)造的Qfn＋2的無圈導(dǎo)出子圖的整體連通性能與引理1中構(gòu)造的Qn中不含圈導(dǎo)出子圖R∪Qfon的是一致的，但由于階數(shù)大了兩階，連通性能比同類其他反饋集變得更優(yōu).

4 結(jié) 語

反饋數(shù)問題是圖論和網(wǎng)絡(luò)理論極難的問題之一，文獻(xiàn)中有關(guān)此研究領(lǐng)域的結(jié)果不多，關(guān)鍵是還沒有找到一個好的方法來處理這個問題.本文所討論的n維折疊超立方體在n為奇數(shù)和偶數(shù)時分別是二部分圖和非二部分圖，根據(jù)此性質(zhì)，本文對于n為奇數(shù)和偶數(shù)兩個大類的情況分別構(gòu)造了n維折疊超立方體的無圈導(dǎo)出子圖，給出了折疊超立方體網(wǎng)絡(luò)的反饋數(shù)的新的上界，改進(jìn)了已有的結(jié)果.

[1]GAREY M R，JOHNSON D S.Computers and Intractability[M].San Francisco：Freeman，1979

[2]BEINEK L W，VANDELL R C.Decycling graphs[J].Journal of Graph Theory，1997，25（1）：59－77

[3]XU Jun－ming.Topological Structure and Analysis of Interconnection Networks [M].London：Kluwer Academic Publishers，2001

[4]FOCARDI R，LUCCIO F L，PELEG D.Feedback vertex set in hypercubes[J].Information Processing Letters，2000，76（1－2）：1－5

[5]王彥輝，徐俊明.折疊超立方體網(wǎng)絡(luò)的最小反饋點集[J].運籌與管理，2005，14（6）：8－11

[6]SMITH G W JR， WALFORD R B. The identification of a minimal feedback vertex set of a directed graph[J].IEEE Transaction on Circuits and Systems，1975，CAS－11（1）：9－15

[7]BAU S，BEINEKE L W，LIU Z.etal.Decycling cubes and grids [J].Utilitas Mathematica，2001，59：129－137

[8]LIANG Y D.On the feedback vertex set problem in permutation graphs [J].Information Processing Letters，1994，52（3）：123－129

[9]LUCCIO F L.Almost exact minimum feedback vertex set in meshes and butterflies[J].Information Processing Letters，1998，66（2）：59－64

[10]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

[11]WANG Fu－h(huán)sing，HSU Cheng－ju，TSAI Jen－chih.Minimal feedback vertex sets in directed split－stars[J].Networks，2005，45（4）：218－223

[12]KRLOVIC R，RUZICKA P.Minimum feedback vertex sets in shuffle－based interconnection networks[J].Information Processing Letters，2003，86（4）：191－196

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

[14]XU Xi－rong，CAO Yong－chang，XU Jun－ming，etal.Feedback numbers of de Bruijn digraphs[J].Computer and Mathematics with Applications，2010，59（2）：716－723

[15]XU Xi－rong， YANG Yuan－sheng， MING Di.Feedback vertex set of generalized de Bruijn digraphsGB（d，n）[J].Utilitas Mathematica，2009，79：107－124

[16]XU Xi－rong，XU Jun－ming，CAO Yong－chang.Bounds on feedback numbers of de Bruijn graphs[J].Taiwanese Journal of Mathematics，2011，15（3）：1101－1113

[17]EL－AMAWY A， LATIFI S. Properties and performance of folded hypercubes [J].IEEE Transaction on Parallel and Distributed Systems，1991，2（1）：31－42