k-連通圖中生成樹和完美匹配上的可收縮邊.pdf

1、圖論是組合數(shù)學(xué)的分支，是一個具有悠久歷史并且發(fā)展迅速的數(shù)學(xué)分支。它起源于一個古老的民間游戲—格尼斯堡七橋問題。1736年歐拉解決了上述問題，發(fā)表了關(guān)于圖論的第一篇文章，圖論由此產(chǎn)生。
　　圖的結(jié)構(gòu)特征是圖論的主要研究方向之一，其中圖的連通性一直是圖論研究的重要課題。在研究圖的連通性的過程中主要包括對圖的結(jié)構(gòu)特征進(jìn)行探究和分析。在進(jìn)行有關(guān)連通圖的構(gòu)造時，我們一般采用一些定義作為基礎(chǔ)，并且運(yùn)用特殊的運(yùn)算來保持圖的連通性，對復(fù)雜的連通圖

2、進(jìn)行上述運(yùn)算得到簡單的連通圖。因為可去邊與可收縮邊能夠保持圖的連通性，所以它們成為構(gòu)造連通圖的常用工具。
　　假設(shè)邊e=xy∈E(G)，把頂點(diǎn)x，y都去掉，并把與這兩個頂點(diǎn)關(guān)聯(lián)的邊都去掉，再將一個新的頂點(diǎn)u添加到圖G中，并且將剛剛?cè)サ舻膬蓚€頂點(diǎn)的所有鄰點(diǎn)與新增的頂點(diǎn)鄰接。上述運(yùn)算即為將邊e收縮，得到的新圖記為G/e。如果得到的新圖依然能夠保持原圖的連通性，我們稱這條邊e是G的可收縮邊，反之則為不可收縮邊。
　　本文主要研究k

3、-連通圖中的可收縮邊的存在性及數(shù)目，分別為k-連通圖中生成樹上的可收縮邊數(shù)目以及如果圖中存在完美匹配時完美匹配上的可收縮邊數(shù)目，并得下述結(jié)果。
　　定理2.1假設(shè)G是階數(shù)為n(n≥7)的k-連通圖（k≥3），H是G的一棵生成樹，滿足圖G的任意斷片階數(shù)都大于「k/2(])，則H上至少有k+1條可收縮邊。
　　假設(shè)k-連通圖中存完美匹配，給出其可收縮邊數(shù)目的結(jié)果如下:
　　定理3.1假設(shè)G是階數(shù)為n（n≥0）的k-連通圖（