完全二部圖定長的路分解

柴 惠，房明磊

（安徽理工大學 數學與大數據學院，安徽 淮南 232001）

設G=(V(G)，E(G))是一個圖，V(G)和E(G)分別表示G的頂點集和邊集.圖G的途徑是指一個點邊交替的序列v0e1v1e2v2…vs-1esvs，其中ei=vi-1vi，i∈{1，2…k}.圖G中頂點不重復出現的途徑稱為路.歐拉跡是指圖的一條通過圖中每條邊恰好一次的途徑.如果圖G的邊集E(G)可以分解為若干個邊不相交的路P1…Pt時，則稱圖G有路分解，并稱由這些邊不相交的路構成的集合｛P1…Pt｝為G的一個路分解（簡記為PD）.

Alspach［1］，Bryant［2］分別研究了偶階、奇階完全圖的路分解.Parker［3］，Zhai和Lu?［4］研究了將圖分解為一定長度路的問題.Constantinou和Ellinas［5］研究了完全二部圖的路分解.閆桂英、許保光和吉日木圖［6］研究了3-正則圖的｛P4，P5｝-分解.Haggkvist和Johansson［7］，Thomassen［8］，Heinrich［9］，Tarsi［10］，Pyber［11］，Donald［12］、袁威威［13］、徐禮禮［14］等，主要對路分解的理論分析進行了研究.

1 預備知識

本文考慮的是簡單圖G=(V(G)，E(G))，由n= |V(G)|個頂點和m=|E(G)|條邊組成.設頂點集V(G)={1，2…n}，符號x?y表示連接頂點x和y的（無向）邊.如果x=x'且y=y'，或者x=y'且y=x'，則兩條邊x?y，x'?y'是相同的.稱H是G的子圖，如果V(H)?V(G)且E(H)?E(G).設H1和H2為G的兩個子圖，那么，H1=H2當且僅當V(H)=V(G)且E(H)=E(G)（即對應點的標號也相同）.路矩陣（Path Matrix）用PM表示，這個矩陣的元素是圖G的頂點，因此，元素和頂點這兩個概念在整篇論文中可以互換使用.在PM的第i行和第j列中找到的元素用表示，如果在處是頂點x，則[i][j]=x.

圖G=(V(G)，E(G))是完全二部圖，若其頂點集V(G)存在劃分V1∪V2，且滿足邊集E(G)={x?y：x∈V1，y∈V2}，顯然V1∪V2=V(G)，V1∩V2=?.記n1= |V1|，n2=|V2|，則n1+n2=n.本文中，設n1≥n2，完全二部圖用Kn1，n2表示.根據n1，n2的取值，將完全二部圖進行分類，見表1.

表1 完全二部圖的分類

定理1如果k，n1，n2∈N，其中，n1，n2為偶數且n1≥n2，則Kn1，n2可進行{Pk+1}-分解，當且僅當且n1n2≡0(modk).［15］

推理2一個連通圖有歐拉跡當且僅當它最多有兩個奇點.

算法3Kn1，n2，n1為偶數，1≤n2≤n1-1.（PM是一個具有行2n2+1列的矩陣）

第1步：構建PM的第1行：

●將頂點1…(n2+1)按遞增順序依次放置在奇數列.

●將頂點(n2+1)…n按遞增順序依次放置在偶數列.

第2步：構建PM的行：

●如果屬于奇數列，則在前一行的同一列中找到的元素的基礎上加2；如果結果大于n，則用得到的數減去n1，即為此元的結果.

●如果屬于偶數列，則與前一行的元素相同.

算法4Kn1，n2，n1，n2都為奇數，且n1=n2.（PM是一個具有行+1列的矩陣）

第1步：構建PM的第1行：

●將頂點1…按遞增順序依次放置在奇數列.

●將頂點(n1+)…n按遞增順序依次放置在偶數列.

第2步：構建PM的行：

●對于偶數列，如果結果大于n，則用得到的數減去，即為此元素的結果.

2 主要結論及證明

定理2完全二部圖Kn1，n2可進行{P4，P5}-分解，當且僅當n1，n2滿足以下條件：i.n1≠1；ii.n1=n2≠2.

2.1 情況1證明

根據定理1，當k=4時，如果n1，n2為偶數且n1≥n2，Kn1，n2可進行{P5}-分解當且僅當n1≥3，n2≥2且n1n2≡0(mod4).可以得到當n1=n2為偶數時Kn1，n2可進行{P5}-分解.

2.2 情況2證明

當n2為偶數時，其證明同情況1.

當n2為奇數且n2≠1時，根據算法3可知，完全二部圖Kn1，n2可以分解為條長為2n2的路.只考慮上面分解的一條路，如果一條路滿足{P4，P5}-分解，則整個圖就可進行{P4，P5}-分解.2n2≡2(mod4)，可以說該路分解為一些{P5}和一個{P3}，這個{P3}和與它相鄰的一個{P5}可分解為兩個{P4}，故在該情況下可以分解為兩個{P4}和一些{P5}.

2.3 情況3證明

根據算法4，當n1=n2為奇數時，完全二部圖Kn1，n2可以分解為條長為的路，此處，只考慮Kn1，n2的一條路P，從三個方面討論：

將K5，5的每條路的最后兩條邊取出后可重新組合成一個圈長為10的圈：9?3?8?2?7?1?6?5?10?4?9，該路可分解為兩個{P4}和一個{P5}.故K5，5可分解為一個{P5}和7個{P4}.

綜上所述，情況3可進行{P4，P5}-分解.

2.4 情況4證明

當n2為偶數時，根據推論1，可知Kn1，2（如圖1）有歐拉跡，可將此歐拉跡分解為兩個{P4}和一些{P5}（兩端長為3，中間長為4）.如K7，2有歐拉跡，此跡可分解為以下路：8.

圖1 圖Kn1,2

將Kn1，n2分解為個子圖，滿足以下條件.即（其中.由Kn1，2有歐拉跡，并且可以進行{P4，P5}-分解，故Kn1，n2可進行{P4，P5}-分解.

圖2為K7，4的分解過程：

圖2 K7,4的分解過程

故n2為偶數時可分解為n2個{P4}和一些{P5}.

當n2為奇數時，先考慮Kn1，3，可以得到如下規律（分奇數為一個端點還是偶數為一個端點）.

舉例說明，將上面兩個路矩陣和為一個，即PMn1，3=PMn1，31+PMn1，32.

K7，5就是K7，3+K7，2.依此例推，可得Kn1，n2=Kn1，3+Kn1，2+Kn1，2+….

故，情況4可進行{P4，P5}-分解.

證畢.