完全多部圖的容錯泛圈性和容錯泛連通性研究
報告人：王超越
指導老師：陳協彬教授
1課題研究背景及選題意義
計算機效能在很大程度上取決於它的拓撲結構。很多年來,許許多多的拓撲結構被提出和研究。如超方體及各種變形、環託、star圖、迴圈圖、交錯群圖互連網路等等,已經被深入地研究和廣泛地**.
互連網路的可靠性(reliability)是評估網路效能的重要概念,高可靠性的互連網路一直是網路設計者追求的重要目標之一.網路拓撲結構是否合理會影響系統的可靠性.對於乙個給定的互連網路,最多能容許多少個節點和（或）連線同時發生故障,而剩餘的子網路中仍然具有某種結構或各節點之間還仍能繼續保持通訊，文獻上習慣稱這種可靠性為容錯性（fault tolerance）。
網路容錯性的實質是當故障發生時,剩餘網路的重組能力。大規模互連網路在執行中故障往往難以避免,因此,研究網路的容錯能力備受關注。
在互連網路中,乙個結構能被另乙個結構模擬是很重要的。網路模擬問題能歸納為圖的嵌入問題。因此,設計和衡量乙個互連網路的中心問題之一就是研究圖的嵌入能力。
路或圈網路具有結構簡單、度數小、通訊成本低的優點,因而它們是並行處理和分布計算中的兩個最受歡迎的互連網路。若乙個網路含有不同長度的路或圈,則它就能夠有效地模擬許多設計**性陣列或環上的演算法。因此,研究互連網路的泛圈性或泛連通性具有實際的意義。
泛圈性可以度量該網路是否可以嵌入任意長度的圈。泛連通性是泛圈性的深化,如果乙個網路是泛連通的則一定是泛圈的。
完全多部圖(complete multipartite graph),是一類重要的圖,也是一類基本的互連網路拓撲結構，研究它的容錯泛圈性和容錯泛連通性很有意義。完全多部圖是指乙個簡單圖,它的頂點集可分解為多個非空子集,兩個頂點相鄰當且僅當它們不在同一子集中。完全k部圖常記作或者,這裡表示部集的點數。
特別的,如果每個部集的點數都為n時,記為.故擬研究完全多部圖的容錯泛圈性和容錯泛連通性,用歸納法進行推理論證。
2國內外研究現狀及問題分析
關於網路的泛圈性和泛連通性,一直是研究熱點。容錯泛圈性和泛連通性,限制泛圈性和泛連通性是目前研究的重點。目前有很多文獻研究了完全多部圖的圖論性質,但對其網路拓撲容錯能力的研究相當少。
下面簡述一些涉及到的主要定義以及國內外對容錯泛圈性和容錯泛連通性的一些研究成果。
一些定義：
圖g稱為泛圈的（pancyclic）,如果g中包含每個長為（）的圈。特別的,圖g稱為泛圈的（pancyclic）如果g中包含每個長為（,其中是g中的最小圈長）的圈。泛圈性最早是由bondy提出的,因為乙個二部圖不包含奇圈,所以後來偶泛圈性的概念被提出。
圖g稱為偶泛圈的（bipancyclic）,如果g中包含每個偶長為（,其中是g中的最小圈長）的圈
圖g為泛連通的（panconnected）.如果對於圖g中任意兩點u和v,g中都存在任意長度為()的（u,v）路。特別的,圖 g稱為泛連通的（panconnected）,如果對於圖g中距離為的任意兩點u和v,g中都存在任意長度為()的（u,v）路。
圖g稱為偶泛連通的（bipanconnected）,如果對於g中距離為的任意兩點u和v,g中都存在長為()的（u,v）路,其中和有相同的奇偶性。
一些結果：
維超立方體( hypercube）（是正則連通的二部圖,有個頂點和條邊,它的每乙個頂點可以用乙個n位二進位制的字串表示,這裡對任意的,中任意的兩個頂點和有邊,當且僅當和之間有乙個位元位不同。
（1）中,表示故障邊集,若,且的每個點至少關聯兩條無故障邊,則對於任意兩個距離為的點和,中都含有每個長為的路,這裡是偶數。
(2) 中,和分別表示故障邊集和故障點集,若,則對於任意兩個距離為的無故障點和,中都含有每個長為的路,這裡是偶數 。
(3) 中,和分別表示故障邊集和故障點集,若, ,則中含有每個偶長從4到的圈。
維摺疊超立方體(folded hypercube),它的頂點集與相同,邊集是由的邊集並上所有補邊得到的。對於中兩點, ,若,則稱是一條補邊。
（4）中,表示故障邊集,若,且每個頂點至少關聯兩條無故障邊,則中含有每個偶長從到的圈。並且,當且為偶數時,中含有每個奇長從到的圈。
（5）中,和分別表示故障邊集和故障點集,若,則對於任意兩個距離為的無故障點和,都含有每個長為的路,這裡是偶數。
3-進製n-方體（n個3-圈的笛卡爾乘積）,是包含個頂點,正則圖,它的每個頂點可以用位位元表示,這裡（）。兩個頂點和是相鄰的當且僅當存在乙個正數, ,使得,並且對任意的都成立。
（6）3-進製n-方體中,表示故障邊集,若,且每個頂點至少關聯兩條無故障邊,則是泛圈的。
k-進製n-方體（n個k-圈的笛卡爾乘積）,它的每個頂點可以用位位元表示,這裡（）。兩個頂點和是相鄰的當且僅當存在乙個正數, ,使得,並且對任意的都成立。
（7）中,表示故障邊集, ,且每個頂點至少關聯兩條無故障邊,則是偶泛圈的。
（8）中,和分別表示故障邊集和故障點集,若,則是泛連通的。
3擬研究內容
完全多部圖的容錯泛圈性和容錯泛連通性。
4參考文獻
[1] bondy, murty, graph theory with applications,macmillan press, london,1976.
[2]x.-b. chen, hamiltonian paths and cycles passing through a prescribed path in hypercubes, inform.
process. lett.110(2009)77–82.
[3]x.-b. chen, edge-fault-tolerant diameter and bipanconnectivity of hypercubes,inform.
process. lett.110(2010)1088-1092.
[4]x.-b. chen, some results on topological properties of folded hypercubes, lett.
109(2009)395-399.
[5]x.-b. chen, on path bipancyclicity of hypercubes, inform.
109(2009)594–598.
[6]m. j. ma,g.
z. liu and j. m.
xu, panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes,parallel computing,33(1):36–42,2007.
[7]j. h. park, panconnectivity and edge-pancyclicity of faulty recursive circulant g(2m, 4), theoretical computer science, 390(1):
70–80, 2008.
[8]j. h. park, h.
s. lim, and h. c.
kim,panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements,theoretical computer science,377:170–180,2007.
[9]i. a. stewart and yonghong xiang,bipanconnectivity and bipancyclicity in k-ary n-cubes,ieee transactions on parallel and distributed systems,
20(1):25–33,2009.
[10]j. m. xu and m.
j. ma, survey on path and cycle embedding in some networks, frontiers of mathematics in china,4(2):217–252,2009.
[11] hsieh, some edge-fault-tolerant properties of the folded hypercube, networks 51(2)(2008)92–101.
[12]j. fan, x. lin, x. jia, node-pancyclicity and edge-pancyclicity of crossed cubes,inform
[13] and edge-fault-tolerant bipancyclicity of hypercubes,inform process.
lett.87(2003)107–110.
[14] kim, lim, panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements,
[15] tsai, linear array and ring embeddings in conditional faulty hypercubes, sci.314(2004)431–443.
[16] xu, du, m. xu, edge-fault-tolerant edge-bipancyclicity of hypercubes, inform process. lett.
96(2005)146–150
[17] xu, ma, cycles in folded hypercubes, appl. math. lett.
我的開題報告
本科生畢業 設計 開題報告 建築工程學院工程造價專業 本科 2012級 1 班 題目 昆明某綜合樓畢業預算設計 畢業 設計 起止時間 2015年 11 月 2016 年 1 月 共8周 學生姓名 楊杰學號 2012311607指導教師任彥華 報告日期 2015年11月9日 雲南農業大學教務處制 20...
我的開題報告
瀋陽工業大學 本科生畢業設計 開題報告 畢業設計題目 化纖毛紡廠變電所設計 學院 瀋陽工業大學工程學院 專業班級 電氣工程及其自動化0303 學生姓名 王晶晶 指導教師 皮紅梅 副教授 2007年 4 月 2 日 化纖毛紡廠變電所設計 一 課題研究的目的和意義 工廠供電，就是指工廠所需電能的 和分配...
北航畢業設計 開題報告 我的
超大展弦比無人機氣動效能分析 2015年 3月 一 課題背景 solar impulse是乙個瑞士的長航程太陽能飛機專案，它由瑞士心裡學家和飛機駕駛員伯特蘭皮卡德和瑞士商人安德烈博爾施伯格共同主持，目標是用僅由太陽能提供動力的飛機實現環球飛行。此次畢業設計為對solar impulse 1的機翼進行...