混合图的某些代数与组合性质

Algebraic graph theory is a combination of graph theory and algebra theory, which mainly studies and characterizes the properties of graph structure by means of the algebraic methods. Based on graph structure theory, matrix theory and charater theory of permutation group, this project aims to study two questions on mixed graphs. One is about the algebraic properties of mixed graphs including the spectrum of Hermitian adjacency (Laplacian) matrix and its applications on Hamiltonian for mixed graph, another is the combinatorial properties of mixed graphs inlcluding the immanants of Hermitian adjacency (Laplacian) matrix and its immanantal polynomials.

代数图论是图论与代数有机结合的产物，主要利用代数方法研究图论问题，进而刻画图的结构性质。本项目将结合图的结构理论、矩阵理论、置换群的特征标理论等，围绕混合图的Hermitian邻接矩阵、Hermitian Laplacian矩阵以及这两类矩阵的immanant展开研究，一方面研究混合图的代数性质，具体包括：Hermitian邻接矩阵、Hermitian Laplacian矩阵的谱理论及其在哈密尔顿性方面的应用；另一面研究混合图的组合性质，具体包括：混合图的Hermitian邻接矩阵、Hermitian Laplacian矩阵的immanant及其多项式的组合性质。

以往有向图的矩阵表示大部分为实矩阵，但不是对称矩阵，因而特征值不一定全是实数，利用这些矩阵的谱来刻画有向图的一些结构问题不是很便捷。本项目在前期工作的基础上，给出了有向图的Hermitian normalized Laplacian矩阵，研究该矩阵的谱理论，进而刻画有向图的结构问题，并利用图的结构参数给出了该矩阵的特征多项式的系数表达式。.网络相似性度量在网络分析领域已被证明是必不可少的。本项目将与图的特征值相关的指标与Ediz偏心连通性指标结合，来研究网络相似性度量问题，以及在网络数据分析中的应用。.Immanant是一类广义矩阵函数，是矩阵行列式和积合式的一般情况，该值与有限群的特征表理论联系在一起，因而它的计算很复杂。本项目研究了完全图和圈的邻接矩阵、Laplacian矩阵的单钩immanant、积合式的表达式。.符号k图是在每个顶点及其关联边上都有关联函数的k一致超图。本项目研究了符号k图邻接张量（超矩阵）和拉普拉斯张量（超矩阵）的H谱、顶点的逆Perron值的界。.k-eccentricity是基于图的steiner树给出的，已知图的steiner树的求解问题是NP困难的，因而k-eccentricity的计算也是困难的。本项目研究了k-eccentricity的一些性质，给出了一些特殊图的k-eccentricity的算法，并利用它们给出了网络相似度测量函数。通过实验显示，构造的测量函数比利用图的相关矩阵的特征值构造的测量函数具有很好的优越性。