图论基础

图和有向图（Graphs and Diagraphs）

无向图（Graphs）

一个无向图 (Undirected graph)，简称为图 (Graph)，由两个集合组成：

  • 节点集 (Nodes/Vertices)：用 $V$ 表示。
  • 边集 (Edges)：用 $E$ 表示。

在无向图中，边是无序对（Unordered pairs）。也就是说，连接节点 $u$ 和 $ v $ 的边记作 $\{u, v\}$，它没有方向，从 $u$ 到 $ v $ 和从 $ v $ 到 $u$ 是一样的。

邻居 (Neighbors)：如果两个节点之间有一条边相连，我们就说它们互为邻居。节点 $ v $ 的所有邻居组成的集合，我们用 $\mathcal{N}_G(v)$ 来表示。

度数 (Degree)：一个节点 $ v $ 的“度”，就是它拥有的邻居的数量（或者说连着多少条边）。

正则图 (Regular Graph)：这是一个特殊的图类。如果一个图里所有节点的度数都一模一样，我们就叫它正则图。

下面是几种在实际应用中经常用到的基础图结构：

image-20260429020308735

  1. 路径图 (Path graph)：像一根线一样，节点按顺序排列，边只连接相邻的节点。
  2. 环形图 (Cycle/ring graph)：把路径图的首尾相连。
  3. 星形图 (Star graph)：有一个核心节点（中心），其他所有节点都只和这个中心相连，周围节点之间互不相连。
  4. 完全图 (Complete graph)：最“社牛”的图，图中的任意两个节点之间都有一条边相连。
  5. 完全二分图 (Complete bipartite graph)：节点被分成两个阵营（两个集合）。同阵营内部互不相连，但第一个阵营的每个节点，都与第二个阵营的每一个节点相连。

有向图 (Directed Graphs / Digraphs)

给无向图的边加上箭头，这就变成了有向图。

有向图 $G = (V, E)$ 中，边变成了有序对（Ordered pairs）边记作 $(u, v)$，代表一条从节点 $u$ 指向节点 $ v $ 的边。这就像单行道，$u$ 是起点，$ v $ 是终点。

对称性：如果在一个有向图中，只要有从 $u$ 到 $ v $ 的边 $(u, v)$，就必定有从 $ v $ 到 $u$ 的边 $(v, u)$，那么这个有向图在结构上等同于无向图。

自环 (Self-loops)：有向图允许一个节点有一条指向自己的边。在常规的无向图中，我们通常是不允许出现自环的。

image-20260429020541387

有向图的子图与度数 (Subgraphs & Degrees in Digraphs)

1. 子图的三种形态 (Subgraphs)

  • 普通子图 (Subgraph)：从原图中随便挑一部分节点 $V’$ 和一部分边 $E’$ 组成的图。
  • 生成子图 (Spanning subgraph)：节点必须一个不少地全选（$V’ = V$），但边可以只挑一部分。
  • 导出子图 (Induced subgraph)：先挑一部分节点 $V’$，然后把原图中连接这些节点的所有边全盘保留。

2. 入与出邻居/度数 (In- and out-neighbors / degree)：因为有了方向，邻居和度数也分成了“进”和“出”

  • 入/出邻居：对于边 $(u, v)$，$u$ 是 $ v $ 的入邻居（指进来），$ v $ 是 $u$ 的出邻居（指出去）。
    • 符号表示：$\mathcal{N}^{\text{in}}(v)$ 表示入邻居集合，$\mathcal{N}^{\text{out}}(v)$ 表示出邻居集合。
  • 入度/出度：
    • 入度 $d_{\text{in}}(v)$：指向节点 $ v $ 的边的数量。
    • 出度 $d_{\text{out}}(v)$：从节点 $ v $ 指出的边的数量。
    • 注意：如果有一个自环，它既算作一次入度，也算作一次出度。

拓扑平衡 (Topologically balanced)：如果一个有向图里，每一个节点的入度都等于它的出度（$d_{\text{in}}(v) = d_{\text{out}}(v)$），我们就说这个图是拓扑平衡的。

无向图中的游走（walks）和连通性（connectivity）

游走与简单游走 (Walks & Simple Walks)

  • 游走 (Walk)：想象你在图的节点上散步。你从一个节点出发，沿着边走到下一个节点，一路走下去形成的序列就叫“游走”（有些教材也称之为 Path）。
  • 简单游走 (Simple Walk)：如果你在散步时不走回头路，即除了起点和终点可以相同之外，途中不重复经过任何一个节点，这就叫简单游走。

连通性与连通分支 (Connectivity & Connected Components)

  • 连通图 (Connected Graph)：如果在一个图里，任意两个节点之间都存在至少一条游走路径（即大家都能互相“走”到），这个图就是连通的。
  • 连通分支 (Connected Components)：如果一个图像是一座座孤岛，整体不连通，那么每一座“孤岛”（各自内部连通的最大子图）就被称为一个连通分支。
    • 👉 请看 PPT 上的 Figure 3.3：这整个是一个图，但它不连通。它由左、右两个连通分支构成。

环与树 (Cycles & Trees)

  • 环 (Cycle)：起点和终点在同一个位置的简单游走，并且至少包含3个不同的节点（在无向图中，两点之间来回走不算作环）。

  • 树 (Tree)：这是一个非常经典的结构。如果一个图既是连通的，又没有任何环 (Acyclic)，它就是一棵树。

    image-20260429163828323

有向图中的游走（walks）和连通性（connectivity）

有向游走与有向环 (Directed Walks & Cycles)

  • 有向游走 (Directed Walk)：完全顺着箭头方向移动形成的序列。
  • 有向环 (Directed Cycle)：顺着箭头走了一圈又回到了起点。
    • 注意区别：在有向图中，长度为1的自环（自己指向自己），以及长度为2的环（A指向B，B又指回A）都是被允许且常见的。

