本文選題：3-連通圖 + 可收縮邊　； 參考：《廣西師范學(xué)院》2017年碩士論文

【摘要】：圖構(gòu)造的研究是圖論中的重要基礎(chǔ)理論研究,對(duì)圖論的發(fā)展有著重大的影響和推動(dòng)作用.圖的可收縮邊是研究連通圖的結(jié)構(gòu)的強(qiáng)有力工具,在歸納證明連通圖的性質(zhì)中有著重要的作用.本文主要對(duì)k-連通圖的可收縮子圖進(jìn)行研究.主要結(jié)果如下:若3-連通圖G存在一棵生成樹(shù)H使得H中的邊都是不可收縮邊,則稱G是fox.本文對(duì)fox的局部結(jié)構(gòu)進(jìn)行了研究,證明了3-連通圖fox中的3度點(diǎn)恰好關(guān)聯(lián)一條不可收縮邊.證明了極小fox中的不可收縮邊的數(shù)目恰好是|V(G)|-1.即極小fox中存在唯一一棵生成樹(shù)H使得H中的邊都是不可收縮邊.對(duì)極小臨界fox中的3度點(diǎn)的數(shù)目進(jìn)行了估計(jì),證明了至少有V(G)(10)1/2個(gè)3度點(diǎn).證明了fox圖G的特殊子圖H周圍存在子圖H,使G/H'還是fox.這為給出fox的歸納構(gòu)造提供了可能.若3-連通圖G存在一棵生成樹(shù)H使得H中至多有一條可收縮邊,則稱G是擬fox.對(duì)擬fox的局部結(jié)構(gòu)進(jìn)行了研究,證明了其局部存在六種可能的結(jié)構(gòu).在此基礎(chǔ)上對(duì)3-連通圖深度優(yōu)先搜索(DFS)生成樹(shù)上的可收縮邊數(shù)目進(jìn)行了估計(jì),證明了若3-連通圖G的DFS生成樹(shù)H的根不是3度點(diǎn),則H中至少有兩條可收縮邊.有例子表明我們的條件是不能夠減弱的.最后對(duì)極大臨界k-連通圖G上的可收縮邊進(jìn)行刻畫(huà),證明了G中一定存在可收縮邊e,使G/e仍是臨界k-連通圖.
[Abstract]:The study of graph construction is an important basic theory research in graph theory, which has a great influence on the development of graph theory. The contractible edge of a graph is a powerful tool for studying the structure of a connected graph and plays an important role in the induction and proof of the properties of a connected graph. In this paper, we study the retractable subgraphs of k-connected graphs. The main results are as follows: if there exists a spanning tree H in 3-connected graph G such that the edges in H are all non-contractive edges, then G is called fox. In this paper, the local structure of fox is studied, and it is proved that the 3-degree point in 3-connected graph fox is exactly associated with a non-contractive edge. It is proved that the number of non-retractable edges in the minimal fox is exactly the number of the VG)-1. That is, there exists only one spanning tree H in minimal fox such that the edges in H are non-contractive. The number of 3 degree points in minimal critical fox is estimated and it is proved that there are at least 3 V(G)(10)1/2 points. It is proved that there exists a subgraph H around the special subgraph H of fox graph G so that G / H'is fox. This makes it possible to give the inductive structure of fox. If a 3-connected graph G has a spanning tree H such that there is at most one contractible edge in H then G is called quasi fox. The local structure of quasi fox is studied and six possible structures are proved. On this basis, the number of contractible edges on the spanning tree of 3-connected graph depth first search is estimated. It is proved that if the root of the DFS spanning tree H of 3-connected graph G is not a 3-degree point, then there are at least two contractible edges in H. There are examples that show that our conditions cannot be weakened. Finally, the retractable edges on maximal critical k- connected graph G are characterized, and it is proved that there must be retractable edges in G, so that G / e is still a critical k- connected graph.
【學(xué)位授予單位】：廣西師范學(xué)院
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5

【參考文獻(xiàn)】

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

1 王珊珊;齊恩鳳;;k-連通圖中最長(zhǎng)圈上可收縮邊的數(shù)目[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2015年10期

2 崔燕飛;王世英;;某些7-連通圖最長(zhǎng)圈上的可收縮邊[J];太原師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2013年03期

3 鐘玲平;崔慶;;臨界k連通圖中的點(diǎn)度數(shù)[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2012年05期

4 盧建立;張志芳;;6-連通圖最長(zhǎng)圈上的可收縮邊[J];科技導(dǎo)報(bào);2010年21期

5 楊朝霞;;某些5-連通圖中最長(zhǎng)圈上的可收縮邊[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2008年06期

6 吳吉昌,李學(xué)良;4-連通圖中圈上的可去邊和可收縮邊[J];廈門大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年05期

，

本文編號(hào)：1984551