有向图的埃尔米特拉普拉斯矩阵研究

拉普拉斯矩阵对于无向图的研究具有重要意义，其特征值反映了图的部分结构与性质，据此可以设计有效的算法以解决图上一些相关的任务，如划分、聚类等。将拉普拉斯矩阵推广至有向图，一大难点是失去了对称性，特征值可能为复数。为了规避该问题，最近的研究引入了k次单位根作为边权，定义了复数域上的拉普拉斯矩阵，该矩阵是埃尔米特矩阵。文中提出了有向边的旋转角的概念，对该矩阵进行了推广，证明了其具有与无向图拉普拉斯矩阵类似的代数性质；给出了有向图的约束方程组和有向环路的定义，证明了拉普拉斯矩阵最小特征值为0、约束方程组有解以及图中任意有向环路旋转角为2lπ(l∈?)这三者间的等价性。最后给出了一些相关推论及应用。