特定形式的圖分割

Abstract

在本論文里，我們研究兩種形式的圖分割。首先我們考慮一種可視為邊著色推廣的圖 分割。如果一個森林 (Forest) 它的分支都是路徑 (Path) 的話，則稱之為路徑森林 。如果一組路徑森林它是一個圖Ｇ的所有邊的分解，則稱之為圖Ｇ的路徑分割。在所 有圖Ｇ的路徑分割中所含之最少路徑森林數稱之為圖Ｇ的路徑數 (Path number)并且 記為 P(Ｇ)。如果限制每條路徑的長度最多為 x，則此種分割形式的路徑數記為 Px (Ｇ)。若 x=1，則 P1(Ｇ) 恰好是圖Ｇ的邊著色數 (Chromatic index)。在本論文中 ，我們研究P2(Ｇ)；當Ｇ是一個樹圖、一個完全圖或是一個平衡完全二分圖時，我們 求出P2(Ｇ)的正確值。 其次，我們考慮一種將圖分為一些同構子圖的分割。在一個n 個點的完全圖中，兩個 圖樣 (Figure) 如果它們沒有共同邊，則稱它們是可相容的(Compatible)。一個構形 (Configuration) 則為一些彼此相容的圖樣所成的集合。在本論文中，我們以長度為 k 的路徑 (Pk+1) 為圖樣。一個構形Ｇ稱為極大 (Maximal)如果不存在有任一個不在 Ｇ中的圖樣f 使得{f}∪Ｇ 也是一個構形。令質譜（Specturm，記為Spec(n，k)）＝ ｛t n｜ 存在一個含有t 個 Pk+1 的極大構形｝。在本論文中的第二部分，我們研究 質譜，當k≦4時，我們完全決定了 Spec(n，k)。