有向圖的圈分解.pdf

1、圖的圈分解問(wèn)題是圖論和設(shè)計(jì)理論研究中的重要課題．自1847年，Kirkmarn確定了K<,n>的3圈分解及1892年Lucas確認(rèn)Walecki解決了K<,n>的n圈分解以來(lái)，國(guó)內(nèi)外許多學(xué)者對(duì)完全圖的圈分解問(wèn)題作了大量的研究，并取得了許多優(yōu)美的結(jié)果，也有一些文獻(xiàn)［20， 53，54，56，57，58，59，60，61，62，63，64，65，66］涉及到完全有向圖的圈分解問(wèn)題。 本文的第二章主要研究了最大填充Mendelsoh

2、n三元系，在§2.4中，推廣了Colbourn和Rosa［68，70］的定理，主要研究了D<,n>-P和D<,n>uP的有向3圈(Mendelsohn三元系)分解，它不僅具有理論意義，而且在計(jì)算機(jī)網(wǎng)絡(luò)設(shè)計(jì)中有一定的現(xiàn)實(shí)意義。通過(guò)利用差，Langford序列，hooked Langford序列等組合論工具，證明了當(dāng)n≥13，D<,n>為n階完全有向圖， P為D<,n>中頂點(diǎn)不相交的有向圈的并時(shí)，D<,n>-P或D<,n>uP可分解為有向3

3、圈(即Mendelsohn三元系)的充分必要條件為D<,n>-P或D<,n>uP的邊數(shù)可被3整除。在D〈，n〉不考慮方向時(shí)即成為2K〈，n〉作為以上內(nèi)容的直接推論可得以下定理：當(dāng)n≥13時(shí)，2K〈，n〉-P或2K〈，n〉u P可分解為3圈的充分必要條件為2K〈，n〉-P或2K〈，n〉u P的邊數(shù)可被3整除． 如果圖G不存在3圈分解，我們可考慮其子圖H．如果子圖H存在3圈分解，則稱(chēng)G可被3圈填充，G-H稱(chēng)為該填充的剩余，在G的所

4、有可能剩余中，邊數(shù)最少的剩余稱(chēng)為是最小剩余，最小剩余所對(duì)應(yīng)的填充稱(chēng)為最大填充．如果圖G不存在3圈分解，我們也可以通過(guò)多次使用某些邊，而得到圖的3圈分解。圖G的3圈覆蓋為三角形(亦稱(chēng)3圈)的集合P，使得G中的每一條邊至少出現(xiàn)在P的一個(gè)三角形中，因此可構(gòu)造多圖G(P)，使得G(P)中的點(diǎn)u和v之間有x條邊聯(lián)接的充分必要條件是P中有x個(gè)三角形包含點(diǎn)u和v，顯然，G(P)存在3圈分解．G(P)-G稱(chēng)為該覆蓋的冗余，在G的所有可能的冗余中，邊數(shù)最

5、少的冗余，稱(chēng)為最小冗余．最小冗余所對(duì)應(yīng)的覆蓋稱(chēng)為最小覆蓋．在§2.5中，推廣了§2.4中的結(jié)論，研究了D<,n>-P和D<,n>u P的最大填充Mendelsohn三元系．證明了當(dāng)n≥13，P為D<,n>中頂點(diǎn)不相交的有向圈的并時(shí)，D<,n>—P或D<,n>VP可分解為向3圈(或Mendelsohn三元系)和剩余L<'I>的充分必要條件是D<,n>-P>或D<,n>VP的邊數(shù)為模3余I，其中I=0,1,2；Lo為空集，L<,1>為有向4

6、圈(或頂點(diǎn)不相交的兩個(gè)有向2圈的并)，L<,2>為有向2圈.§2.4中的結(jié)論即為I=0的情況． 本文的第三章利用數(shù)學(xué)歸納法和直接構(gòu)造法，研究了D<,>-P和D<,n>uP的有向4圈分解，證明了當(dāng)n≥8,P為D<,n>中頂點(diǎn)不相交的有向圈的并時(shí)，D<,n>-P或D<,n>uP可分解為有向4圈的充分必要條件是D<,n>-P或D<,n>uP邊數(shù)可被4整除。集合T的元素為圖G中邊不相交的Hamilton圈，T稱(chēng)為最大Hamilton圈

7、集，簡(jiǎn)稱(chēng)最大集，如果T中所有Hamilton圈滿足G-E(T)不含Hamilton圈，E(T)為T(mén)中所有Hamilton圈的邊所組成的集合．圖G的譜為整數(shù)|T|的范圍．本文的第四章研究了完全有向圖D<,n>的最大Hamilton圈集．證明了D<,n>中存在含有m個(gè)有向Hamilton圈的最大集T的充分必要條件為:||≤m ≤ n-1． 本文的第五章研究Dｎ，ｎ＋Ｐ的有向ｍ圈分解，證明了當(dāng)ｍ為偶數(shù)，ｎ為奇數(shù)且4≤ｍ≤2ｎ，ｐ為D