DAG与源汇点 (DAG, Sources and Sinks)

  • DAG (Directed Acyclic Graph, 有向无环图)：如果一个有向图里没有任何有向环，我们就叫它 DAG。它在计算机科学、任务调度和网络拓扑中极其常见，因为它代表着一种没有死循环的层级关系。
  • 源点 (Source) 与 汇点 (Sink)：
    • 源点 (Source)：只出不进。入度为 0 的节点（$d_{\text{in}} = 0$）。
    • 汇点 (Sink)：只进不出。出度为 0 的节点（$d_{\text{out}} = 0$）。
    • 定理：任何一个 DAG 都至少有一个源点和一个汇点。

如下图(a)：上面的两个点没有箭头指入，是源点；最下面的点没有箭头指出，是汇点。这个图没有环，是一个典型的 DAG。而(b) 顺时针形成了一个闭环，所以是一个有向环。

image-20260429163959024

有向树与生成树 (Directed Trees)

  • 有向树 (Directed tree / Rooted tree)：它首先必须是一个 DAG（无环），并且具备一个根节点 (Root)。从这个“根”出发，到达图中任何其他节点，都有且仅有唯一的一条有向游走路径。
  • 有向生成树 (Directed spanning tree)：如果你在一个复杂的有向图中，能抽取出一个子图，这个子图不仅包含原图的所有节点，而且它的结构刚好是一棵“有向树”，那么这就是原图的有向生成树。

应用视角：在一个通信网络或多智能体系统中，如果网络拓扑包含一棵有向生成树，意味着存在一个“根”节点，它的信号或指令可以通过网络有向地传递给系统内的每一个成员，这通常是系统能够实现信息同步或状态一致的基础前提。

有向图的联通特性（Connectivity Properties）

四种“连通定义”

因为有向图的边带有“单行道”属性，它的连通性比无向图要复杂得多。因此定义了四个级别的连通定义：

  1. 强连通 (Strongly connected)：图里任意两个节点之间，都存在互相到达的有向路径。
  2. 弱连通 (Weakly connected)：如果把所有箭头的方向都忽略掉（把它当成无向图看），它是连通的，那就是弱连通。
  3. 全局可达节点 (Globally reachable node)：图里存在一个节点，所有其他节点都能顺着箭头走到它这里，则称为全局可达节点。
  4. 有向生成树 (Directed spanning tree)：图里存在一个“根”节点，从这个根出发，可以顺着箭头走到所有其他节点，则为有向生成树。这在多智能体系统中极其重要，往往是信息能全网广播、系统达成一致性的最低拓扑要求。

一个小技巧（反转图 $G^{(\text{rev})}$）： 如果你把一个有向图里所有的箭头都反转（逆行），就得到了反转图。一个有趣的对称关系是：如果原图有一个“有向生成树”（一能到多），那么它的反转图就必定包含一个“全局可达节点”（多能到一）。

周期性与非周期性 (Periodic and Aperiodic)

在强连通图中，我们在里面“绕圈子”的规律。核心看的是简单环的长度。

计算最大公约数 (GCD)：把你在这个图里能找到的所有简单环的长度都列出来，求它们的最大公约数 $k$。

  • 周期性图 (Periodic)：如果 $k > 1$，说明你在这个图里转圈，步数总是 $k$ 的倍数，这就是周期性的。如下图左，只有长度为 2 的环，所以周期是 2
  • 非周期性图 (Aperiodic)：如果 $k = 1$（最大公约数是1），那就是非周期性的。如下图中间，一个环步长是1，一个是2，公约数为1。还有下图右边，一个步长是2，一个步长是3，公约数为1。

image-20260429170925190

一个结论：如果一个强连通图里哪怕只有一个自环 (Self-loop)，它必定是非周期的。因为自环是一个长度为 1 的环。任何正整数和 1 的最大公约数都是 1。

凝聚图（Condensation digraph）

当我们面对一个极其庞大且复杂的有向图时，直接分析会让人眼花缭乱。可以通过凝聚图来简化它。

  1. 找圈子 —— 强连通分支 (Strongly connected components)： 首先，我们在原图里把那些能够“互相联通”的节点全部打包在一起。一个 SCC 就是一个局部最大的强连通子图。在这个小圈子里，大家是绝对连通的。

  2. 打包浓缩 —— 凝聚图(Condensation digraph $C(G)$)：

    我们把刚才找到的每一个 SCC “压缩”成一个超级节点。

    • 如果在原图中，圈子 A 里的某个节点，有一条边指向圈子 B 里的某个节点；
    • 那么在凝聚图 $C(G)$ 中，我们就画一条从“超级节点 A”指向“超级节点 B”的边。‘

下图是一个凝聚图的例子

image-20260429171307642

凝聚图 $C(G)$ 最关键的性质：

  1. 凝聚图 $C(G)$ 绝对没有环 (Acyclic)：经过浓缩后，新的图 $C(G)$ 绝对不可能再有环了！它必然是一个 DAG（有向无环图）。因为如果超级节点之间还能形成环，那就说明这几个超级节点本来就应该被打包进同一个更大的 SCC 里。
  2. 弱连通性的“遗传”：如果原图 $G$ 是弱连通的（忽略箭头后连通），那么把节点打包后的凝聚图 $C(G)$ 依然是弱连通的，反之亦然。这很符合直觉：打包并不会凭空切断原本的连接。

全局可达性的“三位一体”等价关系：以下三件事是完全等价（同生共死）的：

  • (a) 原图 $G$ 里有一个“全局可达节点”（所有节点都能走到它）。
  • (b) 凝聚图 $C(G)$ 里有一个“全局可达的超级节点”。
  • (c) 凝聚图 $C(G)$ 中存在唯一的一个汇点 (unique sink)。

或写成：

  • 如果原图有一个全局可达点 $ v $，那么它所在的超级节点 $H$ 也是全局可达的。
  • 如果浓缩图里有一个超级节点 $H$ 是全局可达的，那么在 $H$ 内部随便挑一个节点 $ v $，$ v $ 也是在原图中全局可达的。
  • 如果有一个节点谁都能到（全局可达），它就必须是最终的那个“坑”（汇点），不能再往外流了（如果往外流，就意味着别人到不了它，或者产生了环）。

