Korean, Edit

图论

推荐阅读：【数学】【数学目录】(https://jb243.github.io/pages/764)

1. 基础知识

2. 应用程序

1.基础知识

⑴ 图的组成部分

① V：节点

② E：边缘

③ G：图表

④ V(G) = {v₁,…,v_n}

⑤ v_i ~ v_j：边e_ij连接顶点v_i、v_j时。

⑷ 节点v的度数：与节点v相连的边的条数，即deg(v)。

① deg(v_i) = Σ_vi~vj 1

② δ(G)为G中节点的最小度，Δ(G)为G中节点的最大度。

③ Σ deg(vi) = 2

电子(G)

④ 若图的所有节点度数相同，则该图是正则图。

⑤ 欧拉图的节点度数为偶数。

⑸ 简单图和完整图

① 简单图：任意两个节点之间最多存在一条边的图，且不允许存在自环（连接节点到自身的边）。

图 1. 简单图

② 完全图：所有节点都由唯一边连接的图。

图 2. 完整图表

○ 强连接（= 不可约）

○ 图中任何节点 i 都可以到达任何其他节点 j 的状态。

○ 如果 j 从 j ∀i, j 可达，则马尔可夫链是不可约的。

○ 完整图中的边数为 _NC₂ = N(N-1) / 2。

⑹ 子图：若 V(H) ⊆ V(G) 且 E(H) ⊆ E(G)，则 H 是 G 的子图。

① 如果 V(H) 的两个顶点相邻当且仅当它们在 G 中相邻，则子图 H 是 G 的诱导子图。

②派：图的完全子图。

③ 步行：类似 v₀ → v₁ → … → v_m 的路径，由边 v₀v₁、v₁v₂、…、v_m-1v_m 连接。

○ v₀ 称为初始顶点，v_m 称为最终顶点。

○ 步行的边数称为长度。

④ 路径：所有节点都不同的行走。

⑤ 循环：v₀ = v_m 的步行。

⑥ 森林：不包含环的图。

⑦ 树：相连的森林

⑧ 周期：节点i的周期是节点i到自身的所有路径的最大公约数。

○ 示例：如果两个节点 A 和 B 通过两条边连接，使得 A = B，则每个节点的周期为 2。

⑨ 非周期：所有节点的周期为1。

○ 对于不可约马尔可夫链，如果一个状态是非周期的，则所有状态都是非周期的。

○ 示例：每个节点都有一条返回自身的路径的步行是非周期性的。

⑩ 常规

○ 正则 ⊂ 不可约

○ 对于某个自然数 k，转移矩阵 M 的 k 次方的所有元素 M^k 均为正（即非零值）。

⑺ 图表类型

①无向图：有无向边的图

② 有向图：有向边的图

③ k 分图：如果其顶点集允许划分为 k 类，且同一类的顶点不相邻。

⑻ 网络的中心性

① 程度中心性表明人们拥有许多社会关系。

② 紧密中心性表明谁处于社交网络的核心。

③介数中心性描述的是连接社交圈的人。> ④ 网络中有影响力的人的特征向量中心性较高。

⑼ 邻接矩阵：表示为A。

① 定义：当节点数为n时，n×n邻接矩阵定义为，A_i,j = 1（如果v_i ~ v_j），A_i,j = 0（否则）

图 3. 邻接矩阵示例

② 图的顶点集上的实值函数，f: V → ℝ

图 4. 实值函数 f 的示例

③ 以下公式成立

④ 对称归一化邻接矩阵： × = D^-1/2AD^-1/2 （参见 D_ii = d(v_i)）

⑽ 关联矩阵：表示为∇。

① 无向图的关联矩阵定义为，B_i,j = 1（如果顶点 v_i 与边 e_j 关联），B_i,j = 0（否则）

图 5. 关联矩阵示例

②有向图的关联矩阵

③ 节点为行、边为列（例如图 5）和边为行、节点为列（例如图 6）两种情况。

⑾ 拉普拉斯矩阵

① 概述

○ 定义： L = ∇^T∇ = D - A （参见 D_ii = d(v_i)）

○ 多重性：图中连通分量的数量

图 6. 拉普拉斯矩阵示例

○ 这里，∇如下：

受保护_0

② 拉普拉斯矩阵的修正

○ 归一化图拉普拉斯： L_n = D^-1/2LD^-1/2 = I - D^-1/2AD^-1/2。对称，半定正

○ 马尔可夫链转移矩阵： L^t = D^-1A

○ 随机游走图拉普拉斯： L_r = D^-1L = I - L_t = D^-1/2L_nD^1/2

③ 特征 1. L 的特征值为 0。 L1_n = 0

○ 如果有 k 个不连通图，则有 k 个特征值为 0。

○ 特征值越接近0，图的连通性越强。

○ 费德勒向量：λ₁ = 0之后第二小的特征值对应的特征向量，代表图的整体结构。

④ 特征2. (Lf)(v_i) = Σ_vj~vi (f(v_i) - f(v_j))：参见图。 4。

⑤ 特征 3. L 是对称且半正定的。

○ 二次形式：f^TLf = Σ_{ei,j, i < j} (f(v_i) - f(v_j))² = (1/2) Σ_ei,j (f(v_i)) - f(v_j))² ≥ 0

