有向圖的圈分解.pdf

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

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

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

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

5、少的冗余，稱為最小冗余．最小冗余所對應(yīng)的覆蓋稱為最小覆蓋．在§2.5中，推廣了§2.4中的結(jié)論，研究了D<,n>-P和D<,n>u P的最大填充Mendelsohn三元系．證明了當n≥13，P為D<,n>中頂點不相交的有向圈的并時，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、圈(或頂點不相交的兩個有向2圈的并)，L<,2>為有向2圈.§2.4中的結(jié)論即為I=0的情況． 本文的第三章利用數(shù)學歸納法和直接構(gòu)造法，研究了D<,>-P和D<,n>uP的有向4圈分解，證明了當n≥8,P為D<,n>中頂點不相交的有向圈的并時，D<,n>-P或D<,n>uP可分解為有向4圈的充分必要條件是D<,n>-P或D<,n>uP邊數(shù)可被4整除。集合T的元素為圖G中邊不相交的Hamilton圈，T稱為最大Hamilton圈

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