關于折疊超立方體的反饋數

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

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

0 引 言

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

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

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

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

文獻[2]證明了一般圖G＝（V，E）的反饋數的下界為

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

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

對于超立方體以及超立方體的變形網絡（如交叉立方體、局部扭立方體、增廣立方體）的最小反饋點集問題的結論目前還比較少，Focardi等[4]給出了超立方體Qn的反饋數的漸進界為.王彥輝等[5]給出了折疊超立方體Qfn的反饋數的漸進界為等[6]研究了有向圖的反饋點集問題；文獻[7～9]對網格圖和置換圖的反饋點集問題進行了研究.文獻[10～13]給出 了 Directed split－stars、Kautz digraphs、Shuffle－based interconnection networks 等 著 名的網絡拓撲結構圖的反饋數的較好的上界.Xu等[14～16]對與線圖相關的網絡拓撲結構圖，如de Bruijn有向圖和de Bruijn無向圖的反饋數進行了研究，得到了較好的反饋數的漸進界.

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

1 定義和引理

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

頂點x＝x n x n－1…x1與y＝y(tǒng) ny n－1…y1有邊相 連 當 且 僅 當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維折疊超立方體網絡是超立方體變形網絡，其通過在n維超立方體網絡Q n中添加2n－1條補邊構造生成，如圖1所示.

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

由于Qfn具有下述優(yōu)良的性質，被認為是替代超立方體Qn的挑戰(zhàn)性網絡結構.

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

（2）Qfn直徑為

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

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

（5）當n為奇數時Qfn是二部分圖，當n為偶數時，Qfn是非二部分圖.

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

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

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

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

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

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

例如R0為二進制編碼點集合R的基礎上后面加0形成的點集合，為二進制編碼點集合Qn的基礎上后面加00的點集合.

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

2 折疊超立方體的反饋數的上界

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

2.1 折疊超立方體的階為奇數的情況

定理1 當n為奇數時，折疊超立方體Qfn＋2中由頂點子集合導出的子圖不含圈.

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

因為內都為奇頂點且是獨立集，所以Q00fon內部任意兩個頂點之間均沒有邊關聯.

現在討論與之間的關系.

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

（2）與以及與的關系

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

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

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

R00Q01Q10Q11Q00導出的子圖不含圈.

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

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

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

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

2.2 折疊超立方體的階為偶數的情況

定理3 當n為奇數時，Qfn＋3是偶階的，由Qfn＋3中的點R000∪Qfon＋3導出的子圖不含圈.

證明 分正常邊和補邊兩種情況進行討論.

（1）R000∪Qfon＋3的補邊

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

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

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

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

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

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

由引理1可得，R000∪Q000fon構成一個無圈子圖.

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

綜上，構成的R000∪Qfon＋3在Qfn＋3導出的子圖為無圈子圖.

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

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

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

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

3 無圈導出子圖的連通性分析

定理5 如果n為奇數，則構造的Qfn＋2的無圈導出子圖的連通分支個數和Qn的無圈子圖R∪Qfon中連通分支個數一致.

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

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

4 結 語

反饋數問題是圖論和網絡理論極難的問題之一，文獻中有關此研究領域的結果不多，關鍵是還沒有找到一個好的方法來處理這個問題.本文所討論的n維折疊超立方體在n為奇數和偶數時分別是二部分圖和非二部分圖，根據此性質，本文對于n為奇數和偶數兩個大類的情況分別構造了n維折疊超立方體的無圈導出子圖，給出了折疊超立方體網絡的反饋數的新的上界，改進了已有的結果.

[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]王彥輝，徐俊明.折疊超立方體網絡的最小反饋點集[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