關于定向圖的斜能量的研究.pdf

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

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

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

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

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

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