有权有向图（Weighted digraphs）

前面我们一直在讨论图的“骨架”（拓扑结构），也就是节点之间有没有连接。现在给这些连接加上“强度”，也就是加权有向图 (Weighted Digraphs)。在研究分布式控制或多智能体一致性时，这些权重往往代表着节点之间的通信信道质量、传感器可靠性，或者是系统间的耦合强度。

什么是加权有向图？

三元组定义：普通的有向图是由节点 $V$ 和边 $E$ 组成的二元组。现在我们引入了第三个元素：权重集合 $\{a_e\}_{e \in E}$。图被定义为一个三元组 $G = (V, E, \{a_e\})$。

权重的物理意义与符号：

  • 所有的权重都必须是严格为正数的（大于0）。
  • 为了方便表示，一条从节点 $i$ 指向节点 $j$ 的边的权重，我们通常记作 $a_{ij}$。

如下图，从节点 1 到节点 2 的箭头旁标注了 3.7，所以 $a_{12} = 3.7$。注意节点 5 有一个自环，所以 $a_{55} = 4.4$。

image-20260429173637098

加权度数 (Weighted Degrees)

在无权图中，度数是“数箭头的个数”。在加权图中，度数变成了“算权重的总和”。

加权出度 (Weighted out-degree) $d_{\text{out}}(v_i)$：节点 $i$射向所有其他节点 $j$ 的箭头的权重，全部加起来。

加权入度 (Weighted in-degree) $d_{\text{in}}(v_i)$：把所有其他节点 $j$ 射向节点 $i$的箭头的权重，全部加起来。

权重平衡 (Weight-balanced Digraphs) ：如果一个加权有向图里，每一个节点的“加权入度”都严格等于它的“加权出度”（即 $d_{\text{out}}(v_i) = d_{\text{in}}(v_i)$），我们就称这个图是权重平衡的。

在这个状态下，每个节点的“能量/信息”流入量等于流出量。在构建拉普拉斯矩阵 (Laplacian Matrix) 时，权重平衡图能保证系统的全 1 向量是拉普拉斯矩阵的左特征向量，这直接决定了多智能体系统最终能否收敛到“平均一致性 (Average Consensus)”。

代数图论

当我们要把通信网络的拓扑结构交给计算机处理，或者在研究网络化系统的一致性 (consensus) 算法中进行严谨的稳定性分析时，我们必须把“图形”转化为“代数语言”。这就需要代数图论 (Algebraic Graph Theory)

邻接矩阵（adjacency matrix）

要想用数学描述一个图，最直接的方法就是建一个表格，记录谁和谁连着。这就是邻接矩阵 $A$。

加权邻接矩阵 (Weighted adjacency matrix)

对于一个有 $n$ 个节点的加权有向图，它的邻接矩阵 $A$ 是一个 $n \times n$ 的方阵。

规则：矩阵的第 $i$ 行、第 $j$ 列的元素 $a_{ij}$，正好等于从节点 $i$ 指向节点 $j$ 的边的权重。如果两点之间没连线，权重就是 0。

行与列的物理意义：行 (Row) 代表“起点 (from)”，列 (Column) 代表“终点 (to)”。例如下面这个例子：

image-20260429174754647

  • 找节点 1 到节点 2 的连线，权重是 3.7。所以矩阵第一行第二列 $A_{12} = 3.7$。
  • 找节点 2 到节点 1 的连线，权重是 8.9。所以矩阵第二行第一列 $A_{21} = 8.9$。
  • 节点 5 有一个指向自己的自环，权重 4.4，所以对角线上 $A_{55} = 4.4$。

二值邻接矩阵 (Binary adjacency matrix)

有时候我们在分析时，并不关心信号有多强，只关心“能不能连通”。这时候我们就可以把权重全部简化为 1。

矩阵 $A$ 里的元素只在 $\{0, 1\}$ 中取值：有边就是 1，没边就是 0。这相当于剥离了“强度”属性，只保留了纯粹的拓扑骨架。

这种二值化的纯拓补骨架可以可以用像素图来描绘，如下图

image-20260430185812113

度矩阵 (Degree Matrices)

度矩阵与邻接矩阵不同，它们是对角矩阵 (Diagonal matrices)——即除了主对角线上有数字，其他地方全都是 0。

加权出度矩阵 $D_{\text{out}}$

定义：对角线上的元素分别是每个节点的加权出度 $d_{\text{out}}(1), \dots, d_{\text{out}}(n)$。

$\mathbf{1}_n$ 是一个全由 1 组成的列向量。当邻接矩阵 $A$ 乘以 $\mathbf{1}_n$ 时，线性代数告诉我们，这实际上就是在把 $A$ 的每一行进行求和。这完全印证了前面的逻辑：第 $i$ 行记录了节点 $i$ 发出的所有边，所以行求和就是出度（表示节点向外发送信息的总强度）。

加权入度矩阵 $D_{\text{in}}$、

定义：对角线上的元素是每个节点的加权入度 $d_{\text{in}}(1), \dots, d_{\text{in}}(n)$。

$A^\top$ 是把邻接矩阵转置（行变列，列变行）。转置后再乘以 $\mathbf{1}_n$，等价于把原矩阵 $A$ 的每一列进行求和。第 $j$ 列记录了所有指向节点 $j$ 的边，所以列求和就是入度（表示节点接收信息的总强度）。

Toeplitz 矩阵

当我们凝视路径图和环形图的矩阵时，数学家提取出了一个极其重要的代数结构：Toeplitz 矩阵（托普利兹矩阵）你从矩阵的任意一个元素出发，沿着右下方的对角线滑动，你会发现这条线上的所有数字都是一模一样的。

