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

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

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

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

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

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

6、2012年，Gutman和Wagner提出了圖G的匹配能量ME(G)的概念，它定義為圖G的匹配多項(xiàng)式的所有根的絕對(duì)值之和。Gutman和、Wagner指出匹配能量在化學(xué)上有很重要的應(yīng)用。他們得到了下面一個(gè)重要的關(guān)系式：TRE(G)=E(G)-ME(G)，其中TRE(G)是圖G的拓?fù)涔舱衲芏鳨(G)是圖G的能量。對(duì)于n個(gè)頂點(diǎn)的隨機(jī)圖Gn,p，其中p∈(0，1)，他們給出了匹配能量ME(Gn,p)的上界和下界。進(jìn)一步，他們提出了一個(gè)猜想：當(dāng)

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