圖的控制理論是圖論的重要內容。本書主要介紹圖的控制理論中的一些重要控制參數及其相關的*新研究成果,包括經典控制、條件控制和數值控制(函數類控制)。從一般點控制到一般邊控制,從特殊點控制到特殊邊控制,層次分明,結構安排合理。本書內容豐富、新穎且不乏創新,具有較好的系統性和完備性,這對于豐富和完善圖的控制理論具有一定的科學理論價值,在實際中也具有一定的應用性和趣味性。書中也包含了一些未解決的問題和猜想,可供讀者思考。本書可供離散數學、運籌學、圖論、組合數學、計算機應用等專業的研究生和教師使用,尤其是對從事圖的控制理論方向研究的科技人員,本書具有較大的參考價值。
本書內容豐富、新穎、信息量大,對于豐富和完善圖的控制理具有重要的科學理論價值。方法創新、趣味性強,在實際問題中具有較好的應用前景
近30多年來,隨著計算機信息化技術的飛速發展和人工智能領域研究的不斷進步,數字化和程序化代替了一些人工的思索、設計、運算等操作,這有力地推動了多種學科的快速發展。圖論作為離散數學的一個重要組成部分,也得到了高速度的發展,其應用越來越廣泛。尤其是對離散型結構上的數字化技術問題,導出的許多實際問題數學模型受到人們的廣泛關注,這使得圖論中一些以數字化為特征的內容(包括標號、控制和染色等)成為圖論中發展*快的分支之一。
圖論的起源可追溯到1736年Euler對哥尼斯堡七橋問題的研究,圖的控制也可追溯到1850年。但真正提出圖的控制概念,是C.Berge在1958年的論著,O.Ore在1960年的論文中正式使用了圖的控制數,從這時起直至1994年,圖的控制問題的研究進展是較為緩慢的。在加拿大學者E. J. Cockayne等提出圖的控制函數概念之后,圖的控制理論有了較大的發展,人們從函數角度來認識和理解圖的控制問題,由于函數的定義域和值域以及約束條件的不同而產生了各種各樣的控制概念。1998年美國圖論學者W.T.Haynes等出版了兩部專著《Domination in Graphs》和《Fundamentals of Domination in Graphs》,較為系統地綜述了圖的控制方面的一些主要研究成果,但由于圖的控制概念和控制內容不斷更新,圖的控制理論在內容上不夠完整。近20年來,在計算機的幫助下,圖的標號方法和技術都有了很大的改進和創新,這也使得圖的控制內容越來越豐富,正在形成一套比較完整的理論。
為了不斷豐富和完善圖的控制理論的內容,我已分別于2008年和2013年出版過《圖的控制理論》和《圖的控制與染色理論》,主要是將圖的點控制概念轉向圖上的邊控制(全控制)問題,通過控制函數的變化產生了許多的新控制概念和控制參數。近幾年來,隨著圖的控制中的一些新概念和結果不斷被產生,一些新的問題和猜想不斷提出,使許多圖論學者對圖的標號問題產生了極大的興趣。從函數角度來看,圖的控制與圖的染色一樣,均是研究在一定的約束條件下圖上的整值函數問題,染色參數大多定義為函數值域的*小容量,而控制參數大多為圖上各元素函數值的*小和問題,兩者均屬于圖的標號內容,是圖論中一個比較完整、內容豐富、方法新穎、趣味性強的重要分支。不斷豐富和完善圖的控制理論的內容,正是出版本書的目的之所在。
本書共分為8章,主要是從函數角度來介紹圖的控制概念及其對應的控制參數。第1章介紹圖的經典控制,就是指一般意義上的點控制概念、控制參數及其相關結果。第2章是條件控制,歸納了幾類特殊的點控制概念及相關問題,對其進行介紹。從第3章開始介紹控制函數,從函數角度定義一些控制概念和控制參數,這些以控制函數形式定義的控制概念和控制參數稱為數值控制或許更合適一些。第4章和第5章著重介紹圖的符號控制和減控制的相關內容,這也是圖的控制理論中*先活躍起來的重點內容。前5章屬于圖的點控制,從第6章開始介紹圖的邊控制,這是關于圖的邊控制問題,以圖的符號邊控制與減邊控制為基礎,拓廣到多種特殊的邊控制。第6章主要介紹圖的符號邊控制,這也是推廣邊控制形式的*先研究的重點內容;第7章介紹減邊控制與羅馬邊控制及其變化形式;第8章是對符號邊控制的一些變化進行探討和研究。書中內容豐富,所涉及的控制參數較多,也提出或列出了不少的未解決問題和猜想,其中有不少趣味性的問題,意在拋磚引玉,并希望得到讀者的建議和指導,這也是筆者的*大愿望。
本書在章節和內容的編排上,盡可能做到層次分明。例如,前2章是一般點控制(經典控制與條件控制),后6章則屬于函數類控制(或者稱為數值控制);前5章是點控制,而后3章屬于邊控制。同時注意各類型的控制概念及參數之間自然過渡。書中未證明的結論均列出了對應的參考文獻,這樣既可滿足讀者的不同要求,又不影響可讀性。
對于運籌學與控制論專業(圖論方向)的研究生,或者從事圖的控制理論研究的科研人員來說,本書或許是一本好的參考資料,至少為相關科技人員提供了較為完整的圖的控制概念及相關結果,具有較大的參考價值。
本書是在多項基金項目的共同資助下出版的,包括國家自然科學基金項目(11961026、11861032、11361024、11261018)、江西省自然科學基金項目(20171B AB201009、20181BAB201002)、江西省高校科技落地計劃項目( KJLD12067),在寫作過程中得到了李春華、王廣富、朱旭生、詹小秦等老師的大力幫助,也得到了張君霞、李廣、蘭婷、鄭萌萌等碩士研究生的協助,此外,徐彤同志認真、仔細地校對了全稿,在此一并深表謝意。
由于作者水平有限,書中一定有不少不足之處,敬請讀者批評指正。
徐保根,男,1963年10月生,教授,碩士生導師,1989年四川大學數學系研究生畢業,組合數學專業。先后評為江西省中青年學科帶頭人、江西省教學名師、江西省新世紀百千萬人才、江西省模范教師、享受省政府特殊津貼、江西省二級教授、華東交大學術委員會委員、華東交大首席教授,華東交大重點學科《數學》學科帶頭人。主持過三項國家自然科學基金項目、四項江西省自然科學基金項目、四項江西省教育廳科研課題和一項江西省高校科技落地計劃項目。另外還參研過二十余項省部級以上的課題的研究,主持的《運籌學與控制論》被列為江西省重點學科,主持的〈圖的控制理論研究〉獲江西省自然科學獎,主持或參研的教改課題多次獲得省教學成果獎。先后在國內外期刊上發表學術論文一百八十余篇,其中的二十多篇論文發表在《Discrete Math.》、《Discrete Appl. Math.》、《Ars Combinatoria.》等國際核心專業期刊上,均被SCI檢索。出版過兩部學術專著和兩部教材。這些論著解決了圖論中一些重要的極圖結構問題,也解決了國內外著名專家提出的若干問題和猜想,首次提出并研究了圖的邊控制、全控制以及多種各樣的特殊控制,形成了一套較為系統的控制理論。
第1章經典控制(1)
1.1圖的點控制概念(1)
1.2控制參數的界限(4)
1.3控制相關參數(15)
1.4積圖的控制數(22)
1.5圖的全控制(28)
1.6控制集劃分(35)
1.7控制臨界性參數(42)
第2章條件控制(46)
2.1連通控制(46)
2.2獨立控制(51)
2.3距離控制(56)
2.4球形(因子)控制(62)
2.5配對控制(66)
2.6強(弱)控制(70)
2.7混合控制(75)
2.8[1,2]控制(77)
2.9k控制(84)
2.10定位控制(87)
第3章幾類特殊控制函數(92)
3.1控制函數的概念(92)
3.2Fractional控制(94)
3.3Fractional全控制(99)
3.4k權控制(102)
3.5羅馬控制(106)
3.6強(弱)羅馬控制(111)
3.7彩虹控制(117)
第4章符號控制(123)
4.1符號(點)控制(123)
4.2符號全控制(134)
4.3符號控制劃分(138)
4.4上符號(全)控制(142)
4.5k符號控制(146)
4.6團符號控制(150)
4.7圈符號控制(153)
4.8羅馬符號(全)控制(158)
第5章減控制(163)
5.1一般減控制(163)
5.2減全控制(165)
5.3k減控制(169)
5.4k減全控制(173)
5.5上減(全)控制(174)
第6章符號邊控制(178)
6.1一般邊控制(178)
6.2符號邊控制(182)
6.3k符號邊控制(188)
6.4符號邊全控制(191)
6.5k符號邊全控制(194)
6.6符號邊控制劃分(196)
第7章減邊控制與羅馬邊控制(199)
7.1減邊控制(199)
7.2減邊全控制(203)
7.3羅馬邊控制(207)
7.4符號羅馬邊控制(208)
7.5符號全羅馬邊控制(211)
第8章符號邊控制的變化(214)
8.1符號圈控制(214)
8.2符號團控制(218)
8.3符號星控制(223)
8.4符號星控制劃分(227)
8.5符號星k控制(230)
附錄符號與術語對照表(234)
參考文獻(237)