换句话说，什么是 Toeplitz 就是“对角线常数”矩阵 (diagonal-constant)。

两大特殊形态：

  • 三对角 Toeplitz (Tridiagonal Toeplitz)：除了主对角线和它紧挨着的上下两条线有非零常数外，其他全是 0。这完美对应了路径图 $P_n$。
  • 循环矩阵 (Circulant)：它是 Toeplitz 的进阶版，矩阵的每一行都是上一行向右“循环移位”一个位置得到的。这完美对应了环形图 $C_n$。

image-20260430190044342

对于Toeplitz 矩阵，我们不需要让计算机去傻傻地做数值分解，我们有极其优美的闭式解析解（Closed-form）！无论 $n$ 是一百还是一万，我们都能直接写出它的所有特征值和特征向量。如下表

Graph 类型 Adjacency Matrix 邻接矩阵 Adjacency Spectrum 邻接谱
Path graph $P_n$ Toeplitz tridiagonal $\{ 2\cos\left(\tfrac{\pi i}{n+1}\right) \mid i=1,\ldots,n \}$
Cycle graph $C_n$ Circulant $\{ 2\cos\left(\tfrac{2\pi i}{n}\right) \mid i=1,\ldots,n \}$
Star graph $S_n$ $\mathbf{e}_1\mathbf{e}_1^{\top} + \mathbf{e}_{-1}\mathbf{e}_1^{\top}$ $\{ \sqrt{n-1}, 0,\ldots,0, -\sqrt{n-1} \}$
Complete graph $K_n$ $\mathbf{1}_n\mathbf{1}_n^{\top} - I_n$ $\{ (n-1), -1,\ldots,-1 \}$
Complete bipartite $K_{n,m}$ $\begin{bmatrix} 0_{n\times n} & \mathbf{1}_{n\times m} \\ \mathbf{1}_{m\times n} & 0_{m\times m} \end{bmatrix}$ $\{ \sqrt{nm}, 0,\ldots,0, -\sqrt{nm} \}$

代数图论:基本和原型

邻接矩阵频谱（Adjacency Spectrum）

在代数图论中，图的“谱 (Spectrum)” 就是指它邻接矩阵的所有特征值的集合。特征值决定了网络中信息扩散的速度、系统达成一致性的快慢等核心动态特性。

在下文中，我们用 G 表示一个加权有向图，用 A 表示它的加权邻接矩阵。

有向图性质 (Digraph G) 非负矩阵性质 (Non-negative matrix A, adjacency of G)
G 是无向图 (undirected) $A = A^{\top}$
G 是权重平衡图 (weight-balanced) $A \mathbf{1}_n = A^{\top} \mathbf{1}_n$，即 $D_{\text{out}} = D_{\text{in}}$
(无自环) 节点 i 是汇点 (sink) (零对角) A 的第 i 行和为 0
(无自环) 节点 i 是源点 (source) (零对角) A 的第 i 列和为 0
每个节点的加权出度为 1 ($D_{\text{out}} = I_n$) A 是 row-stochastic (行随机矩阵)
每个节点的加权出度与入度均为 1 ($D_{\text{out}} = D_{\text{in}} = I_n$) A 是 doubly-stochastic (双随机矩阵)

解释：

  • 无向图：如果 $i$ 到 $j$ 有边且权重相等，那么 $j$ 到 $i$ 也是一样的。反映在矩阵上，就是沿着主对角线完美对称，即$A = A^{\top}$
  • 权重平衡图 (Weight-balanced) ：每个节点的“加权出度”等于“加权入度”。在矩阵里，这刚好对应着每一行的元素总和，等于对应列的元素总和。
  • 汇点 (Sink) ：汇点是“只进不出”的。它没有向外的箭头，所以它对应的矩阵行（代表发出）全是 0。
  • 源点 (Source) ：源点是“只出不进”的。没有箭头指向它，所以它对应的矩阵列（代表接收）全是 0。
  • 出度全为 1 ：如果图中每个节点的总出度都是 1，那么矩阵的每一行加起来都等于 1。这在概率转移矩阵（马尔可夫链）中非常常见。
  • 出入度全为 1：这是最完美的平衡状态——矩阵不仅每一行加起来是 1，每一列加起来也是 1。

矩阵乘法与“多跳路由”

代数图论中，矩阵的乘方，代表了图中的游走！

线性代数告诉我们，$(A^2)_{ij}$ 是矩阵 $A$ 的第 $i$ 行和第 $j$ 列的内积：

这个公式背后的物理意义极其精妙：

  • $(A)_{ih}$ 代表从节点 $i$ 到中继节点 $h$ 的连接（第一跳）。
  • $(A)_{hj}$ 代表从中继节点 $h$ 到目标节点 $j$ 的连接（第二跳）。
  • 如果 $(A)_{ih} > 0$ 且 $(A)_{hj} > 0$，说明存在一条路径 $i \to h \to j$。
  • 求和符号 $\sum$ 的作用，就是遍历网络中所有的中继节点 $h$，把所有可行的两跳路径累加起来。

因此，只要 $(A^2)_{ij} > 0$，就意味着绝对存在至少一条从 $i$ 到 $j$ 的长度为 2 的游走路径。

举个例子：

假设我们有 4 个节点，它们构成一个简单的无向连通图，如下图所示。

image-20260501170206045

其邻接矩阵如下：

观察 $A_{14} = 0$：代表从节点 1 到节点 4 没有直接的单跳连接。

现在我们计算 $A^2 = A \times A$：

$(A^2)_{14} = (0\times0) + (1\times1) + (1\times0) + (0\times0) = 1$（第一行乘第四列）

其中，只有$(1\times1)$这一步贡献了最终$(A^2)_{14}$的1，它的物理意义就是，可以从节点1的出（行）去到节点2（节点2的第二行末尾），再从节点2去到节点4。只有这一条路有贡献，因此只存在唯一一条从节点 1 到节点 4 路径，跳数为2。

