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

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

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