关于定向线图及相关矩阵的一些简短笔记-计算机科学-机器学习-算法.pdfVIP

关于定向线图

及相关矩阵的一些简短笔记

CyriacAntony,JacobAntony

2025年7月21日

本

译

中1介绍

1

v有向线图的概念是由Kotani和Sunada引入的[1]，它们与Hashimato的[2]非

1

2回溯矩阵密切相关。设是一个（简单无向）图。图的定向线图是一个有向图，其

8

3顶点集为，当[3]时，在它从顶点到顶点

1

.存在一条弧。我们将的有向线图表示为，其基础无向图表示为。我

7

0们可以用从通过将的每条边替换为两条弧和获得的简单有向

5

2图来重新定义定向线图。有向线图的是以的弧集为其顶点集的有向

:

v图，并且当时，从顶点到顶点存在一条弧（参见图1）。的非

i

x

r回溯矩阵是的邻接矩阵。

a

邻接矩阵的特征多项式对于-正则图及其是众所周知的。已知

这个多项式的根是Ihara函数[2]的极点的倒数。我们确定了图的（邻接矩

阵）的特征多项式以及的斜对称邻接矩阵。我们还展示了这一结果在

星着色中的应用（定义和详细信息见第2.2节）。

我们考虑的所有图都是简单且有限的；除非另有说明，否则它们也是无向的。

为了澄清，我们考虑的有向图也是简单的（即没有平行弧，尽管可能存在两个方向

相反的弧）。为方便起见，我们假设完全图的顶点集是对于所有。

1

2结果

2.1的谱

Lubetzky和Peres[4]证明了有向线图的邻接矩阵与具有和块的块

对角矩阵酉等价。

定理1(卢贝茨基和佩雷斯[4]).设是一个具有个顶点和条边的连通-正

则图，其特征值为，其中。然后，矩阵的非回溯矩阵与以下

分块对角矩阵单位相似，

diag(1)

其中和重复次，

if