圖的割空間的若干性質(zhì).pdf

1、本文主要研究了圖的割空間理論及相關(guān)性質(zhì)，這是圖論研究領(lǐng)域中的一個重要方面。但是與相對較為成熟的圈空間理論相比，對割空間的研究則顯得較少。作為相互正交的兩個空間，它們之間有著密切的聯(lián)系。我們首先證明了最小割基在結(jié)構(gòu)上的唯一性。然后，通過研究割的性質(zhì)，得到拓撲圖論中的一個重要性質(zhì)，即不可分離圈不能由若干可分離圈生成。最后，給出了一個找最短割的多項式算法，并以此部分解決了Thomassen[18]關(guān)于是否存在多項式算法尋找短圈的問題。另外，我

2、們還研究了2-邊著色的完全圖中單色三角形的最小數(shù)目，并確定了該最小值。具體內(nèi)容如下： 1．通過建立一個基變換的Hall型定理，得到一個判定最小割基的充分必要條件，以此證明了最短割基在結(jié)構(gòu)上的唯一性(即：任兩個最短割基之間，一定存在一個1-1映射使得所對應(yīng)的割的長度相等)。 2．通過定義嵌入圖的幾何對偶圖及其相應(yīng)的嵌入系統(tǒng)，得到幾何對偶圖中的可分離圈就對應(yīng)于原圖中的割；反之，若幾何對偶圖中的割在原圖中對應(yīng)于一個圈，那么該圈