平面圖和線圖上的彩虹連通性研究.pdf

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

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

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

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

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

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