圖的斜譜和匹配根的若干結(jié)果.pdf

1、令Gσ是簡單無向圖G的一個定向圖，它具有頂點集V={v1,…,vn}和弧集Γ。定向圖Gσ的斜鄰接矩陣定義為一個n×n矩陣S(Gσ)=(sij)，其中sij=1且sji=-1如果〈vi,vj〉∈Γ，否則sij=sji=0。斜鄰接矩陣的所有特征根稱為定向圖的斜譜。定向圖的斜譜半徑定義為它的斜鄰接矩陣的所有特征根的模的最大值。
　　斜鄰接矩陣最早是由Tutte于1947年提出來的，Tutte利用斜鄰接矩陣給出了一個圖是否有完美匹配的判定

2、條件。在1961年，物理學家Fisher，Kasteleyn和Temperley利用矩陣的行列式和Pfaffian給出了平面矩形網(wǎng)格的完美匹配的計數(shù)。他們發(fā)現(xiàn)：如果一個圖G存在一個Pfaman定向σ，那么該圖的完美匹配的個數(shù)等于其對應(yīng)的斜鄰接矩陣S(Gσ)的行列式的平方根。
　　在2010年，Adiga等人研究了定向圖的斜譜并且引入了斜能量的概念，它定義為斜鄰接矩陣的所有特征根的模之和。斜能量可以看作是無向圖的能量在定向圖上的一種

3、推廣。在2012年，Cavers等人對定向圖上的斜鄰接矩陣作了廣泛的研究并且提出了一些關(guān)于斜譜半徑的有趣的問題，例如：在給定頂點數(shù)的奇圈圖(所有圈都是奇圈)中，哪些圖具有最大斜譜半徑?其實他們的研究主要基于在加拿大阿爾伯塔省“BIRS”研究站召開的“Theory and Applications of Matrices Described by Patterns”會議上討論的結(jié)果。自從他們的結(jié)果問世以來，越來越多的學者開始了對斜鄰接矩陣

4、的研究。
　　定向圖的斜譜半徑的上界已經(jīng)被很多學者研究并且關(guān)于這個上界已經(jīng)有了很好的結(jié)果。但是，斜譜半徑的下界方面的結(jié)果很少。在第二章，我們研究了斜譜半徑的下界并得到了一些新結(jié)果。進一步我們給出了那些滿足斜譜半徑達到下界√△的圖的一些性質(zhì)，其中△為圖的最大度。最后，利用已經(jīng)得到的斜譜半徑的下界，我們給出了斜能量的幾個下界，這些結(jié)果改進了由Adiga等人得到的斜能量下界。
　　Cavers等人證明了一個結(jié)果：如果G是一個奇圈圖

5、(所有圈都是奇圈)，那么G的任意一個定向圖Gσ的斜譜半徑都等于G的最大匹配根。其中，圖G的最大匹配根指的是圖G的匹配多項式的所有根的最大值。并且他們提出了一個猜想：在所有頂點數(shù)為n的奇圈圖中，能達到最大斜譜半徑的圖一定同構(gòu)于一個特殊奇圈圖，該圖有一個度為n-1的頂點并且恰好有|3(n-1)/2|條邊。在第三章我們證明了這個猜想。進一步，我們給出了給定頂點數(shù)和邊數(shù)的奇圈圖的斜譜半徑的緊上界，并且完全刻畫了達到該上界的極值圖。
　　在

6、2012年，Gutman和Wagner提出了圖G的匹配能量ME(G)的概念，它定義為圖G的匹配多項式的所有根的絕對值之和。Gutman和、Wagner指出匹配能量在化學上有很重要的應(yīng)用。他們得到了下面一個重要的關(guān)系式：TRE(G)=E(G)-ME(G)，其中TRE(G)是圖G的拓撲共振能而E(G)是圖G的能量。對于n個頂點的隨機圖Gn,p，其中p∈(0，1)，他們給出了匹配能量ME(Gn,p)的上界和下界。進一步，他們提出了一個猜想：當

7、n→∞，n-3/2E(ME(Gn,p))幾乎總是收斂于8√p/3π，其中E(ME(Gn,p))是ME(Gn,p)的期望。
　　在第四章，我們引入了隨機圖的經(jīng)驗匹配根(匹配多項式的根)分布函數(shù)的概念。大部分關(guān)于根分布的研究主要集中于隨機矩陣的譜分布。隨機矩陣的譜分布可追溯到Wigner的杰出工作一半圈分布。利用矩方法，我們證明了隨機圖的經(jīng)驗匹配根分布幾乎總是弱收斂于半圈分布。最后，我們利用分析的方法證明了他們的猜想。事實上，我們證明