这个定理可以推广到$A^k$：

  • 对于二值邻接矩阵 ($A_{0,1}$)：矩阵的 $k$ 次方 $A_{0,1}^k$ 的第 $(i, j)$ 个元素，精确等于从节点 $i$ 到节点 $j$ 长度为 $k$ 的游走路径的总条数。

  • 对于加权邻接矩阵 ($A$)：矩阵的 $k$ 次方 $A^k$ 的第 $(i, j)$ 个元素只要是正数（大于 0），就说明从节点 $i$ 到节点 $j$ 存在一条长度为 $k$ 的游走路径。

不可约矩阵的图论特征

基础概念

1.集合的划分 (Partition)

想象你所在的班级（全集），现在要进行分组。你需要把全班分成A组和B组。规则是：两组加起来必须是全班所有人（不能漏人），两组之间不能有同一个人兼任（不能重叠），并且两组都不能是空壳（每组至少得有一个人）。

在数学上，对于一个包含 $n$ 个节点的索引集合 $\{1, \dots, n\}$，我们定义它的一个划分 $\{\mathcal{I}, \mathcal{J}\}$ 满足三个严格的条件：

  1. 完备性（不能漏人）：$\mathcal{I} \cup \mathcal{J} = \{1, \dots, n\}$
  2. 非空性（每组至少一个人）：$\mathcal{I} \neq \emptyset, \mathcal{J} \neq \emptyset$
  3. 互斥性（不能重叠）：$\mathcal{I} \cap \mathcal{J} = \emptyset$

2.置换矩阵 (Permutation Matrix)

置换矩阵就像是一个“洗牌机”。当你用它去乘以一个向量时，它不会改变原本数值的大小，而仅仅是把它们的位置打乱重新排列。置换矩阵是一个正交的二值方阵（Binary Matrix），它的特点是每一行和每一列都有且仅有一个 1，其余全为 0。

代数上，它通过置换基向量 $\mathbb{e}_1, \dots, \mathbb{e}_n$ 来重新排列向量或矩阵的元素。

举个例子，对于一个图的邻接矩阵 $A$，如果我们对其进行变换 $P^T A P$（其中 $P$ 是置换矩阵），这在物理意义上仅仅代表我们对图中的节点重新编了个号。比如把原来的节点 1 叫做节点 3，节点 3 叫做节点 1。图的拓扑结构和连通性并没有发生任何实质性的改变。

举个例子来看，现在有置换矩阵P：

我们使用向量$[1, 2, 3]^\top$和它相乘：

向量 $[1, 2, 3]^\top$ 乘上 $P$ 之后变成了 $[2, 3, 1]^\top$。这就像是给节点重新发身份证：原来的 2 号变成了新的 1 号，原来的 3 号变成了新的 2 号，原来的 1 号变成了新的 3 号。

为什么是 $PAP^\top$ 而不是 $PA$？

  • 如果只做 $PA$，你仅仅是把矩阵的“行”打乱了（即改变了信息的接收方视角）。
  • 你要想让图的结构保持一致，必须同时对“列”（信息的发送方）做同样的打乱。这就需要右乘 $P^\top$。

还是使用上面的置换矩阵P，下面计算结果非常直观地展示了这一点：原本 $A$ 中位置在 $(1, 2)$ 的元素 $a_{12}$（代表节点 1 到 2 的边），经过PA变换后，是第一行变去了第三行，发送节点的顺序置换。经过$PAP^{\mathrm{T}}$变换后，跑到了新矩阵的 $(3, 1)$ 位置。这才完美对应了前面说的：旧节点 1 变成了新节点 3，旧节点 2 变成了新节点 1。图的连线关系一模一样，仅仅是标签换了。

3.分块三角矩阵 (Block Triangular Matrix)

对于一个 $n \times n$ 的矩阵 $A$，如果存在一个整数 $r$（$1 \le r \le n-1$），使得 $A$ 可以被写成这样的形式：

其中左下角是一个 $(n-r) \times r$ 的零矩阵。

假设这个矩阵 $A$ 是某个有向图的邻接矩阵。左下角这一块 0，意味着从集合 $\mathcal{J}$（对应下方矩阵 $D$ 的节点）到集合 $\mathcal{I}$（对应左上矩阵 $B$ 的节点）没有任何有向边。 在通信网络或控制系统中，这意味着信息/能量只能单向流动，或者说系统中存在“信息孤岛”，无法实现全局的信息交互（Consensus）。

强联通有向图与不可约矩阵的代数性质

设 G 是一个有 n ≥ 2 个节点的带权有向图，并且其带权邻接矩阵为 A。如果G是一个联通有向图且是不可约矩阵，那么下面的陈述等价：

  1. A不可约，$\sum_{k=0}^{n-1} A^k > 0$（意味着：在 $n-1$ 步以内，网络中的任意两个节点之间，一定至少有一条路可以走通。）
  2. 不存在置换矩阵 $P$ 使得 $PAP^T$ 是分块三角阵（它意味着无论你怎么给节点重新编号，都无法把这个网络拆分成“只出不进”或“只进不出”的孤立区块。矩阵是“不可约（Irreducible）”的。）
  3. 图 $G$ 是强连通的 (Strongly connected)
  4. 对于任意划分 $\{\mathcal{I}, \mathcal{J}\}$，总存在从 $\mathcal{I}$ 指向 $\mathcal{J}$ 的边（想象你用剪刀把这个网络随便剪成两半（$\mathcal{I}$ 和 $\mathcal{J}$），你总能找到至少一条通信链路是跨越这条剪切线的。）

在文献中，通常通过2或4来定义矩阵的不可约性。

本质上，2 和 4 说的完全是同一件事，只不过一个是穿了“矩阵”的马甲，一个是穿了“集合”的马甲。

