關(guān)于定向圖的斜能量的研究.pdf

1、令Gσ簡單無向圖G的一個(gè)定向圖且S(Gσ)為Gσ的斜鄰接矩陣。定向圖Gσ的斜能量εs（Gσ）定義為它的斜鄰接矩陣S(Gσ)的所有特征值的模之和。這一概念首先由Adiga，Balakrishnan和So在2010年提出來，并且可以看作無向圖能量在定向圖上的一種推廣形式。而（無向）圖能量的概念是由Gutman在1977年提出來的:給定一個(gè)簡單無向圖G，它的能量ε(G)定義為它的鄰接矩陣A(G)的所有特征值的絕對值之和。
　　由于圖能量

2、和化學(xué)之間的緊密關(guān)系，圖能量已經(jīng)得到了廣泛而深入的研究。但是考慮到在一些情況下，化學(xué)家使用有向圖模型而不是無向圖模型，例如，使用有向圖的頂點(diǎn)來表示不同的化學(xué)物質(zhì)，弧的方向來表示相應(yīng)的兩個(gè)物質(zhì)之間的特定反應(yīng)。因而，人們希望定向圖的斜能量能如同圖能量一樣在化學(xué)上有著重要應(yīng)用。目前，定向圖的斜能量正得到越來越廣泛的關(guān)注。
　　本文主要從以下幾個(gè)方面研究定向圖的斜能量:考慮二部圖G的定向圖Gσ，使其滿足Sps（Gσ）=iSp(G);刻畫所

3、有具有最優(yōu)斜能量的4正則定向圖;研究各種圖積的定向及導(dǎo)出的定向圖的斜譜和斜能量;在隨機(jī)圖背景下研究定向圖的斜能量。
　　第一章是引言，我們首先給出了有關(guān)圖和定向圖的一些基本概念，然后介紹了定向圖斜能量的相關(guān)背景，最后簡要地介紹了斜能量的研究進(jìn)展，同時(shí)總結(jié)了本文的主要結(jié)果。
　　在第二章，我們主要研究了滿足性質(zhì)Sps（Gσ）=iSp(G)的二部圖的定向。Shader和So證明了一個(gè)圖G是二部圖當(dāng)且僅當(dāng)該圖G存在定向Gσ使得Sp

4、s(Gσ)=iSp(G)，并且指出二部圖的基本定向恰好滿足該性質(zhì)。之后，Cui和Hou猜想二部圖滿足Sps（Gσ）=iSp(G)的定向在Switching等價(jià)條件下是唯一的。在本章，我們證明了該猜想是正確的，并且給出了有效的算法將任一滿足Sps（Gσ）=iSp(G)的定向通過一系列Switching變換轉(zhuǎn)化為基本定向。
　　在第三章，我們主要研究最優(yōu)斜能量。對于任何一個(gè)定向圖Gσ，εs（Gσ）≤n√Δ，其中n和Δ分別表示圖G的頂點(diǎn)

5、數(shù)和最大度。為方便起見，稱上界n√Δ為最優(yōu)斜能量，相應(yīng)的定向?yàn)閳DG的最優(yōu)定向。Adiga，Balakrishnan和So已經(jīng)證明具有最優(yōu)定向的圖一定是正則圖。本章刻畫了所有具有最優(yōu)斜能量的4正則定向圖:首先刻畫所有可能的具有最優(yōu)定向的4正則圖，然后證明了這些正則圖恰好都具有最優(yōu)定向并且給出了相應(yīng)的定向，最后證明了這些正則圖的最優(yōu)定向在Switching等價(jià)和同構(gòu)條件下是唯一的。
　　在第四章，我們研究了各種圖積的定向及導(dǎo)出的定向圖

6、的斜譜，其中包括Cartesian積，Kronecker積，strong積和lexicographic積。我們在不同節(jié)分別討論了這些積:首先給出各種積的定向，然后計(jì)算導(dǎo)出的定向圖的斜譜。據(jù)此我們構(gòu)造出了一些具有最優(yōu)斜能量的定向圖類。注意到具有最優(yōu)斜能量的定向圖的斜鄰接矩陣恰好是一個(gè)斜Weighing矩陣，反之也成立。所以本章也簡單介紹了有關(guān)斜Weighing矩陣的一些猜想和研究進(jìn)展。
　　在第五章，我們在隨機(jī)圖背景下研究定向圖的斜