圖的控制與染色理論主要介紹圖的控制理論與染色理論中的一些重要內(nèi)容和最新研究成果。從一般點(diǎn)控制到特殊點(diǎn)控制,從一般邊控制到特殊邊控制,從一般染色到特殊染色,層次分明,結(jié)構(gòu)安排合理。本書(shū)內(nèi)容豐富、新穎,系統(tǒng)性強(qiáng),方法具體且不乏創(chuàng)新之處,書(shū)中涉及的許多內(nèi)容、問(wèn)題和猜想在理論上均具有較強(qiáng)的完備性,在實(shí)際工作中也具有一定的應(yīng)用性和趣味性。
《圖的控制與染色理論》可供離散數(shù)學(xué)、運(yùn)籌學(xué)、圖論、組合數(shù)學(xué)、計(jì)算機(jī)應(yīng)用等專業(yè)的研究生和教師使用,尤其是對(duì)從事圖的控制理論與染色理論方向研究的科技人員,本書(shū)具有較強(qiáng)的理論價(jià)值。
本書(shū)主要介紹圖的控制理論與染色理論中的一些重要內(nèi)容和最新研究成果。主要內(nèi)容包括:圖的一般點(diǎn)控制、特殊的點(diǎn)控制、符號(hào)控制與減控制等。
近二十多年來(lái),隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展,信息化和數(shù)字化技術(shù)的不斷進(jìn)步,許多實(shí)際問(wèn)題的數(shù)學(xué)模型使離散型結(jié)構(gòu)上的數(shù)字化技術(shù)得到了人們更多的關(guān)注,圖論作為離散數(shù)學(xué)的一個(gè)重要組成部分,自然得到了高速發(fā)展,而且其應(yīng)用也越來(lái)越廣泛。事實(shí)上,圖論為任何一個(gè)包含一種二元關(guān)系的系統(tǒng)提供了一個(gè)數(shù)學(xué)模型。這也許使得圖的標(biāo)號(hào)理論(包括圖的標(biāo)號(hào)、控制和染色等)成為圖論中發(fā)展最快的分支之一。
在數(shù)學(xué)的眾多分支中,圖論不像代數(shù)、拓?fù)涞葘W(xué)科一樣,具有一套完整的數(shù)學(xué)理論。1998年美國(guó)圖論學(xué)者W.T.Haynes等人出版了兩部專著《Dominationin Graphs》和《Fundamentalsof Dominationin Graphs》,較為系統(tǒng)地綜述了控制方面的一些主要研究成果。值得注意的是,幾乎所有的概念和結(jié)果都是針對(duì)圖的點(diǎn)控制而言,很少涉及圖的邊控制問(wèn)題,使得控制理論從內(nèi)容上不夠完整。不過(guò)近十多年來(lái),在計(jì)算機(jī)的幫助下,圖的標(biāo)號(hào)方法和技術(shù)都有了很大的改進(jìn)和創(chuàng)新,圖論中一些以數(shù)字化為特征的內(nèi)容(如圖的標(biāo)號(hào)、控制和染色等)得到了更快的發(fā)展。這也使得其內(nèi)容越來(lái)越豐富,它或許正在形成一套比較完整的理論。
為了豐富和完善圖的控制理論的內(nèi)容,作者已于2008年出版過(guò)《圖的控制理論》一書(shū),主要是將圖的點(diǎn)控制概念轉(zhuǎn)向圖上的邊控制問(wèn)題,從而產(chǎn)生了許多新概念和新內(nèi)容。近幾年來(lái),隨著圖的控制與染色中的一些新概念和結(jié)果不斷產(chǎn)生,一些新的問(wèn)題和猜想不斷被提出,許多圖論學(xué)者對(duì)圖的標(biāo)號(hào)產(chǎn)生了極大的興趣。當(dāng)然,圖的標(biāo)號(hào)本來(lái)也不是獨(dú)立的,它滲透到圖論中的眾多分支,如圖的因子分解、圖的拼裝等。可以預(yù)見(jiàn),在不遠(yuǎn)的將來(lái),圖的標(biāo)號(hào)(包括控制、染色)會(huì)更加受到人們的關(guān)注和重視,產(chǎn)生更加豐富的研究成果,使圖的控制與染色成為圖論中一個(gè)結(jié)構(gòu)比較完整、內(nèi)容豐富、方法新穎、趣味性強(qiáng)的重要分支,逐步豐富和完善圖的控制與染色方面的內(nèi)容,這正是作者出版本書(shū)的目的之所在。
本書(shū)共分為8章,主要包括圖的控制和染色兩方面。第1、2章介紹圖的一般點(diǎn)控制和一些特殊的點(diǎn)控制,其中涉及多種控制參數(shù),也包括控制集的劃分等問(wèn)題。第3、4章著重介紹圖的符號(hào)控制與減控制,并在此基礎(chǔ)上產(chǎn)生了多種變形。前4章均是介紹圖的點(diǎn)控制。第5、6章是關(guān)于圖的邊控制問(wèn)題,以圖的符號(hào)邊控制與減邊控制為基礎(chǔ),拓廣到多種特殊的邊控制。第7章介紹圖的正常著色及Ramsey數(shù),即傳統(tǒng)意義下的點(diǎn)、邊、全染色,并介紹了三種類型的Ramsey數(shù)。第8章中作者選取幾類特殊著色進(jìn)行了介紹。
本書(shū)在內(nèi)容的編排上,盡可能由一般到特殊、由易到難。書(shū)中未證明的結(jié)論均列出了對(duì)應(yīng)的參考文獻(xiàn),這樣既可滿足讀者的不同要求,又不影響可讀性。書(shū)中提出或列出了不少未解決的問(wèn)題和猜想,也有不少趣味性的問(wèn)題,其意在拋磚引玉,并期望能吸引讀者的目光,這是筆者的最大愿望。
對(duì)于圖論專業(yè)(尤其是控制論或染色方向的)的研究生,或者從事圖的控制與染色的科研人員來(lái)說(shuō),本書(shū)或許是一本好的參考資料,尤其是在目前國(guó)內(nèi)還沒(méi)有一部關(guān)于圖的控制或染色的專著情況下,該書(shū)具有較好的參考價(jià)值。
本書(shū)是在多項(xiàng)基金項(xiàng)目的共同資助下出版的,包括國(guó)家自然科學(xué)基金項(xiàng)目(11061014、11361024、11261019)、江西省自然科學(xué)基金(20114BAB201010)、江西省高校科技落地計(jì)劃項(xiàng)目(KJLD12067)和江西省教育廳科研課題(GJJ12295)。在寫(xiě)作過(guò)程中,上海大學(xué)單而芳教授為作者提供了寶貴的資料,本書(shū)的編寫(xiě)還得到了李春華、范自柱、王廣富等多位老師的大力幫助,也得到了丁宗鵬、操葉龍、康洪波、趙利芬等多位碩士研究生的協(xié)助,此外,徐彤同志認(rèn)真、仔細(xì)地校對(duì)了全稿,在此一并深表謝意。
第1 章圖的一般點(diǎn)控制
1.1 圖的點(diǎn)控制概念
1.2 圖的控制數(shù)界限
1.3 控制相關(guān)概念及參數(shù)
1.4 乘積圖的控制數(shù)
1.5 控制數(shù)臨界圖
1.6 集控制與全集控制
1.7 反集控制與補(bǔ)集控制
1.8 Bondage數(shù)與Reinforcement數(shù)
第2 章特殊的點(diǎn)控制
2.1 Fractional控制
2.2 全控制與F?全控制
2.3 k權(quán)控制相關(guān)參數(shù)
2.4 連通控制與獨(dú)立控制
2.5 距離控制
2.6 強(qiáng)控制與弱控制
2.7 混合控制
2.8 配對(duì)控制
第3 章符號(hào)控制與減控制
3.1 圖的符號(hào)控制
3.2 圖的主控制數(shù)
3.3 k符號(hào)控制
3.4 圖的減控制
3.5 k減控制
第4 章特殊符號(hào)減控制
4.1 圖的符號(hào)全控制
4.2 圖的減全控制
4.3 上符號(hào)全控制
4.4 上減全控制
4.5 團(tuán)符號(hào)控制
4.6 圈符號(hào)控制
4.7 圖的反符號(hào)控制
第5 章符號(hào)邊控制與減邊控制
5.1 一般邊控制
5.2 符號(hào)邊控制
5.3 k符號(hào)邊控制
5.4 符號(hào)邊全控制
5.5 k符號(hào)邊全控制
5.6 減邊控制
5.7 減邊全控制
第6 章符號(hào)邊控制的變形
6.1 符號(hào)圈控制
6.2 符號(hào)團(tuán)控制
6.3 符號(hào)星控制
6.4 符號(hào)星k控制
6.5 符號(hào)路控制
6.6 符號(hào)樹(shù)控制
6.7 符號(hào)控制概念的延伸
第7 章染色與Ramsey數(shù)
7.1 圖的邊著色
7.2 圖的點(diǎn)著色
7.3 圖的全著色
7.4 經(jīng)典Ramsey數(shù)
7.5 廣義Ramsey數(shù)
7.6 混合Ramsey數(shù)
第8 章特殊著色
8.1 圖的反著色
8.2 一種廣義著色
8.3 圖的IC著色
8.4 圖的局部著色
8.5 圖的Grundy著色
8.6 點(diǎn)區(qū)別邊著色
8.7 點(diǎn)區(qū)別全著色
附錄 符號(hào)與術(shù)語(yǔ)對(duì)照表
參考文獻(xiàn)