關于局部扭立方體的反饋數

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

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

0 引 言

在組合網絡理論中，若一個簡單圖刪除某些節點后構成的導出子圖不存在回路，則稱被刪去的節點集合為該簡單圖的反饋點集.階數最小的反饋點集稱為最小反饋點集，最小反饋點集的階數叫做反饋數.

確定圖的最小反饋點集問題，因其在諸多領域內的廣泛應用而受到重視.例如在互聯網中，如果網絡有回路，廣播消息會一直在網橋環網中傳遞，形成“廣播風暴”，阻塞網絡.解決這個問題的做法就是想辦法盡可能少地關閉一些網橋，使剩下的網絡不再有回路［1］.再如：任何一個具有自動化功能的工作單位，都需要不斷地發出指令，再分析指令執行的結果，然后發出新的指令，用以調整或改變工作狀態.持續不斷的反饋是自動化得以實現的關鍵.另外，在操作系統和超級計算機的分布式計算中避免死鎖產生的問題，同樣也是確定網絡反饋點集的問題［2］.

因為確定一般網絡（或圖）的最小反饋點集問題屬NP 難問題［3］，所以現階段還不能對這一問題給出令人滿意的結論.盡管在一些文獻中，對某些特殊拓撲結構圖（如mesh網絡、toroids網絡、butterflies網絡、立方連通網絡、超立方體網絡和星圖等）的反饋數的上界和下界都已經陸續得到［4－19］，但即使是得到了具體的圖，要確定其最小反饋集仍不是容易的事.

本文根據局部扭立方體頂點集合中最后一位字節不同的特點，將其頂點集合劃分為兩個不相交的子集，并構造極大無圈子圖得到反饋數的上界，從而研究局部扭立方體的反饋數問題.

1 定義和引理

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

定義1Qltn的邊集由這樣的邊組成：對任意兩個頂點x＝x1x2…xn和y＝y1y2…yn，它們之間進行連邊，當且僅當它們滿足如下要求之一：

（1）存在一個整數k（1≤k≤n－2）滿足yk是xk的補點，xk∈｛0，1｝），yk＋1＝（xk＋1＋xn）mod 2，x和y的其余字節均相同（x和y僅有連續兩位字節不同），此時（x，y）稱為非匹配邊；

（2）存在一個整數k∈｛n－1，n｝，x和y僅在第k位不同，其余字節全相同，則x和y存在連邊，并稱（x，y）為匹配邊.

由上述定義不難發現，Qlt2由標記為00、01、10和11的4個頂點以及4條邊（00，01）、（00，10）、（01，11）、（10，11）組成.

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

定義2 圖G中兩兩互不相鄰的頂點構成的集合S稱為圖G的獨立集.

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

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

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

2 局部扭立方體的反饋數的上界

定義3 對于局部扭立方體Qltn，頂點x＝x1x2…xn∈V（Qltn）.定義：

顯然，AQn是Qltn的所有奇頂點構成的集合，BQn是Qltn的所有偶頂點構成的集合，且V（Qltn）＝AQn∪BQn，AQn∩BQn＝.

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

通常，由Qltn＝0Qltn－11Qltn－1知，可根據第一位字節的不同將Qltn的頂點劃分為兩個不相交的子集.

本文給出一種新的劃分方法：根據最后一位字節的不同將Qltn的頂點劃分為兩個不相交的子集.

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

即T0n－1與M1n－1為Qltn的頂點劃分的兩個不相交的子集.

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

首先給出新劃分的兩個不相交的子集T0n－1與M1n－1的性質.

引理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））.

因為G0是Qltn中Tn0－1的導出子圖，x，y∈且x和y的最后一位字節都為0.由Qltn定義知，當且僅當x和y只有一位字節不同時存在連邊，這與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的規則易得到集合Rn和Sn與Mn之間有如下結果：

根據歸納 可 得Rn∪Sn＝0Rn－1∪1Rn－1∪0Sn－1∪1Sn－1＝0Mn－1∪1Mn－1＝Mn.

因為Mn＝Rn∪Sn，則M1n＝R1n∪S1n.

現在討論R1n與S1n所誘導的子圖之間的關系.

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

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

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

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

對n分為奇數和偶數兩種情形來歸納證明.

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

因為R2k＋1＝0R2k∪1R2k，則R12k＋1＝0R12k∪1R12k.由假設G（R12k）含匹配邊，則G（0R12k）和G（1R12k）含匹配邊.

為證明G（R12k＋1）含有匹配邊，只需證明0R12k與1R12k之間各點無連邊.用反證法證明，假設0R12k與之間有點相連接，即a∈0R12k，b∈1R12k，a與b有連邊，（a，b）∈E（G（R12k＋1））.因為R2k＝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僅有連續兩位字節不同，其余全相同.顯然，a和b的第一位字節不同，若（a，b）為非匹配邊，則第二位字節必不相同.那么，分兩種情況考慮：

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

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

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

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

因為R2k＋2＝0R2k＋1∪1S2k＋1，則R12k＋2＝0R12k＋1∪1S12k＋1.由 假 設G（R12k＋1）含 匹 配 邊，則G（0R12k＋1）和G（1R12k＋1）含匹配邊.

為證明G（R12k＋2）含有匹配邊，只需證明0R12k＋1與之間各點無連邊.用反證法證明，假設與1S12k＋1之 間 有 點 相 連 接，即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僅有連續兩位字節不同，其余全相同.顯然，a和b的第一位字節不同，若（a，b）為非匹配邊，則第二位字節必不相同.那么，分兩種情況考慮：

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

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

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

由引理2知，T0n－1＝Q0n－1＝AT0n－1∪BT0n－1，其中AT0n－1為Q0n－1的奇數點集合，BT0n－1為Q0n－1的偶數點集合.AT0n－1和BT0n－1分別是Q0n－1的獨立集.

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

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

因為AT0n－1T0n－1，R1n－1M1n－1，由Qltn定義知，頂點x∈AT0n－1與頂點y∈R1n－1當且僅當最后一位字節不同，其余字節相同時兩點之間有連邊.即若x與y相連，則x＝xn－1xn－2…x10∈AT0n－1，至多存在一個y＝yn－1yn－2…y11∈R1n－1.因此，G（AT0n－1∪R1n－1）的導出子圖是不含圈的.證畢.

由引理4和反饋點集的定義，得下面引理.

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

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

證明 因為則有即2n－1，所以f（n）≤V（Qltn）＼（AT0n－1∪R1n－1）＝2n－2n－1＝2n－1.證畢.

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

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

注：事實上，可證G（BT0n－1∪S1n－1）是不含圈的，V（Qltn）＼（BT0n－1∪S1n－1）也是Qltn的反饋點集.因為可 得f（n） ≤V（Qltn）＼（BT0n－1∪S1n－1）＝2n－2n－1＝2n－1，即結合引理1也可得到定理2.

3 結 語

對一般圖確定最小反饋點集是一個NP難問題，準確計算出圖的最小反饋點集是很困難的.至今，人們只對一些特殊的圖給出了求最小反饋點集的多項式時間的算法.本文根據n維局部扭立方體頂點集合中最后一位字節不同的特點，將其頂點集合劃分為兩個不相交的子集，構造極大無圈子圖并得到了局部扭立方體網絡的反饋數的上界.

［1］ 周書明.六角形蜂窩網絡的反饋數［J］.工程數學學報，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］ 吳葉舟.線圖的反饋數［D］.合肥：中國科學技術大學，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，Fujito 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.