平面圖和線(xiàn)圖上的彩虹連通性研究.pdf

1、假設(shè)在一個(gè)蜂窩網(wǎng)絡(luò)中，人們希望能在任意兩個(gè)頂點(diǎn)之間傳送信息，并且要求該線(xiàn)路上的每條邊被分配不同的信道。那么，在滿(mǎn)足上述要求的前提下，最少需要使用多少不同信道才能保證網(wǎng)絡(luò)中任意兩點(diǎn)之間能夠傳送信息？將該網(wǎng)絡(luò)抽象成一個(gè)圖，研究證明這個(gè)最小值就是該圖的彩虹連通數(shù)。彩虹連通的概念由Chartrand等人于2008年提出。
　　設(shè)G為一個(gè)非平凡的連通圖。定義圖G上的一個(gè)邊染色c∶E(G)→C，其中C={1，2，…，k}，k∈N，表示k種不同

2、顏色的集合，邊染色c允許圖G中相鄰的邊染同種顏色。圖G的一條路是彩虹的，如果該路上每條邊的顏色不同。給定圖G的一個(gè)邊染色，如果任意兩個(gè)頂點(diǎn)之間存在一條彩虹路，則稱(chēng)圖G在該染色下是彩虹連通的。同時(shí)稱(chēng)該邊染色為彩虹染色。使得圖G彩虹連通所需的最少顏色數(shù)稱(chēng)為彩虹連通數(shù)，記為rc(G)。
　　在頂點(diǎn)染色圖G中，如果一條路的內(nèi)部頂點(diǎn)染的顏色都不相同，那么稱(chēng)該路是彩虹的。頂點(diǎn)染色圖G是彩虹頂點(diǎn)連通的，如果任意兩個(gè)不同頂點(diǎn)之間至少有一條彩虹路。

3、這樣的頂點(diǎn)染色稱(chēng)為彩虹頂點(diǎn)染色。連通圖G的彩虹頂點(diǎn)連通數(shù)，記為rvc(G)，是使得圖G彩虹頂點(diǎn)連通所需的最少顏色數(shù)。彩虹頂點(diǎn)連通的概念首次由Krivelevich和Yuster提出。
　　本文首先從算法復(fù)雜性的角度對(duì)彩虹（頂點(diǎn)）連通性進(jìn)行了研究。對(duì)于一般圖，Chakraborty等人證明了對(duì)于給定的邊著色圖（顏色數(shù)是任意的）判定該圖是否彩虹連通是NP-完全的。對(duì)于特殊圖類(lèi)，給定一個(gè)邊著色圖G（顏色數(shù)是任意的）判定圖G在該染色下是否

4、彩虹連通，確定這個(gè)問(wèn)題的復(fù)雜類(lèi)別是很有意義的。事實(shí)上，特殊圖類(lèi)的復(fù)雜性研究能更好地幫助我們從算法的角度理解彩虹連通性。受此啟發(fā)，我們研究了上述判定問(wèn)題在平面圖，以及平面二部圖上的復(fù)雜性，證明了給定一個(gè)邊染色平面圖G，判定圖G在該染色下是否彩虹連通是NP-完全的。更進(jìn)一步地，我們證明了給定一個(gè)邊染色平面二部圖G，判定圖G在該染色下是否彩虹連通仍然是NP-完全的。
　　對(duì)于彩虹頂點(diǎn)連通性的復(fù)雜性問(wèn)題，本文研究了如下判定問(wèn)題:給定一個(gè)頂

5、點(diǎn)染色線(xiàn)圖，判定該圖是否頂點(diǎn)彩虹連通。我們證明了該判定問(wèn)題是NP-完全的。相對(duì)于目前已有的結(jié)果，我們的結(jié)論則更強(qiáng)。
　　其次，本文研究了平面圖的彩虹連通數(shù)的上界問(wèn)題。作為圖論中一個(gè)相當(dāng)大的圖類(lèi)，平面圖的彩虹連通數(shù)的上界研究還是空白。一個(gè)自然的問(wèn)題就是:給定一個(gè)平面圖G，確定rc(G)的上界。我們給出了無(wú)橋平面圖的彩虹連通數(shù)的上界，具體地，當(dāng)直徑為2時(shí)，無(wú)橋外平面圖G的彩虹連通數(shù)滿(mǎn)足2≤rc(G)≤3，并且上界是緊的;當(dāng)直徑為3時(shí)，

6、無(wú)橋外平面圖G的彩虹連通數(shù)滿(mǎn)足3≤rc(G)≤6。因此這個(gè)結(jié)果部分地回答了上述問(wèn)題。
　　本文由四部分組成。在第一章中我們首先介紹了彩虹（頂點(diǎn)）連通的背景，一些術(shù)語(yǔ)和概念，其次概述了相關(guān)的結(jié)果以及本文的主要結(jié)論。
　　在第二章中我們證明了:給定一個(gè)邊染色平面圖G，判定圖G在該染色下是否彩虹連通是NP-完全的。更進(jìn)一步地，我們證明了:給定一個(gè)邊染色平面二部圖G，判定圖G在該染色下是否彩虹連通是NP-完全的。
　　在第三章