假设存在一个划分 $\{\mathcal{I}, \mathcal{J}\}$，使得从 $\mathcal{I}$ 到 $\mathcal{J}$ 没有任何边（即对于所有的 $i \in \mathcal{I}, j \in \mathcal{J}$，邻接矩阵的元素 $a_{ij} = 0$）。我现在施展一个置换矩阵 $P$。我把所有属于集合 $\mathcal{I}$ 的节点，全部强行排在矩阵的后面（右下角），把属于 $\mathcal{J}$ 的节点排在前面（左上角）。

经过 $PAP^\top$ 变换后，新的矩阵左下角那个区块，恰好代表“从 $\mathcal{I}$ 到 $\mathcal{J}$ 的边”。因为我们假设了这些边不存在，所以左下角将出现一个巨大的零矩阵（$A_{\mathcal{I}\mathcal{J}} = 0$）。这就是分块三角阵。

带自环的情况

前面我们要求网络中所有人都能互相通信（强连通），这在很多实际系统中要求太高了。 在无线传感器网络中，并不是所有传感器都需要互相通信。很多时候，我们只需要保证所有节点采集到的数据，最终都能沿着某条路径汇聚到同一个“基站 (Base Station / Data Sink)”。这就是节点 $j$ 的全局可达性 (Global reachability)。

现在我们退一步，它只关心某一个特定的节点 $j$。

既然我们只关心到达节点 $j$ 的路径，我们在看矩阵求和 $\sum_{k=0}^{n-1} A^k$ 时，就不需要看整个矩阵了，只需要看第 $j$ 列。因为在邻接矩阵中，第 $j$ 列的元素代表了“从其他各个节点出发，到达节点 $j$ 的路径情况”。如果这一列全为正数，说明大家都有一条通往 $j$ 的路。

同时，如果有一条长度为 $k$ 的路，且路上有自环，那么必定也存在长度为 $k+1, k+2\dots$ 的路。举个例子，想象你要从 A 走到 B，原本最快需要 3 步。但是如果你或者中间节点有一个“自环”，这意味着你可以在原地“踏步”停留一回合。所以，你也可以选择花 4 步、5 步甚至 100 步到达 B（多出来的步数全在原地转圈消耗掉了）。

如果网络中每个节点都有自环，我们就再也不用辛苦地去把 $A^0 + A^1 + \dots + A^{n-1}$ 全部加起来了！ 因为既然最长的不重复路径不会超过 $n-1$ 步，而有了自环，任何短于 $n-1$ 步的路径，都可以通过“原地踏步”硬生生凑成恰好 $n-1$ 步。因此，我们只需要看 $A^{n-1}$ 这一个矩阵就够了！

  • 强连通 $\iff$ $A^{n-1} > 0$ （此时 $A$ 被称为素矩阵/本原矩阵 Primitive Matrix）。

  • 节点 $j$ 全局可达 $\iff$ $A^{n-1}$ 的第 $j$ 列全是正数。

本原矩阵的图论特征( primitive matrices)

设 G 是一个有 n ≥ 2 个节点的带权有向图，并且具有带权邻接矩阵 A。以下两个命题是等价的：

  • 一个有向图 $G$ 是强连通且非周期的 (Aperiodic)
  • 它的邻接矩阵 $A$ 是素矩阵 (Primitive)（即存在某个足够大的整数 $k$，使得 $A^k > 0$ 全为正数）。

证明：现在我们证明如果这个图一定强连通，且非周期，那么它是素矩阵 ($A^k > 0$)。

为了证明这个定理，引入了 Frobenius 数（弗罗贝尼乌斯数）。

假设你只有面值为 $3$ 元和 $5$ 元的硬币。你能凑出哪些金额？ 你可以凑出 $3, 5, 6(3+3), 8(5+3), 9(3+3+3), 10(5+5)\dots$ 但是，你死活凑不出 $1, 2, 4, 7$。

一旦越过了 $7$ 这个门槛，从 $8$ 开始的所有整数（$8, 9, 10, 11\dots$），你全都能用 $3$ 和 $5$ 凑出来！这里的 $7$ 就是 Frobenius 数（最大不可表示整数）。

能实现“凑出所有大数”的前提是，这些硬币的面值必须是互素的 (Coprime)，即它们的最大公约数 (GCD) 必须是 $1$。如果你只有 $5$ 元和 $10$ 元的硬币，它们的公约数是 $5$。那你永远只能凑出 $5$ 的倍数，永远凑不出 $12$。你被“困”在了 $5$ 的周期里。

进一步地推广这个定理，硬币 = 环的长度：在强连通图中，存在很多个闭合的环（Cycles）。假设这些环的长度分别是 $\ell_1, \ell_2, \dots, \ell_N$。

如果图是“非周期的 (Aperiodic)”。在图论中，这意味着图中所有环的长度的最大公约数是 1。这完美契合了 Frobenius 定理的互素条件。我现在想从节点 $i$ 走到节点 $j$，并要求步数恰好是某个很大的数 $m$。我该怎么走？

  • 首先，因为图是强连通的，我肯定能找到一条路从 $i$ 出发，去把图中所有的环都“逛”一遍，最后走到 $j$。（假设这部分基础路线长度是固定值）。

  • 在逛的过程中，我可以选择在长度为 $\ell_1$ 的环上多绕几圈，或者在长度为 $\ell_2$ 的环上多绕几圈。

  • 因为 $\ell_1, \ell_2, \dots, \ell_N$ 是互素的（硬币面值），根据 Frobenius 定理，只要我需要的额外步数足够大，我就一定能用这些环的长度“凑”出任意想要的步数！

因此，对于任意的节点对 $(i, j)$，只要步数 $m$ 超过某个阈值 $k(i, j)$，从 $i$ 到 $j$ 长度为 $m$ 的路径就必然存在，即 $(A^m)_{ij} > 0$。我们取所有节点对中最大的那个阈值作为全局的 $k$。当矩阵乘到 $A^k$ 时，所有的元素就都大于 0 了。

举个例子：

image-20260501180556728

