圖的單色及雜色子圖劃分的復(fù)雜性.pdf

1、一個邊染色圖稱為單色的，如果它的所有邊都有相同的顏色，而一個邊染色圖稱為雜色的，如果它的任意兩條邊的顏色均不相同。一個r-邊染色圖G的單色樹分解數(shù)定義為最小的整數(shù)k，使得只要用r種顏色對圖G的邊進(jìn)行染色，都存在k個點(diǎn)不交的單色樹覆蓋圖G的所有頂點(diǎn)。r-邊染色圖G的單色圈分解數(shù)和單色路分解數(shù)可以同樣的方法定義。 本文分為兩部分，第一部分主要考慮邊染色圖的單色子圖劃分問題，第二部分主要考慮邊染色圖的雜色子圖劃分問題。 第一部

2、分由第二和第三章組成。第二章我們考慮如下優(yōu)化問題：給定一個r-邊染色圖G，求最少個數(shù)的頂點(diǎn)不交的單色樹、圈或路，覆蓋圖G的所有頂點(diǎn)(文中分別簡稱為PGMT、PGMC和PGMP問題)。對于這三個問題我們有如下結(jié)果： 1.PGMT問題是一個NP-完備問題，并且不存在常數(shù)因子的近似算法，除非P=NP。實(shí)際上，我們證明了：對于二部圖，PGMT問題仍然是一個NP-完備問題。 2.PGMC問題是一個NP-完備問題，并且不存在常數(shù)因子

3、的近似算法，除非P=NP。 3.PGMP問題是一個NP-完備問題，并且不存在常數(shù)因子的近似算法，除非P=NP。 若r為一個固定的整數(shù)，我們把r邊染色圖的PGMT、PGMC和PGMP問題分別稱為r-PGMT、r-PGMC和r-PGMP問題.對單色子圖分解的問題有如下了更強(qiáng)的NP-完備性結(jié)果。 4.對于任何固定的整數(shù)r≥5，r-PGMT問題是一個NP-完備問題。 5.對于任何固定的整數(shù)r≥5，r-PGMC問題

4、是一個NP-完備問題。 6.對于任何固定的整數(shù)r≥5，r-PGMP問題是一個NP-完備問題。 第三章主要考慮2-邊染色的完全多部圖中單色子圖劃分問題，有如下的結(jié)果。 7.對于完全多部圖，2-PGMP問題仍然是NP-完備問題。因此，2-PGMP問題是NP-完備問題。 8.對于完全多部圖，2-PGMC問題仍然是NP-完備問題。因此，2-PGMC問題是NP-完備問題。 9.對于完全多部圖，2-PGMT問

5、題是一個P-問題，即可以在多項(xiàng)式時(shí)間內(nèi)求解。 根據(jù)結(jié)論9的證明，我們不僅可以在多項(xiàng)式時(shí)間內(nèi)找到2-邊染色完全多部圖的一個最優(yōu)單色樹分解，而且可以給出它的單色樹分解數(shù)的顯性表達(dá)式(首先由Kaneko，Kano和Suzuki[30]證明)的一個更自然的證明。 第二部分由第四和第五章組成。首先，對應(yīng)于單色樹、圈、路分解數(shù)的概念我們引入r-邊染色圖G的雜色樹、圈、路分解數(shù)的概念，定義為最小的整數(shù)k，使得只要用r種顏色對圖G的邊進(jìn)

6、行染色，都存在k個頂點(diǎn)不交的雜色樹、圈、路覆蓋圖G的所有頂點(diǎn)。 第四章主要考慮邊染色完全多部圖的雜色樹分解數(shù)問題。Kaneko，Kano和Suzuki[30]對r-邊染色完全多部圖的單色樹分解數(shù)僅僅解決了r=2的特殊情形，而我們對一般的整數(shù)r徹底解決了r-邊染色完全多部圖的雜色樹分解數(shù)問題。盡管我們沒有能夠給出其顯性表達(dá)式，我們構(gòu)造了兩種典型r-邊染色，據(jù)此 10.我們可以在多項(xiàng)式時(shí)間內(nèi)求出r-邊染色完全多部圖的雜色樹分

7、解數(shù)的值。作為推論，完全圖和完全二部圖的雜色樹分解數(shù)則可以給出顯性表達(dá)式。 類似單色子圖劃分的情形，第五章我們考慮如下優(yōu)化問題：給定一個r-邊染色圖G，求最少個數(shù)的頂點(diǎn)不交的雜色樹、圈或路，覆蓋圖G的所有頂點(diǎn)。我們分別稱之為Minimumheterochromatictree，cycleandpathpartition問題。我們證明如下結(jié)果。 11.Minimumheterochromatictree(cycle)par

8、tition問題為NP-完備問題，并且不存在常因子的近似算法，除非P=NP。實(shí)際上，我們證明了：對于二部圖，Minimumheterochromatictreepartition問題仍然是NP-完備的。 12.對于2-邊染色圖，Minimumheterochromaticpathpartition問題為NP-完備問題；因此，對于一般圖Minimumheterochromaticpathpartition問題為NP-完備問題.由此