完全二部圖定長的路分解

柴 惠，房明磊

（安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001）

設(shè)G=(V(G)，E(G))是一個圖，V(G)和E(G)分別表示G的頂點(diǎn)集和邊集.圖G的途徑是指一個點(diǎn)邊交替的序列v0e1v1e2v2…vs-1esvs，其中ei=vi-1vi，i∈{1，2…k}.圖G中頂點(diǎn)不重復(fù)出現(xiàn)的途徑稱為路.歐拉跡是指圖的一條通過圖中每條邊恰好一次的途徑.如果圖G的邊集E(G)可以分解為若干個邊不相交的路P1…Pt時，則稱圖G有路分解，并稱由這些邊不相交的路構(gòu)成的集合｛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］等，主要對路分解的理論分析進(jìn)行了研究.

1 預(yù)備知識

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

圖G=(V(G)，E(G))是完全二部圖，若其頂點(diǎn)集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.本文中，設(shè)n1≥n2，完全二部圖用Kn1，n2表示.根據(jù)n1，n2的取值，將完全二部圖進(jìn)行分類，見表1.

表1 完全二部圖的分類

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

推理2一個連通圖有歐拉跡當(dāng)且僅當(dāng)它最多有兩個奇點(diǎn).

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

第1步：構(gòu)建PM的第1行：

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

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

第2步：構(gòu)建PM的行：

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

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

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

第1步：構(gòu)建PM的第1行：

●將頂點(diǎn)1…按遞增順序依次放置在奇數(shù)列.

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

第2步：構(gòu)建PM的行：

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

2 主要結(jié)論及證明

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

2.1 情況1證明

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

2.2 情況2證明

當(dāng)n2為偶數(shù)時，其證明同情況1.

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

2.3 情況3證明

根據(jù)算法4，當(dāng)n1=n2為奇數(shù)時，完全二部圖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可進(jìn)行{P4，P5}-分解.

2.4 情況4證明

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

圖1 圖Kn1,2

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

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

圖2 K7,4的分解過程

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

當(dāng)n2為奇數(shù)時，先考慮Kn1，3，可以得到如下規(guī)律（分奇數(shù)為一個端點(diǎn)還是偶數(shù)為一個端點(diǎn)）.

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

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

故，情況4可進(jìn)行{P4，P5}-分解.

證畢.