图中有两个明显的环，一个长度是 $2$（左边的两节点互指），一个长度是 $3$（右边的三角形）。他们的GCD是1，因此它是一个非周期图。假设保底路径 $\gamma$ 走完要 10 步。现在系统要求你必须走 105 步才能到终点。怎么办？很简单，保底走 10 步，剩下 95 步的配额，你可以在左边绕 1 圈（耗费 2 步），在右边绕 31 圈（耗费 93 步），完美凑齐。

反推：现在我们要证明反面：如果一个矩阵是素矩阵 ($A^k > 0$)，那么这个图一定强连通，且非周期。**

既然存在某个 $k$ 使得 $A^k > 0$，说明 $k$ 步之内任何人都能到任何人那里。这直接满足强连通的定义。因为图是强连通的，所以每个节点必定至少有一条出边（你总能走到下一个地方，不存在死胡同）。

同时，$A^{k+1} = A A^k$：$(A^{k+1})_{il} = \sum_{h=1}^n a_{ih} (A^k)_{hl} \ge a_{ij} (A^k)_{jl} > 0$

这个式子的物理意义是：假设在第 $k$ 步时，网络已经实现了“全覆盖” ($(A^k)_{jl} > 0$ 全为正)。 那么在第 $k+1$ 步会发生什么？因为节点 $i$ 必定有一条路通向某个邻居 $j$ ($a_{ij} > 0$)，而邻居 $j$ 在剩下的 $k$ 步里能到达所有地方 ($(A^k)_{jl} > 0$)。 所以，$i$ 走 $k+1$ 步也一定能到达所有地方！

从而得到了既然 $A^k > 0$，那么 $A^{k+1} > 0$，紧接着 $A^{k+2} > 0, A^{k+3} > 0 \dots$ 一旦矩阵的次幂变成了全正数，它就永远保持全正数！

在数学上，如果一个集合包含了所有足够大的连续整数，那么这些数的最大公约数 (GCD) 只能是 1。从而就证明了它强联通且非周期。

谱图论的元素（spectral graph theory）

前面我们一直在研究矩阵 $A$ 的零/非零结构（可约/不可约），现在我们要研究 $A$ 的特征值 (Eigenvalues)，特别是它的谱半径 (Spectral Radius, $\rho(A)$)。

膨胀决定谱半径的上界与下界

回顾前面的知识，对于一个非负矩阵 $A$，它的谱半径 $\rho(A)$ 是它所有特征值绝对值中的最大值。

很多时候，矩阵 $A$ 很大，直接求特征值太难了。下面提供了一种极其巧妙的方法，通过寻找一个测试向量 $x$，来给出谱半径的上下界。

假设 $x$ 是一个非负向量（代表网络中每个节点的某种初始能量）。

  • (i) 下界：如果你发现经过一轮状态更新 ($Ax$)，每个节点的能量都至少变成了原来的 $r_1$ 倍（即 $r_1 x \le Ax$），那么这个系统的谱半径 $\rho(A)$ 肯定 $\ge r_1$。
  • (ii) 上界：反过来，如果更新一轮后，每个节点的能量最多变成原来的 $r_2$ 倍（即 $Ax \le r_2 x$），那么谱半径 $\rho(A)$ 肯定 $\le r_2$。
  • (iii) 严格界限：如果矩阵是不可约的 (Irreducible)（网络强连通），并且上面的不等式不是处处相等，那么谱半径的界限就是严格的不等号 ($<$)。

举个例子：假设我们有一个网络，节点 1 和节点 2。它们的传递规则矩阵 $A$ 如下：

物理意义：

  • 节点 1 每次保留自己 2 倍的能量，并从节点 2 吸收 1 倍的能量。
  • 节点 2 每次保留自己 3 倍的能量，并从节点 1 吸收 1 倍的能量。

现在，我们随便给这个网络注入一个初始能量向量 $x$，比如大家都给 1 个单位的能量$ x = \begin{bmatrix} 1 \\ 1 \end{bmatrix} $

现在，我们来观察每个节点能量膨胀的倍率：

  • 节点 1 的能量从 1 变成了 3，膨胀了 3 倍。
  • 节点 2 的能量从 1 变成了 4，膨胀了 4 倍。

根据引理：

  • 下界 $r_1$：所有节点中，膨胀倍率最小的那个。所以 $r_1 = 3$。（因为每个节点至少都膨胀了 3 倍，即 $3x \le Ax$）。
  • 上界 $r_2$：所有节点中，膨胀倍率最大的那个。所以 $r_2 = 4$。（因为每个节点最多只膨胀了 4 倍，即 $Ax \le 4x$）。

整个网络系统的固有“生长速度”（即谱半径 $\rho(A)$）一定介于最慢的节点和最快的节点之间，即：

来求解特征值验证一下，解方程 $\det(A - \lambda I) = 0$：

引理证明：

1.证明 (i) 的下界：反证法与极限

假设谱半径没那么大（$\rho(A/r_1) < 1$）。如果矩阵的谱半径严格小于 1，那么在线性代数中有一个铁律：这个矩阵的无数次幂一定会趋于全零矩阵（$\lim_{k \to \infty} (A/r_1)^k = 0$）。这就意味着，任何初始能量 $x$ 经过无数次迭代后都会衰减到 0。

但是你的前提是 $r_1 x \le Ax$，也就是每次迭代，能量都在以 $r_1$ 的倍率增长（或保持不变）。它越乘越大，怎么可能衰减到 0？矛盾！所以 $\rho(A)$ 必须 $\ge r_1$。

2.证明 (ii) 的上界：佩龙-弗罗贝尼乌斯定理 (Perron-Frobenius Theorem)

定理借用：对于非负矩阵 $A$，PF 定理保证了它一定存在一个非负的左特征向量 $w^\top \ge 0$，对应于最大的特征值（也就是谱半径 $\rho(A)$）。即 $w^\top A = \rho(A) w^\top$。

把前提条件 $Ax \le r_2 x$ 的两边，同时左乘这个神奇的 $w^\top$：