○ 在图4的例子中，f^TLf = 9.27

○ 也就是说，L 有 n 个非负实值特征值。

○ 当使用矩阵 p 代替 f 时，表示为 tr(pᵀLp)。

⑥ 特征 4. 给定 Y = [y₁ y₂ ⋯ y_m] ∈ ℝ^k×m，

○ tr(YTLY) = Σei,j

yi - yj

2

⑦ 特性 5. 瑞利商

○ λ₂，费德勒值（代数连通性），表示微分或分离值所需的能量。

○ 较大的 λ₂ 表明数据难以分离，表明整体结构连接良好。

○ 较小的 λ₂ 意味着数据很容易分离，表明存在弱连接结构或聚集成不同的组。

⑧ 应用1. 无向加权图的拉普拉斯算子

⑨ 应用 2. 谱聚类 (ref)

○ 原问题

○ 它试图在图中找到“最小切割”：在标准化簇体积的同时，具有最小簇间边权重的顶点划分。

○ 聚类（图划分）的关键思想是使不同簇之间的连接（即跨簇的边权重之和）变小，同时防止某些簇变得太小的不平衡分裂。

○ 如果我们只最小化集群间连接（最小切割），我们通常会得到一个简单的分区，只是剥离一些节点。因此，我们改为最小化归一化切割，即按簇大小（连接性/关联性）对切割进行归一化。

○ 切削的定义

○ 体积的定义

○ 2簇优化问题

○ 多集群优化问题

○ 相当于找到满足以下条件的簇标签 X ∈ {0,1}^N×K 的 one-hot 编码

○ 使用拉普拉斯矩阵的解决方案

○ 问题定义

○ 条件 y^TDy=1 是必要的原因：如果没有这个条件，则存在一个平凡解 y=0，并且对于任何非零 y，存在一个 0≤c<1 的标量 c，使得 cy 使目标函数任意小。»» ○ 需要条件 y^TD1=0 的原因：该条件对于 y≠1（正交性）是必要且充分的。如果没有它，目标函数的最小值始终为 0，并且始终在 y=1 处实现（通过拉格朗日乘子 的方法）。

○ 在原来的谱聚类问题中，放宽one-hot约束并添加条件X^TDX = I使其等价于该解。

○ 步骤1： 计算给定的n个数据点之间的距离，创建一个n × n的邻接矩阵A。经常使用高斯核。

○ 步骤2： 根据邻接矩阵，计算拉普拉斯矩阵： L_n 或 L_r 也可以使用。

○ 步骤3： 计算拉普拉斯矩阵的k个最小特征值对应的特征向量矩阵 W = [ω₂, ···, ω_k] ε ℝ^n×k 。排除 ω₁ = 1，它对应于 λ₁ = 0，因为它是微不足道的。

○ 步骤 4： 将 n 个数据点自然嵌入到 k 个维度中： Y = W^T = [y₁, ⋯, y_n]，每个列向量代表嵌入的数据点。

○ 步骤5： 对Y的列向量进行聚类，例如K-means聚类。

⑩ 应用3. 拉普拉斯矩阵可以用作傅里叶变换算子（例如，G-FuNK）

⒀ 距离：两个节点之间最短路径的长度。如果不存在这样的路径，则距离定义为 ∞。

⒁ 聚类系数：若特定节点的度为 k_i，且与该节点相连的周围节点之间的边数为 e_i，则：

① 例如，如果 A 与 B、C、D 连接，并且还有附加边 B-C 和 C-D，则对于 A，e_i = 2，k_i = 3，C_i = 2 / 3。

② k_i (k_i - 1) / 2：周围节点之间可以形成的最大边数。

③ C_i 的值在 0 到 1 之间，值接近 1 表明周围节点是全连接的。

2.应用

⑴ 鸽巢原理

⑵ 唯一图的数量取决于节点数量：几乎完美遵循指数函数。

⑶ Dijkstra 和 Floyd 算法

