论文部分内容阅读
令Gσ为简单无向图G的一个定向图且s(Gσ)为Gσ的斜邻接矩阵。定向图Gσ的斜能量εs(Gσ)定义为它的斜邻接矩阵S(Gσ)的所有特征值的模之和。这一概念首先由Adiga, Balakrishnan和So在2010年提出来,并且可以看作无向图能量在定向图上的一种推广形式。而(无向)图能量的概念是由Gutman在1977年提出来的:给定一个简单无向图G,它的能量£(G)定义为它的邻接矩阵A(G)的所有特征值的绝对值之和。由于图能量和化学之间的紧密关系,图能量已经得到了广泛而深入的研究。但是考虑到在一些情况下,化学家使用有向图模型而不是无向图模型,例如,使用有向图的顶点来表示不同的化学物质,弧的方向来表示相应的两个物质之间的特定反应。因而,人们希望定向图的斜能量能如同图能量一样在化学上有着重要应用。目前,定向图的斜能量正得到越来越广泛的关注。本文主要从以下几个方面研究定向图的斜能量:考虑二部图G的定向图Gσ,使其满足Sps(Gσ)=iSp(G);刻画所有具有最优斜能量的4正则定向图;研究各种图积的定向及导出的定向图的斜谱和斜能量;在随机图背景下研究定向图的斜能量。第一章是引言,我们首先给出了有关图和定向图的一些基本概念,然后介绍了定向图斜能量的相关背景,最后简要地介绍了斜能量的研究进展,同时总结了本文的主要结果。在第二章,我们主要研究了满足性质Sps(Gσ)=iSp(G)的二部图的定向。Shader和So证明了一个图G是二部图当且仅当该图G存在定向Gσ使得Sps(Gσ)=iSp(G),并且指出二部图的基本定向恰好满足该性质。之后,Cui和Hou猜想二部图满足Sp。(Gσ)=iSp(G)的定向在Switching等价条件下是唯一的。在本章,我们证明了该猜想是正确的,并且给出了有效的算法将任一满足Sps(Gσ)=iSp(G)的定向通过一系列Switching变换转化为基本定向。在第三章,我们主要研究最优斜能量。对于任何一个定向图Gσ,εs(Gσ)≤n(?),其中n和△分别表示图G的顶点数和最大度。为方便起见,称上界n(?)为最优斜能量,相应的定向为图G的最优定向。Adiga, Balakrishnan和So已经证明具有最优定向的图一定是正则图。本章刻画了所有具有最优斜能量的4正则定向图:首先刻画所有可能的具有最优定向的4正则图,然后证明了这些正则图恰好都具有最优定向并且给出了相应的定向,最后证明了这些正则图的最优定向在Switching等价和同构条件下是唯一的。在第四章,我们研究了各种图积的定向及导出的定向图的斜谱,其中包括Cartesian积,Kronecker积,strong积和exicographic积。我们在不同节分别讨论了这些积:首先给出各种积的定向,然后计算导出的定向图的斜谱。据此我们构造出了一些具有最优斜能量的定向图类。注意到具有最优斜能量的定向图的斜邻接矩阵恰好是一个斜、Veighing矩阵,反之也成立。所以本章也简单介绍了有关斜Weighing矩阵的一些猜想和研究进展。在第五章,我们在随机图背景下研究定向图的斜能量。我们定义了两种随机图模型:随机定向图模型gσ(n,p)和随机定向正则图模型gn,dσ。对于随机定向图模型gσ(n,p),我们首先研究定向图斜邻接矩阵的极限谱分布,据此我们得到了斜能量的确切估计式,此公式对几乎所有定向图都成立。对于随机定向正则图模型gn,dσ,我们分两种情况来估计斜能量:d是一个固定值和d趋于无穷,并且分别得到了它们的确切估计式。