代數圖論

代數圖論

代數圖論是數學中離散數學的一個分支,主要是應用代數方法解決圖論問題,而不是幾何、組合或算術方法。其主要有三個分支,分別是線性代數方法、群論方法和圖不變數方法。

進展


圖的minor理論是近代圖論研究的中心問題之一。在我國很少有這方面的研究成果。國際上, 洪淵等人首先研究了圖的minor與圖的特徵值之間的關係。其中,圖的樹寬度又是圖的minor理論中的一個重要參數。他們給出了樹寬度不大於k的所有圖其譜半徑的可達上界和達到上界的極圖。同時對樹寬度不大於k的所有圖得到最小特徵值的可達上界和達到上界的極圖。另外,對於禁用K5–minor圖給出了其譜半徑的可達上界和達到上界的極圖。同時對禁用K5–minor圖得到了其最小特徵值的可達下界和達到下界的極圖。而對於t=n,n-1,n-2的禁用Kt–minor圖給出了其譜半徑的可達上界和達到上界的極圖。
在研究了譜圖理論及應用方面,張曉東李炯生討論了混合圖的性質和圖的拉普拉斯的矩陣的最大特徵值的上界的估計,並刻畫了達到上界的所有的圖類。他們把圖的拉普拉斯矩陣的研究推廣到新的領域。在完全正則圖的分解指數方向,解決了Berman和Kogan的關於完全正則圖的問題。整圖是指該圖的Laplace特徵值或鄰接特徵值都是整數;這類圖的拓撲結構和它們的特徵值存在著一些有趣的聯繫。遠在1970年代,Harary和Schwenk提出研究整圖的問題。但至今,這個問題仍沒有完全解決。范益政和李炯生提出了新概念譜整性變化。譜整性變化是圖的譜擾動的一種情形。它的提出為了解圖的譜擾動,特別是構造整圖提供了新的方法和視角。此後,他們用這種方法還討論了度極大圖,具有少數匹配數的樹,以及混合圖的譜擾動。另外,李炯生等人研究了經典Turan數t(Kr,r,n)在可圖序列中的變形,確定了t(Kr,r,n)的度序列形式的極值å(Kr,r,n),為研究極值圖論的經典結果在可圖序列中的變形問題提供了一個範例和研究方法。
張福基等人研究了譜半徑小於 (圖譜半徑在實軸上的最小聚點)的連通圖依譜半徑大小的排序。他們首次引進了漸近序的概念,證明了所考慮的圖類只存在漸進序。同時解決了一個無窮圖類依譜半徑排序的問題。他們還進而還考慮了上述結果在化學中的應用。另外,洪淵等人研究了如何用圖的度序列確定圖的Laplace譜半徑的可達上界和達到上界的極圖。
方新貴、王傑和徐明耀對於有限單群Cayley圖的全自同構群的結構給予了刻畫,證明了圖的全自同構群或是幾乎單的或有著極強的限制性結構。作為一個應用,他們還得到了一個有限單群Cayley圖正規性的充分條件,並由此構造出了若干新的半傳遞圖,其中兩個圖的無限族具有任意大的度數。另外他們還得到一個充分條件以使的有限非交換單群的Cayley圖是弧正則的。據此他們構造了兩個3度弧正則圖的無限族使其全自同構群是非可解的,且其中一個無限族不是Cayley圖。同時他們還證明了對大多數有限非交換單群決定的3度Cayley圖均是正規的,並將此結果應用於群的圖正則表示和3-CI性的刻畫

推薦書籍


代數圖論
代數圖論
書名:代數圖論 圖書編號:1014024
定價:65.0
ISBN:750626618
作者:Chris Godsil
出版日期:2004-04-01
版次:1
開本:橫24開
簡介:本書以英文的形式介紹了代數圖論的有關內容。
目錄:Preface
1 Graphs
1.1 Graphs
1.2 Subgraphs
1.3 Automorphisms
1.4 Homomorphisms
1.5 Circulant Graphs
1.6 Johnson Graphs
1.7 Line Graphs
1.8 Planar Graphs
Exercises
Notes
References
2 Groups
2.1 Permutation Groups
2.2 Counting
2.3 Asymmetric Graphs
2.4 Orbits on Pairs
2.5 Primitivity
2.6 Primitivity and Connectivity
Exercises
Notes
References
3 Transitive Graphs
4 Arc-Transitive Graphs
5 Generalized Polygons and Moore Graphs
6 Homomorphisms
7 Kneser Graphs
8 Matrix Theory
9 Interlacing
10 Strongly Regular Graphs
11 Two-Graphs
12 Line Graphs and Eigenvalues
13 The Laplacian of a Graph
14 Cuts and Flows
15 The Rank Polynomial
16 Konts
17 Knots and Eulerial Cycles
Glossary of Symbols
Index