把 $w^\top A$ 替换成 $\rho(A) w^\top$：

消去：因为 $w^\top x > 0$（一个是左特征向量，一个是正向量的内积），两边同时约掉 $w^\top x$，直接得出 $\rho(A) \le r_2$。

谱半径的单调性

(i) 如果矩阵 $A$ 的每一个元素都小于等于矩阵 $A’$（即 $A \le A’$），那么 $\rho(A) \le \rho(A’)$。（换言之，如果你在通信网络中增加了一条边（把某个 0 变成了正数），或者增强了某条链路的权重，那么整个网络的“连通强度”（谱半径）一定会上升或至少不降。）**

(ii) 如果网络 $A’$ 是强连通的（不可约），只要你哪怕只增强了一条边（$A \neq A’$），谱半径就会严格增大 ($\rho(A) < \rho(A’)$)。

证明 $A \le A’ \implies \rho(A) \le \rho(A’)$：

PF 定理告诉我们，对于非负矩阵 $A$，它的谱半径 $\rho(A)$ 对应着一个非负的特征向量 $v \ge 0$。那么，$\rho(A)v = Av$。 既然假设了 $A \le A’$，而且 $ v $ 里的元素都是非负的，那么直接乘上去，不等号方向不变：

把 $\rho(A)$ 当作 $r_1$，把 $ v $ 当作测试向量 $x$。因此，直接得出结论 $\rho(A) \le \rho(A’)$。

出度数（Row Sums）决定谱半径

在图论中，$A \mathbf{1}_n$ 的物理意义极其明确：它就是矩阵 $A$ 的行和 (Row Sums)。对于有向图来说，它就是每个节点的出度 (Out-degree)，也就是一个节点向外连接的权重总和。

1. 谱半径被“最大度数”和“最小度数”死死夹住：$\min(A\mathbf{1}_n) \le \rho(A) \le \max(A\mathbf{1}_n)$

物理直觉：一个网络的整体信息扩散能力（$\rho(A)$），不可能超过网络中最活跃那个节点（交际花，度数最大）的传播能力；同时，也不可能低于最孤僻那个节点（社恐，度数最小）的传播能力。

2. 如果$\min(A\mathbf{1}_n) < \max(A\mathbf{1}_n)$，那么以下陈述等价：

  • 对于每个满足 $e_i^{\top}A\mathbf{1}_n = \max(A\mathbf{1}_n)$ 的节点 $i$，存在一条从节点 $i$ 到每个满足 $e_j^{\top}A\mathbf{1}_n < \max(A\mathbf{1}_n)$ 的节点 $j$ 的有向路径 (directed walk)；用人话翻译：
  • $\rho(A) < \max(A\mathbf{1}_n)$。

对定理2的解释：

$A\mathbf{1}_n$：这是矩阵的行和向量，代表每个节点的出度 (Out-degree)，也就是每个节点向外连接的“通道数量”或“能量输出功率”。

$\max(A\mathbf{1}_n)$：全网最大的出度。我们可以把它理解为网络里的最高功率。

$e_i^{\top}A\mathbf{1}_n = \max(A\mathbf{1}_n)$：节点 $i$ 的出度等于全网最大值。所以，节点 $i$ 就是“首富”。其中$e_i$ 被称为第 $i$ 个标准基向量 (Standard Basis Vector)，只有第 $i$ 个位置是 1，其他所有位置全是 0。例如$e_1^\top = [1, 0, 0]$。它的作用是抽样节点$i$的出度。

$e_j^{\top}A\mathbf{1}_n < \max(A\mathbf{1}_n)$：节点 $j$ 的出度小于最大值。所以，节点 $j$ 就是“平民（普通节点）”，它们的能量输出功率存在“缺口”。

“对于网络中的每一个‘富豪（超级节点 $i$）’，都必须存在一条有向路径，能够通向网络中的每一个‘平民（普通节点 $j$）’。”

只有当这个条件满足时，整个网络的谱半径 $\rho(A)$ 才会严格小于最大出度（即 $\rho(A) < \max$）。

举个例子来看：

image-20260501184830893

对于左边的图，分为左右两排。左边每个节点都连向右边 3 个节点，右边每个节点也都连向左边 3 个节点。所有人的度数（行和）都精准地等于 3。没有高低差，能量无处泄露。因此，最小度数 = 最大度数 = 3，它的谱半径 $\rho(A_{K_{3,3}})$ 严格等于 3。

对于右边的图，中间的节点上下左右都有邻居，度数为 4（最大行和）；边缘的节点只有 3 个邻居，度数为 3；四个角落的节点只有 2 个邻居，度数为 2（最小行和）。因为这是一个连通图，中心节点（度数 4）的信息一定会顺着网格“泄露”到边缘和角落（度数 2 或 3）。同时，这个网格网络的谱半径，在 $2$ 和 $4$ 之间，即 $2 < \rho(A) < 4$。

行次随机矩阵 (Row-substochastic matrix)

定义：什么是“行次随机矩阵”？

  1. 不产生新能量：所有行的和最多为 1（$A\mathbf{1}_n \le \mathbf{1}_n$）。这意味着网络中的每个节点，向外传递的能量（或概率、水流）总和，绝对不会超过它自身拥有的量。
  2. 至少有一个“漏洞”：至少有一行的和严格小于 1（$\exists\ i,\ e_i^\top A\mathbf{1}_n < 1$）。这意味着网络中至少存在一个节点，它在传递能量时存在“损耗”或“泄露”。

对于行次随机矩阵，会在以下时候收敛 (Convergent)（收敛：随着时间推移 $A^k \to 0$，即系统能量最终全部耗散，等价于谱半径 $\rho(A) < 1$））：

  • 当且仅当 $G$ 中存在从每个出度为 1 的节点到某个出度小于 1 的节点的有向路径时，$A$ 是收敛的；
  • 如果 $A$ 是不可约的 (irreducible)，那么 $A$ 是收敛的。