發(fā)布時間：2018-08-02 20:25

【摘要】：在互連網(wǎng)絡(luò)中,匹配排除用于衡量在邊連接失敗的情形下互連網(wǎng)絡(luò)的強健性.一個偶階圖的匹配排除數(shù)是指最少邊數(shù),使得刪除這些邊所得圖不存在完美匹配.很多互連網(wǎng)絡(luò)被證明是極大匹配的和超匹配的.最近,條件匹配排除數(shù)的概念被引入來研究不是關(guān)聯(lián)同一個頂點的匹配排除集.一個偶階圖的條件匹配排除數(shù)是指最少邊數(shù),使得刪除這些邊所得圖不存在完美匹配也不存在孤立點.本文主要研究了廣義Petersen圖(9),6))的匹配排除和條件匹配排除問題.我們得到廣義Petersen圖(9),6))是極大匹配的;廣義Petersen圖(9),6))除了少數(shù)幾種情況都是超匹配的,條件極大匹配的.此外,我們表明(9),6))不是條件超匹配的,如果它包含3長圈或4長圈或5長圈.由此可知(9),1)和(9),2)不是條件超匹配的,而且我們也確定了(9),1)和(9),2)的全部非平凡的最優(yōu)條件匹配排除集.
[Abstract]:In interconnection networks, matching exclusion is used to measure the robustness of the interconnection network in the event of a failure of an edge connection. The matching exclusion number of a graph of even order refers to the minimum number of edges so that there is no perfect match between the graphs obtained by deleting these edges. Many interconnection networks have been proved to be extremely matched and supermatched. Recently, the concept of conditional matching exclusion number was introduced to study the matching exclusion set which is not associated with the same vertex. The conditional matching exclusion number of a graph of even order refers to the minimum number of edges so that there is no perfect matching and no outliers in the graph obtained by deleting these edges. In this paper, the problem of matching exclusion and conditional matching exclusion of generalized Petersen graph (9) is studied. We obtain that the generalized Petersen graph (9) ~ (6) is maximal matched, and the generalized Petersen graph (9) ~ (6) is supermatched except for a few cases. In addition, we show that (9) (6) is not conditional supermatch if it contains 3 long cycles, 4 long cycles or 5 long cycles. It can be seen that (9) 1) and (9) 2) are not conditional supermatched, and we also determine all the nontrivial optimal conditional matching exclusion sets of (9) 1) and (9) 2).
【學(xué)位授予單位】：蘭州大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5

【相似文獻】

相關(guān)期刊論文 前10條

1 黃煦艷,李喬;Petersen圖的一致最優(yōu)可靠性[J];上海交通大學(xué)學(xué)報;2001年05期

2 劉平,殷志祥;廣義Petersen圖的可擴性[J];淮南工業(yè)學(xué)院學(xué)報;2001年03期

3 侯新民,王天明;廣義Petersen圖的寬直徑(英文)[J];數(shù)學(xué)研究與評論;2004年02期

4 ;ANALYSIS ON STABILITY OF ROCK-FILL DYKES IN A MOUNTAIN RIVER[J];Journal of Hydrodynamics(Ser.B);2004年06期

5 ;Wide Diameter of Generalized Petersen Graphs[J];數(shù)學(xué)研究與評論;2010年03期

6 劉弦;;廣義Petersen圖的同構(gòu)問題[J];河南科學(xué);1991年01期

7 莊容坤;;廣義Petersen圖的再推廣[J];惠陽師專學(xué)報(自然科學(xué)版);1993年03期

8 彭錦,王衛(wèi)兵,毛經(jīng)中;剖分Petersen圖得到的新測地塊(英文)[J];運籌學(xué)學(xué)報;2003年03期

9 馬登舉,任韓,盧俊杰;廣義Petersen圖G(2m+1,m)的交叉數(shù)[J];華東師范大學(xué)學(xué)報(自然科學(xué)版);2005年01期

10 周樹娜;劉煥平;楊海寬;;關(guān)于廣義Petersen圖點堅韌度的注記[J];新疆師范大學(xué)學(xué)報(自然科學(xué)版);2008年01期

相關(guān)碩士學(xué)位論文 前10條

1 李賓慶;廣義Petersen圖的匹配排除問題[D];蘭州大學(xué);2017年

2 郭炳;廣義Petersen圖和循環(huán)圖的最小點覆蓋算法及應(yīng)用研究[D];山西大學(xué);2014年

3 譚學(xué)功;寬直徑[D];華南師范大學(xué);2005年

4 李蘇;廣義Petersen圖的條件色數(shù)[D];暨南大學(xué);2012年

5 鄭百功;冒泡排序圖B_n和廣義Petersen圖P（10,3）的交叉數(shù)[D];大連理工大學(xué);2013年

6 呂凱;廣義Petersen圖的Liar支配和距離雙支配研究[D];大連理工大學(xué);2010年

7 汪家錄;一類廣義Petersen圖P（N，k）的1-因子數(shù)及相關(guān)問題研究[D];華東師范大學(xué);2011年

8 吉春年;廣義Petersen圖和循環(huán)圖的羅馬支配研究[D];大連理工大學(xué);2008年

9 陳華珠;廣義Petersen圖的條件著色和L（2，，1）-標號[D];暨南大學(xué);2011年

10 田旌熙;循環(huán)圖和廣義Petersen圖的支配參數(shù)[D];大連理工大學(xué);2008年

本文編號：2160624