⑷【子图数量统计算法】(https://jb243.github.io/pages/1892#:countingisland)

⑸ 【信仰的力量】(https://jb243.github.io/pages/869)

⑹ 社交网络理论或六度分离

① 地球上任意两个人之间通过不超过六个中介联系起来的理论。

② 证明：如果一个人平均认识100人，那么经过六步，100⁶ = 10亿，得出类似的结论。

⑺ 佩伦-弗罗贝尼乌斯定理

① 定理1. 如果一条带有转移矩阵P的有限马尔可夫链是强连通的，则恰好存在一个平稳分布q。» ○ 稳态分布满足 Pq = q。

○ 示例：如果 P = I（单位矩阵） ε ℝ^2×2，则它是可约的，因此对于所有 x ε [0, 1]，存在无穷多个 (x, 1-x) 形式的平稳分布。

② 定理2. 如果一个具有转移矩阵P的有限马尔可夫链是强连通且非周期的，则称为遍历马尔可夫链并满足：

○ P_ij：从节点 j 转移到节点 i 的概率。 Σ_i P_ij = 1。

○ 2-1. 当 k → ∞ 时，矩阵 P^k 收敛为列全部等于 q 的矩阵；即，P_ij(k) 收敛于 q_i （对于任何 i 和 j），因为 k → ∞

○ 2-2. 对于任何初始状态 x₀ 来说，马尔可夫链 {x_k} 收敛到 q，因为 k → ∞

○ 示例：如果 P=((0,1),(1,0))，则它是周期性的（周期=2）。因此，存在唯一的平稳分布 π=(0.5,0.5)，但 $\lim_{k\to\infty} p(k)$ 不会收敛到单一极限，而是分裂成两个子序列（例如，$p^{\text{even }k}=(1,0)$ 和 $p^{\text{odd }k}=(0,1)$）。

⑻ Google 的 PageRank 算法

① 步骤1. 将网页表示为图，并将其表示为马尔可夫过程转移矩阵P。

② 步骤2. 瞬移：对于汇聚节点，强制分配到其他页面的转移概率为1/n：P → P’。

③ 步骤 3. P’’ = (1 - α) P’ + (α / n) 1。

○ 这里，1 是指用 1 填充的 n × n 矩阵。

○ 虽然 P’ 不保证是正则的，但 P’’ 始终保证是正则的。

○ P’’ 是由 Google 创始人谢尔盖·布林 (Sergey Brin) 和拉里·佩奇 (Larry Page) 定义的马尔可夫链。

④ 步骤 4. 搜索稳态向量 x 使得 P’‘x = x。

○ 由于 P’’ 是规则的，因此它是强连通的，这确保了唯一稳态的存在。

○ 此时的状态转换概率可以视为推荐页面的重要性。

⑤ 个性化PageRank：使用用户输入修改隐形传态分布（或图/候选集），产生用户特定的平稳分布。

⑼ 四色定理

① 任何地图最多可以用四种颜色着色，确保相邻的两个区域没有相同的颜色。

② 通过使用计算机验证四色定理在所有情况下都成立来证明该定理。

⑽ 欧拉路径问题或柯尼斯堡桥问题

① 当且仅当存在 0 或 2 个奇数度的节点时，图中才存在一条只经过每个节点一次的欧拉路径。

② 如果有 2 个节点的度数为奇数，则其中一个为起点，另一个为终点。

③ 没有一条路径能够恰好穿过柯尼斯堡的所有七座桥梁一次。

⑾ 拉姆齐理论

① 在任何足够大的图中，必须存在某种结构（例如熟人的完整图或陌生人的子图）。

② R(s, t)：保证存在s个陌生人的子图或t个熟人的子图的最小节点数。

③ 定理1. R(3, 3) = 6：任意6个人中，要么有3个共同的朋友，要么有3个共同的陌生人。这可以通过计算可能性来证明。

④ 定理 2. R(3, 3, 3) = 17。> ⑤ 定理 3. R(3, 3, 4) = 30。

⑥ 定理4. R(s, t)的递推关系：R(s, t) ≤ R(s-1, t) + R(s, t-1)。

⑦ 定理 5. R(s, t) 上限的存在性：通过 R(s, t) 的递推关系和数学归纳法证明（ref）。

⑧ 定理 6. R_k(s₁, s₂, …, s_k) ≤ R_k/2(R(s₁, s₂), R(s₃, s₄), …, R(s_k-1, s_k))。

⑿ 舒尔定理

① 对于任意 k ≥ 2，存在 n > 3，使得在 k 着色下，总存在满足 x + y = z 的 (x, y, z)，在 {1, 2, …, n} 中以相同方式着色。通过拉姆齐理论证明。

② 这与费马大定理相关，揭示了 (x, y, z) 的存在性，其中 x^m + y^m = z^m (mod p)。

⒀ Erdős–Rényi 随机图

① 即使有随机连接节点的简单规则，在一定阈值下也会出现非常大的图。

输入：2024.10.01 19:44