本文選題：k-連通圖　切入點(diǎn)：可收縮邊　出處：《山東大學(xué)學(xué)報(bào)(理學(xué)版)》2016年08期

【摘要】：給出了k-連通圖生成樹和完美匹配上的可收縮邊數(shù)目,得到如下結(jié)果:任意斷片的階都大于「k/2■的k-連通圖中生成樹上至少有4條可收縮邊;若該k-連通圖中存在完美匹配,則完美匹配上至少有「k/2■+1條可收縮邊。
[Abstract]:In this paper, the number of contractible edges on the spanning tree and perfect matching of k-connected graphs is given. The following results are obtained: there are at least four contractible edges on the spanning tree of a kconnected graph whose order of any fragment is greater than "k / 2", if there is a perfect match in the k-connected graph, The perfect match has at least "k / 21 retractable edges".
【作者單位】： 山東大學(xué)數(shù)學(xué)學(xué)院;
【基金】：國家自然科學(xué)基金資助項(xiàng)目(61432010)
【分類號】：O157.5

【相似文獻(xiàn)】

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

1 謝果;判定k-點(diǎn)連通圖與k-邊連通圖極小性的定理[J];四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2000年05期

2 余世群;一類極大臨界h連通圖的性質(zhì)[J];湖北民族學(xué)院學(xué)報(bào)(自然科學(xué)版);2002年04期

3 齊登記,余世群;收縮臨界6-連通圖中的6度點(diǎn)[J];湖北民族學(xué)院學(xué)報(bào)(自然科學(xué)版);2002年04期

4 趙克文,曾克揚(yáng);哈密爾頓連通圖的一點(diǎn)注記[J];工程數(shù)學(xué)學(xué)報(bào);2003年02期

5 趙克文;哈密爾頓連通圖與鄰域并條件[J];信息工程大學(xué)學(xué)報(bào);2003年02期

6 余世群;一類極大臨界2連通圖的結(jié)構(gòu)[J];湖北民族學(xué)院學(xué)報(bào)(自然科學(xué)版);2004年04期

7 陳儀朝,蘇健基;恰含5條非基本邊的極小3連通圖[J];廣西師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年03期

8 林福財(cái);關(guān)于4連通圖的容錯(cuò)直徑和寬直徑[J];漳州師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2005年01期

9 余世群;;一類極大臨界4連通圖的結(jié)構(gòu)[J];湖北民族學(xué)院學(xué)報(bào)(自然科學(xué)版);2006年02期

10 劉育興;蘇健基;;恰有k條非基本邊的極小3連通圖[J];數(shù)學(xué)研究與評論;2006年04期

相關(guān)會(huì)議論文 前1條

1 張薇;張立輝;乞建勛;李星梅;蘇志雄;;帶正權(quán)的無向連通圖中最短路問題研究[A];中國運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

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

1 羅朝陽;圖的點(diǎn)度與距離型拓?fù)渲笜?biāo)參數(shù)及其應(yīng)用[D];山東大學(xué);2015年

2 吳亞平;k-連通圖中最長圈及余直徑研究[D];華中師范大學(xué);2011年

3 康海燕;連通圖中可去邊和圈的研究[D];山東大學(xué);2010年

4 劉素娟;2-（邊-）連通圖的彩虹連通數(shù)[D];南開大學(xué);2013年

5 陳曉東;無爪圖及其擴(kuò)展圖的Hamilton性[D];大連理工大學(xué);2012年

6 侯新民;網(wǎng)絡(luò)（圖）廣義直徑的研究[D];大連理工大學(xué);2002年

7 蔡建生;圖的因子和分?jǐn)?shù)因子[D];山東大學(xué);2007年

8 梁浩;圖的拉普拉斯矩陣和臨界群[D];中國科學(xué)技術(shù)大學(xué);2009年

9 洪振木;某些網(wǎng)絡(luò)可靠性和有效性研究[D];中國科學(xué)技術(shù)大學(xué);2014年

10 Alaa Amer Najim;關(guān)于圖的邊添加和邊減少問題研究[D];中國科學(xué)技術(shù)大學(xué);2006年

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

1 齊恩鳳;k-連通圖的可收縮邊和可收縮圈[D];廣西師范大學(xué);2006年

2 余世群;一類極大臨界h連通圖的結(jié)構(gòu)[D];廣西師范大學(xué);2003年

3 覃城阜;收縮臨界5-連通圖的性質(zhì)[D];廣西師范大學(xué);2004年

4 楊迎球;k連通圖中的k可收縮邊[D];廣西師范大學(xué);2007年

5 張志芳;6連通圖中的可收縮邊[D];河南師范大學(xué);2011年

6 畢振明;恰含6條非基本邊的極小3連通圖[D];山東大學(xué);2012年

7 王雪;7-連通圖最長圈上的可收縮邊及3-連通圖可收縮非邊的分布[D];山東大學(xué);2013年

8 崔燕飛;連通圖中可收縮邊的分布[D];山西大學(xué);2014年

9 洪艷梅;極小限制性邊連通圖的最優(yōu)性和超邊連通圖的容錯(cuò)性[D];新疆大學(xué);2009年

10 陳新衛(wèi);收縮臨界k連通圖中的原子及階較小的端片[D];廣西師范大學(xué);2007年

，

本文編號：1660698