参数化维度传播各向异性

组合优化问题中的相变

第 0 章图表简介

接下来的三节简要介绍图论和图算法。 第一个涉及基本定义和概念，并介绍一些图问题。 第二个专门讨论一些基本的图算法。 在第三部分中，我们将讨论随机图，这在整个课程中至关重要。

让我们首先提到一些与图论相关的书籍。 所有这些都远远超出了我们需要的有关图表的一切：

• Gary Chartrand，图论入门，多佛出版社。 公司，纽约，1985 年。
  
  这本小平装书包含了关于图论的精彩、易于阅读的介绍。 每一章都基于“现实世界”的示例，这些示例映射到图形问题。 对于那些希望更多地了解图形而不是通过阅读一本困难的数学书的人来说，这是一本好书。

• Béla Bollobás，现代图论，Springer，纽约，1998 年。
  
  本书由一位领先的图论学家撰写，涵盖第一部分和第三部分（以及更多内容）。 它非常好且完整，但在数学上相当困难。

• Robert Sedgewick，C 语言算法：图算法，Addison Wesley，波士顿，2002 年。
  
  本书收集了许多图算法，包括对其正确性的广泛描述和证明。

1 基本概念和图问题

1 柯尼斯堡图和欧拉图的桥梁

图论方法的最早使用可能可以追溯到 18 世纪。 此时，柯尼斯堡镇普雷格尔河上有七座桥梁。 长期以来，人们一直在思考这样一个问题：是否可以通过每座桥穿过小镇一次，最后回家？ Leonhardt Euler (1707–1783) 在 1736 年解决了这个问题，将其映射到图问题并求解任意图 [2]，即。例如，对于任意城镇、城市地图等。 在柯尼斯堡的例子中，他不得不得出一个有点令人失望的结果：不存在这样的循环。

图1显示了普雷格尔河，柯尼斯堡位于两岸和两个岛屿。 还显示了七座桥梁。 下面给出了到图的映射。 每个河边、岛屿和桥梁都被分配一个顶点，绘制为圆，两个顶点通过边缘连接，绘制为一条线，如果它们也物理连接。 为了给出更精确的描述，我们必须介绍基本的图论术语，这些术语总结在下面的定义中。

[htb]

柯尼斯堡的桥梁及其图形表示。 顶点用圆表示，边用线表示。

基本定义：

• （无向）图 $G=(V,E)$ 由其顶点 $i\in V$ 及其无向边 给出$\{i,j\}\in E\subset V^{(2)}$。 请注意，$\{i,j\}$ 和 $\{j,i\}$ 表示相同的边。

• order $N=|V|$ 计算顶点数。

• size $M=|E|$ 计算边的数量。

• 如果$\{i,j\}\in E$，则两个顶点$i,j\in V$相邻/相邻。

• 边$\{i,j\}$与其末端顶点$i$和$j$重合。

• 顶点$i$的度$\mathrm{deg}(i)$等于相邻顶点的数量。 零度的顶点称为孤立。

• 如果$V^{\prime }\subset V,E^{\prime }\subset E$，图$G^{\prime }=(V^{\prime },E^{\prime })$是$G$的子图。

• 如果$V^{\prime }\subset V$和$E^{\prime }=E\cap {(V^{\prime })}^{(2)}$，图$G^{\prime }=(V^{\prime },E^{\prime })$是$G$的导出子图，即。即，$E^{\prime }$ 包含来自 $E$ 的连接 $V^{\prime }$ 中两个顶点的所有边。

• 如果子图 $G^{\prime }=(V^{\prime },E^{\prime })$ 的形式为 $V^{\prime }=\{i_0,i_1,\mathrm{\dots },i_l\}$、$E^{\prime }=\{\{i_0,i_1\},\{i_1,i_2\},\mathrm{\dots },\{i_{l-1},i_l\}\}$，则它是 $G$ 的 路径。 路径的长度为$l=|E^{\prime }|$。 $i_0$和$i_l$称为端点。 该路径从 $i_0$ 到 $i_l$，反之亦然。 有人说$i_0$和$i_l$通过路径连接。 请注意，在路径内，每个顶点（可能除了端点）仅被“访问”一次。

• 带有 $i_0=i_l$ 的路径，i。即，闭合路径称为循环。

• 一系列边 $\{i_0,i_1\}$、$\{i_1,i_2\},\mathrm{\dots },\{i_{l-1},i_l\}$ 称为 walk。 在一次行走中，某些顶点或边可能会出现多次。

• 具有成对不同边缘的行走称为轨迹。 因此，踪迹也是 $G$ 的子图。

• 电路是具有重合端点的路径，即。即，一条封闭路线。 （注意：循环是电路，但反之则不然，因为电路可能多次经过同一个顶点）。

• 如果所有顶点对$i,j$都通过路径连接，则图$G$是连通的。

• 如果图 $G^{\prime }=(V^{\prime },E^{\prime })$ 是 $G$ 的连通诱导子图，并且没有边，则它是 $G$ 的 连通分量在 $E$ 中将 $V^{\prime }$ 的顶点与 $V\setminus V^{\prime }$ 中的顶点连接起来。

• 补图 $G^C=(V,E^C)$具有边集$E^C=V^{(2)}\setminus E=\{\{i,j\}\mid \{i,j\}\notin E\}$。 因此，通过用边连接 $G$ 中不相邻的所有顶点对并断开 $G$ 中相邻的所有顶点对，从 $G$ 获得它。 。

• 加权图 $G=(V,E,\omega )$是具有边权重$\omega :E\to ℝ$的图。

Example 1.1.

图表 我们考虑如图1所示的图表。 可以写成 $G=(V,E)$

$V$ $=$ $\{A,B,C,D,a,b,c,d,e,f,g\}$

$E$ $=$ $\{\{A,a\},\{A,f\},\{A,d\},\{A,f\},\{A,g\},\{B,a\},\{B,b\},\{B,c\},$

$\{C,e\},\{C,f\},\{C,g\},\{D,c\},\{D,d\},\{D,e\},\}.$

因此，图具有 $|V|=11$ 个顶点和 $|E|=14$ 个边。 由于 $\{D,e\}\in E$，顶点 $D$ 和 $d$ 相邻。 顶点 $d$ 的度数为 deg$(d)=2$，而顶点 $A$ 的度数为 5。

例如，$G^{\prime }=(V^{\prime },E^{\prime })$ 与 $V^{\prime }=\{A,g,C,e,D\}$ 和 $E^{\prime }=\{\{A,g\}$、$\{g,C\}$、$\{C,e\}$、$\{e,D\},\}$是从$A$到$D$的路径。 $G$ 已连接，因为所有顶点都通过路径连接到所有其他顶点。 边序列$\{B,c\},\{c,D\},\{D,c\}$是一条行走，但它并不对应于一条路径，因为有些顶点被访问了两次。 边序列 $\{A,b\}$、$\{b,B\}$、$\{B,a\}$、$\{a,A\}$、$\{A,g\}$、$\{g,C\}$、$\{C,f\}$、$\{f,A\}$是一条路径，特别是它是一条电路。

回到柯尼斯堡人的问题，用图论语言表述，他们面临以下问题：

欧拉电路： 给定一个图，是否有一个电路仅使用每个边一次？

欧拉证明的令人惊奇的一点如下：欧拉回路的存在——显然是一个全局对象——可以通过纯粹的局部属性来决定，在这种情况下是顶点度数。

定理： 当且仅当所有顶点度数都是偶数时，连通图 $G=(V,E)$ 是欧拉图（具有欧拉循环）。

Proof 1.2.

$(\to )$ 这个方向是微不足道的。 遵循欧拉回路，输入的每个顶点也会被留下，每次都使用以前未访问过的边。 因此所有度数都是均匀的。

$(\leftarrow )$ 另一个方向就有点难了。 对于只有偶数顶点度数的任意图，我们将通过图大小 $M$ 的归纳来证明这一点。

该定理对于 $M=0$（一个孤立的顶点）和 $M=3$（三角形）显然是正确的，它们是最简单的偶数图。

现在我们取任何$M>0$，并假设该定理对于所有尺寸小于$M$的图都成立。我们将证明该定理对于大小为 $M$ 仅具有偶数度的连通图 $G$ 也成立。

由于 $M>0$，图 $G$ 是不平凡的，因为它的度数为偶数，它包含度数至少为 2 的顶点。 那么$G$包含一个循环，可以通过以下方式看到：从任意顶点开始，沿着边走。 每当您进入一个新顶点时，至少有一条未使用的边可用于再次退出该顶点。 在某个时刻，您进入一个已经看到的顶点（最多在 $M$ 步之后），从那里开始的步行部分是一个循环。

每个周期也是一个循环。 现在考虑最大尺寸$|E^{\prime }|$的电路$C=(G^{\prime },E^{\prime })$。 如果$C$是$G$中的欧拉回路，则一切正常。 如果不是，我们就有 ，并且子图 $H=(V,E\setminus E^{\prime })$ 至少有一个非平凡连通分量 $H^{\prime }$。 电路具有偶数度，因此 $H$ 及其所有连接的组件具有偶数度。 由于$H^{\prime }$的大小为，因此它具有可以添加到$C$的欧拉电路，从而违反了$C$的最大值。因此，$C$必定是欧拉回路，证明完成。

回到柯尼斯堡，我们看到存在奇数度数的顶点。 不存在欧拉环路，居民在穿过城镇时要么跳过桥梁，要么穿越两次桥梁。

在上述无向图的定义中，边没有方向。 这与有向图（也称为有向图)不同。 有向图的大多数定义与无向图相同。 这里我们列出了一些差异和附加定义。

• 有向图 $G=(V,E)$ 与无向图类似，不同之处在于边（在本例中也称为弧)$(i,j)\subset V\times V$是有序的顶点对。

• 出度 $d_{\mathrm{out}}(i)$是出边$(i,j)$的数量。

• 入度 $d_{\mathrm{in}}(i)$ 是传入边$(j,i)$ 的数量。

• 有向路径的定义与无向图的路径类似，只是所有边沿路径必须具有相同的“向前”方向。 从形式上看，从 $i_0$ 到 $i_l$ 的路径是一个子图 $G^{\prime }=(V^{\prime },E^{\prime })$，其中包含 $V^{\prime }=\{i_0$、$i_1,\mathrm{\dots },i_l\}$、$E^{\prime }=\{(i_0,i_1)$、$(i_1,i_2)$、...、$(i_{l-1},i_l)\}$。

• 如果对于所有顶点对 $i,j$，在 $G$ 中存在一条从 $i$ 到 $j$ 的有向路径，以及一条从 $j$ 到 $i$ 的路径，则称有向图 $G=(V,E)$ 为 强连接图。 有向图的强连通分量 (SCC) 是最大尺寸的强连通子图，即。即，它不能通过添加顶点/边来扩展，同时仍然保持强连接。

2 哈密尔顿图

想象一下，您必须组织一场外交晚宴。 主要问题是将$N$大使安排在圆桌会议上：有些国家是强敌，在晚宴期间，外交官可能会表现得不太外交。 因此，您更愿意只将属于和平关系国家的大使安排在相邻席位上。

[htb]

左：必须放置外交官的圆桌。 右图：关系图，只有关系积极的大使才能相互联系，才能成为餐桌上的邻居。

同样，这个问题可以映射到图论问题。 对应的图就是“良好关系图”。 顶点与大使相同，并且任何两个具有良好关系，即。即，潜在的邻居通过边连接，见图2。 现在问题简化为寻找长度为 $N$ 的循环：

哈密​​尔顿循环： (HC) 给定的图中是否存在一个循环，使得每个 顶点 都被访问一次？

乍一看，这个问题似乎与寻找欧拉回路类似，但事实并非如此。 它属于NP完全问题（见第1章）。 4）并且一般来说，不能根据局部考虑来决定。 对于高度连通的图，有一个例外：

定理： 如果 $G=(V,E)$ 是顺序 $N\ge 3$ 的图，使得 $V$ 中所有顶点的 $\mathrm{deg}(i)\ge N/2$ ，则 $G$ 是哈密​​顿量（即，它具有哈密顿循环）。

我们没有给出证明，只是声明该定理不足以说明图 2 中给出的特定样本。 存在度数为 2 和 3 的顶点，它们小于 $N/2=4$。

哈密​​顿循环的搜索与已经提到的旅行商问题 (TSP) 密切相关，该问题是在加权图上定义的。 子图的总权重是其所有边的权重之和。 在 TSP 中，我们正在寻找最小权重的哈密顿循环。

3 最小生成树

让我们来讨论下一个问题。 这次你必须在一个没有火车但有许多城镇需要连接的国家规划铁路网络。 该国有财政问题，要求您设计尽可能最便宜的网络，为您提供可以直接连接哪些城镇对以及费用的信息 - i。 e.他们给你一个加权图。 您必须找到包含每个城镇的连通子图，才能从一个城镇前往另一个城镇。 同样明显的是，循环会增加总成本。 可以删除循环中最昂贵的边，而无需断开某些城镇与其他城镇的连接。 但如何才能找到全局最优解呢？

在回答这个问题之前，我们必须先了解一些定义：

Definition 1.3.

树，森林树是一个连通的无环图。

森林是一个仅包含树作为连接组件的图，请参见，e。例如，图1.3。

[htb]

森林是由树木组成的。

这里给出了树的一些易于证明的属性：

定理： $N$ 阶数的树的大小为 $M=N-1$。

Proof 1.4.

从一个孤立的顶点开始，添加边。 由于没有循环，每条边都会添加一个新顶点。

推论： 每棵 $N\ge 2$ 阶树至少包含两个 1 度顶点（叶子）。

Proof 1.5。

假设相反，i。即，至少有 $N-1$ 个度数至少为 2 的顶点。 由此我们发现

$$\sum _{i\in V}\mathrm{deg}(i)\ge 2N-1$$

另一方面，我们有

$$\sum _{i\in V}\mathrm{deg}(i)=2M$$

因为每条边都被计算两次。 这就产生了与定理的矛盾。

为了解决我们的铁路网络问题，我们需要两个进一步的定义。

Definition 1.6.

（最小）生成树/森林

• 令$G=(V,E)$为阶连通图$N$。 生成树 是顺序为$N$的无环子图，其最大尺寸$N-1$， 我。即，生成树仍然是连接的。

• 如果$G=(V,E,\omega )$被加权，则权值最小的生成树称为最小生成树 （或经济生成树)。

• 对于一般图，（最小）跨越森林 是其不同连接组件的所有（最小）生成树的并集。

由于生成树的最大尺寸条件，图及其生成林的连通分量是相同的。 生成树可以使用计算连通分量的算法来构建，请参见第 2 节。 1。 最小生成树显然满足了我们铁路网络的所有要求，并且可以使用 Prim 算法以非常简单的方式构建它们，这在第 2 节中介绍。 3。

4 边缘覆盖和顶点覆盖

现在我们介绍边缘和顶点覆盖。 这两个问题彼此相似，但在算法解决的容易程度方面有根本的不同。 我们已经在欧拉回路和哈密顿循环中看到了这一点。 顶点覆盖问题将作为本书的原型示例。 所有概念、方法和分析技术都将使用顶点覆盖问题进行解释。 我们从基本定义开始，但与顶点覆盖算法相关的附加定义在第 2 节中给出。 6.1.

对于图$G=(V,E)$,边覆盖是边的子集$E^{\prime }\subset E$，使得每个顶点包含在至少一条边$e\in E^{\prime }$中>。 每个没有孤立顶点的图都有一个边缘覆盖，因为在这种情况下 $E$ 本身就是一个边缘覆盖。 最小边缘覆盖是最小基数$|E^{{}^{\prime }}|$的边缘覆盖。 在图4中显示了图表和最小边缘覆盖。 构建最小边缘覆盖的快速算法可以在参考文献中找到。 [3]。

[H T]

图和最小边覆盖（左）和最小顶点覆盖（右）。 属于封面的边/顶点以粗体显示。

顶点覆盖的定义非常相似。 它是顶点的子集 $V^{\prime }\subset V$，使得每条边 $e=\{i,j\}\in E$ 至少包含 $V^{\prime }$ 中的一个顶点，即。例如，$i\in V^{\prime }$ 或 $j\in V^{\prime }$。 请注意，$V$ 本身始终是顶点覆盖。 最小顶点覆盖是最小基数$|V^{{}^{\prime }}|$的顶点覆盖。

顶点覆盖与独立集和派密切相关。 图的独立集合$G=(V,E)$是顶点的子集$I\subset V$，这样对于所有元素$i,j\in I$，没有边$\{i,j\}\in E$ 。 团是顶点的子集 $Q\subset V$，因此对于所有元素 $i,j\in Q$ 都有一条边 $\{i,j\}\in E$。

定理： 对于给定的图 $G=(V,E)$ 和子集 $V^{\prime }\subset V$，以下三个语句是等效的。

• $V^{\prime }$是$G$的顶点覆盖。

• $V\setminus V^{\prime }$是一个独立的$G$集合。

• $V\setminus V^{\prime }$是补图的派系$G^C$（参见第页的定义• ‣ 1)。

Proof 1.7.

(A $\to$ B)

设$V^{\prime }$为顶点覆盖，$i,j\in V\setminus V^{\prime }$。 我们假设有一条边$\{i,j\}\in E$。 由于$i,j\notin V^{\prime }$，这是一条边，其两个顶点都不在$V^{\prime }$中，并且$V^{\prime }$不是顶点覆盖。 这是一个矛盾！ 因此，不可能存在边$\{i,j\}\in E$，并且$V\setminus V^{\prime }$是一个独立的集合。

(B $\to$ C)

设$V\setminus V^{\prime }$为独立集合，且$i,j\in V\setminus V^{\prime }$。 根据定义，不存在边$\{i,j\}\in E$，因此存在边$\{i,j\}\in E^C$。 因此，$V\setminus V^{\prime }$是$G^C$的派系。

(C $\to$ A)

设$V\setminus V^{\prime }$为$G^C$和$\{i,j\}\in E$的派系。 根据 $G^C$ 的定义，这意味着 $\{i,j\}\notin E^C$。 因此，我们有 $i\notin V\setminus V^{\prime }$ 或 $j\notin V\setminus V^{\prime }$，因为 $V\setminus V^{\prime }$ 是一个派系。 因此，$i\in V^{\prime }$ 或 $j\in V^{\prime }$。 根据顶点覆盖的定义，$V^{\prime }$是顶点覆盖。

最小顶点覆盖是最小基数的顶点覆盖。 根据上面的定理，对于最小顶点覆盖$V^{\prime }$,$V\setminus V^{\prime }$是$G$的最大独立集和$G^C$的最大团。 在图4中，显示了一个图及其最小顶点覆盖。 对于给定整数 $K$，与最小化问题相关的是以下决策问题：

顶点覆盖 (VC)： 给定的图$G$是否有一个顶点覆盖$V^{\prime }$和$|V^{{}^{\prime }}|\le K$？

在第 1 章中。 在图 4 中，我们将看到 VC 是一个所谓的 NP 完全问题，这特别意味着尚不知道解决该问题的快速算法，甚至不希望能够构造出来。 这个命题及其与统计物理学的关系将是本书的主题。

5 图形着色问题

我们在本节中讨论的最后一个问题是调度问题。 想象一下，您必须组织一次包含许多会议的会议，原则上这些会议可以并行举行。 然而，有些人想要参加不止一场会议。 我们正在寻找一个完美的日程安排，即每个人都可以参加他想要参加的所有会议，但会议总时间最短。

到无向图的映射如下：会话被视为顶点。 每当有人想要同时参加两个活动时，两个活动就会通过一条边连接起来。 现在，我们尝试对顶点进行着色，以使相邻顶点不具有相同的颜色。 因此，我们可以并行组织所有这些具有相同颜色的会议，因为没有人愿意参加两个相应的会议。 最佳的时间表需要尽可能少的颜色数量。

这个问题类似于地理地图的着色，其中国家对应于顶点，共同边界对应于边缘。 同样，我们不想使用相同的颜色给邻国着色。 主要区别在于图的结构。 “地理”是二维的，没有交叉边——所谓的图形的平面性使问题变得容易。 第一张图更一般，因此也更复杂。 同样，问题变成了 NP 完全问题。

让我们更准确地说：

Definition 1.8。

$q$-着色、色数，$q$-核心

• 一个$q$着色的$G=(V,E)$是一个映射$c:V\to \{1,\mathrm{\dots },q\}$，使得$c(i)\ne c(j)$的所有边$\{i,j\}\in E$.。

• 所需颜色的最小数量称为色数 $G$ .

• 最大子图，其中所有顶点的最小度至少为$q$，称为$q$-核心。

不可$q$着色的最小图是顺序$q+1$和大小$q(q+1)/2$的完整图$K_{q+1}$ >，岛。即，所有顶点对都是相连的。 完全图也称为派。 对于 $K_3$ 来说，这是一个三角形，对于 $K_4$ 来说，这是一个四面体。

在分析$q$着色问题之前，先介绍构建$q$核心的线性时间算法。 该算法的思想很简单，它删除所有度数小于$q$的顶点及其关联边。 简化图可能会有新的度数小于$q$的顶点，这些顶点将被递归地删除，直到获得最小度数至少为$q$的子图。 出于显而易见的原因，获得了 $q$ 核心：算法无法删除 $q$ 核心之外的任何顶点，因此最终状态至少与 $q$-核心。 根据后者的最大值，两者必须相等。 下面介绍的算法的输入是初始图 $G=(V,E)$，输出是其 $q$ 核心：

algorithm core($V,E,q$)
begin
	if min$\{\mathrm{deg}(i)|i\in V\}\ge q$ then
		return $G=(V,E)$;
	else do
		begin
			;
			$V:=V\setminus U$;
			$E:=E\cap V^{(2)}$;
			return core($V,E,q$);
		end
end

定理： 当且仅当其 $q$ 核心是 $q$ 可着色时，图才是 $q$ 可着色的。

Proof 1.9。

($\to$) 整个图的着色显然是每个子图的着色。

($\leftarrow$) 通过 core-algorithm 构造 $q$-core，但跟踪删除顶点的顺序。 现在对核心进行任何 $q$ 着色。 通过按相反顺序添加删除的顶点来重建完整图。 添加后，顶点的度数立即小于$q$。 他们的邻居使用少于 $q$ 的颜色，即。即，添加的顶点可以被着色。 这样，$q$核的每个着色都可以递归地扩展到整个图的着色。

[htb]

左图是不可3色的四面体$K_4$，字母表示4色的不同颜色。 右图也有固定的阶数 3，但可以用三种颜色着色。

这表明 $q$ 为图着色的困难部分在于为其 $q$ 核心着色，即。即，非平凡的$q$-核心的存在是必要的，但对于$q$-不着色性来说还不够，参见，e。例如，图1.9中给出的示例。 这也导致

推论： 每个最多具有 $q$ 个度数至少为 $q$ 的顶点的图是 $q$ 可着色的。

在本节的开头，我们还考虑了地理地图（或平面图)的着色，即。即可以在平面上绘制而无需交叉边的图形。 对于这些图，可以使用以下著名定理轻松找到色数：

定理： 每个平面图都是 4 色的。

这在1852年就已经被猜想出来，但最终的解决方案直到1976年才由Appel和Haken[4]给出。 然而，他们的证明却很不寻常：Appel 和 Haken 根据图结构将原始问题“减少”到了 2000 多个案例。 最终使用了大约 1200 小时的计算时间对这些案例进行了数字着色。 许多数学家对这个证明颇为不满，但至今还没有人提出“手写”的证明。

另一方面，很容易看出 3 种颜色通常不足以为平面图着色。 最简单的例子是 4-clique $K_4$，它是平面的，如图 1.9 所示。

6 匹配

给定图 $G=(V,E)$，匹配的 $M\subset E$ 是边的子集，使得 $M$ 中没有两条边与同一顶点 [5 ，6]，i。即，对于所有顶点 $i\in V$，我们最多有一条边 $e\in M$ 的 $i\in e$。 给定匹配中包含的边称为匹配，其他边称为自由。 属于边$e\in M$的顶点被覆盖（或匹配)，其他顶点M暴露（或 Exposure 或 free)。如果 $e=\{i,j\}$ 匹配，则 $i$ 和 $j$ 称为 mates.

最大基数的匹配$M$称为最大基数匹配。 如果匹配不留下任何暴露的顶点，则它是完美，因此它自动成为最大基数匹配。 另一方面，并​​非每个最大基数匹配都是完美的。

二部图的顶点集可以细分为两个不相交的顶点集，例如$U$和$W$，使得图中的边$\{i,j\}$ 仅将 $U$ 中的顶点连接到 $W$ 中的顶点，在 $U$ 或 $W$ /t8>.请注意，最近邻超立方晶格是二分晶格，而三角形和面心立方晶格是不是二分晶格。 由于二分图上的所有环都具有偶数条边，因此二分图上的匹配比一般图上的匹配要容易得多。 此外，二分图上的最大基数匹配可以很容易地与最大流问题[7,8,9]相关，请参见第 2 节。 11.5。

Example 1.10。

匹配

[htb]

匹配示例图，请参阅文本。

图1.10显示了示例图。 请注意，该图是二分图，具有顶点集 $U=\{1,2,3\}$ 和 $W=\{4,5,6\}$。 匹配中包含的边由粗线表示。 左半部分显示的匹配是$M=\{\{1,4\},\{2,5\}\}$。 这意味着，e。例如，边$\{1,4\}$是匹配的，而边$\{3,4\}$是空闲的。 顶点 1、2、4 和 5 被覆盖，而顶点 3 和 6 则暴露。

在图的右半部分，显示了完美匹配的$M=\{\{1,5\},\{2,6\},\{3,4\}\}$，即。即，没有暴露的顶点。

有了加权图$G=(V,E,w)$，我们还考虑加权匹配，匹配的权重由所有匹配边的权重之和给出。 如果$M$的总权重对于所有可能的匹配假设为最大值，则它是最大权重匹配。 对于完美匹配，最大权重匹配和最小权重匹配之间有一个简单的映射，即：let ${\tilde{w}}_{ij}=W_{\max }-w_{ij}$，其中$w_{ij}$是边$\{i,j\}$的权重> 和$W_{\max }>{\max }_{\{i,j\}}(w_{ij})$。 ${\tilde{w}}_{ij}$ 上的最大完美匹配是 $w_{ij}$ 上的最小完美匹配。

Lovász 和 Plummer [6] 中可以找到对匹配问题的很好的历史介绍，其起源可以追溯到组合学的起源。 匹配与统计力学直接相关，因为可以通过计算二聚体覆盖（=完美匹配）[6]来找到方晶格上二维伊辛模型的配分函数>。 这是一个图形枚举问题，而不是此处考虑的优化问题。 一般来说，图枚举问题比图优化问题更难。

[htb]

（左）：具有匹配的二部图。 交替路径（阴影）在暴露的顶点处开始和结束，并在不匹配（细）边和匹配（粗）边之间交替。 （右）：沿着交替路径交换匹配和不匹配的边会将匹配的基数增加一。 这称为增强，是最大匹配算法的基本工具。 在这个例子中，增强产生了最大基数匹配，甚至是完美匹配。

平面自旋玻璃的基态计算相当于一般图上的最小权完美匹配问题，参见第 2 节。 11.7。 一般图上的最大/最小（完美）匹配问题在算法上比二部图更复杂，请参见，e。例如，参考文献 [10, 11]，但它们仍然可以在仅随系统规模呈多项式增加的运行时间内求解。 这些匹配算法依赖于寻找交替路径，即边缘交替匹配和不匹配的路径，见图6。

2 基本图算法

在本节中，我们将介绍基本的图算法，这些算法与查找图的连通分量相关。 首先，我们解释两种不同的策略，深度优先搜索和广度优先搜索。 除了产生连接组件之外，它们还构建跨越树。 然后我们解释如何通过修改深度优先搜索来获得有向图的强连通分量。 最后我们展示了，对于加权图的情况，可以使用 Prim 的简单算法找到最小权重跨度树。 图算法的另一种基本类型是最短路径算法，我们稍后将在第 2 节中对其进行解释。 11.4。

1 深度优先和广度优先搜索

对于给定的图$G=(V,E)$，我们想要确定它的连通分量。 有两种基本的搜索策略，深度优先搜索（DFS）和广度优先搜索（BFS），它们密切相关。

第一个算法的主要工作是在以下过程深度优先（）中完成的，该过程从给定顶点$i$开始并访问连接到$i$的所有顶点。 主要思想是对当时尚未访问的 $i$ 的所有邻居执行深度优先（）的递归调用。 数组 comp$[]$ 用于跟踪进程。 如果comp$[i]=0$顶点$i$尚未被访问。 否则它包含当前探索的组件的编号（id）$t$。 $t$ 的值也作为参数传递，而数组 comp$[]$ 作为引用传递，即。即，它的行为类似于全局变量，并且在调用过程中对 $comp[]$ 执行的所有更改在调用完成后仍然存在。

procedure depth-first($G$, $i$, [ref.] comp, $t$)
begin
	comp[$i$]:=$t$;
	for all neighbors $j$ of $i$ do
		if comp[$j$] = 0 then
			depth-first($G$, $j$, comp, $t$);
end

要获得所有连接的组件，必须对所有尚未访问过的顶点调用深度优先（）。 这是通过以下算法完成的。

algorithm components($G$)
begin
	initialize comp$[i]:=0$ for all $i\in V$;
	$t:=1$;
	while there is a vertex $i$ with comp$[i]$=0 do
		depth-first($G$, $i$, comp, $t$); $t:=t+1$;
end

对于任何顶点$i$，当过程为邻居$j$递归调用自身时，它遵循边$\{i,j\}$。 由于没有顶点被访问两次，因此这些边形成每个连接组件的生成树。 我们将这些边称为树边，其他边称为后边。 在访问开始搜索的顶点的其他邻居之前，算法会尝试在图中尽可能远地进行搜索。 正是由于这个原因，该过程才得名。 因此，生成树称为深度优先生成树，所有连通分量的生成树的集合就是深度优先生成林。 在下一节中，我们将使用深度优先生成树来查找有向图中的强连通分量。

Example 2.1.

深度优先生成树 作为示例，我们考虑图2.1左侧所示的图。 我们假设算法首先对顶点 1 调用深度优先()，因此设置 $comp[1]:=1$。

[H T]

示例图（左）。 靠近顶点的数字表示在深度优先搜索期间访问顶点的可能顺序。 右侧显示了生成的深度优先生成树。

我们假设顶点$2$是for循环中遇到的顶点1的第一个邻居。 因此，对于顶点 $2$ 调用深度优先，其中设置了 $comp[2]:=1$。 这里，在 for 循环中，可能首先遇到顶点 1，但它已经被访问过 ($comp[1]=1$)，因此什么也没有发生。 在下一次迭代中，遇到第二个邻居顶点 $4$。 现在为顶点$4$调用深度优先（），并分配$comp[4]:=1$。 我们假设顶点 7 是在顶点 4 的所有邻居的循环中遇到的第一个顶点。 因此，接下来调用深度优先($G,7,comp,1$)，从而导致两次深度优先()的递归调用。 完整的递归调用层次结构如下所示（我们仅显示顶点 $i$ 的参数）：

depth-first($1$)
	depth-first($2$)
		depth-first($4$)
			depth-first($7$)
				depth-first($6$)
					depth-first($3$)
			depth-first($5$)

顶点 3 达到递归的最深点。 它的所有邻居，即顶点 1、4 和 6 都已被访问过，因此该过程返回此处而无需进一步调用。 此时，只有顶点 5 尚未被访问，因此在迭代顶点 4 的其他邻居时会访问它。 访问顶点的顺序如图2.1所示，并且还显示了生成的深度优先生成树。

在算法运行期间，对于每个顶点，访问所有邻居以测试它是否已经被访问过。 因此，每条边都会被触摸两次，时间复杂度为 $𝒪(|E|)$。

深度优先搜索也可以适用于有向图。 在这种情况下，在顶点 $i$ 处，仅遵循边 ($i,j$)，即。 e.，指向前方。 这意味着生成的深度优先生成树可能看起来不同。 甚至树中包含的顶点也可能有所不同，具体取决于外部循环中访问顶点的顺序（如无向情况下的 elements() 中），正如我们将在下面的示例中看到的。 这意味着有向图的组件没有很好地定义，因为它们取决于处理顶点的顺序。 相反，人们感兴趣的是计算定义明确的强连接分量。 相应的算法将在下一节中介绍。 在那里，我们需要反向拓扑顺序，也称为后序。 这正是深度优先生成树计算过程中顶点$i$完成处理的顺序。即，以 $i$ 作为参数调用过程的终止顺序。

该算法如下，仅针对无向情况稍加修改。 后序存储在数组 $post[]$ 中，该数组作为引用传递，即。即，对值的所有修改在程序之外也有效。 我们还需要一个计数器 $c$，也是通过引用传递，用于建立后序。 数组$tree$，也通过引用传递，跟踪哪些顶点已经被访问过，并存储包含顶点的树的标识号，对应于数组$comp$用于无向情况。

procedure depth-first-directed($G$, $i$, [ref.] $tree$, $t$, [ref.] $post$, [ref.] $c$)
begin
	$tree[i]:=t$;
	for all $j$ with $(i,j)\in E$ do
		if tree[$j$] = 0 then
			depth-first-directed($G$, $j$, $tree$, $t$, $post$, c);
	$post[i]:=c$;
	$c:=c+1$;
end

主子程序，查找所有连接的深度优先生成树并建立反向拓扑顺序，如下所示。

algorithm postorder($G$)
begin
	initialize tree$[i]:=0$ for all $i\in V$;
	$t:=1$;
	$c:=1$;
	while there is a vertex $i$ with $tree[i]$=0 do
		depth-first-directed($G$, $i$, $tree$, $t$, $post$, $c$); t:=t+1;
end

在 postorder() 的循环内部调用深度优先定向() 的顶点，i。即，树的构造开始的顶点被称为深度优先生成树的根。 它们是每棵树接收最高 $post$ 数字的顶点。 较早访问的其他树的顶点将收到较低的 $post$ 编号，较晚访问的树的顶点将收到比当前树的所有顶点更高的 $post$ 编号。

Example 2.2.

有向图的深度优先生成树 我们考虑图2.2所示的图。 [H T]

有向图示例。

我们假设在 postorder() 中首先考虑顶点 1。 顶点 1 有一个邻居，因此将为顶点 2 调用深度优先定向()，其中为顶点 3 调用该过程。 顶点 3 在前向有一个邻居，即顶点 1，该顶点已被访问过，因此此处不执行任何调用。 这意味着顶点 3 的过程完成，并且 $post[3]:=1$ 被分配。 由于顶点 2 的所有邻居都已被访问，因此该调用也完成并分配 $post[2]=2$ 。 接下来，同样的事情发生在顶点 1 上，结果是 $post[1]=3$。 因此，算法返回到顶层，即 postorder()。

现在，我们假设对顶点 4 调用深度优先定向，并且按照 3、5、6、8 的顺序处理其邻居。 顶点 3 已被访问过。 对顶点 5 的深度优先定向() 的调用导致对其未访问的邻居顶点 7 的过程的调用。 对顶点 8 的调用本身调用了对顶点 9 的过程。 总共获得以下调用层次结构，仅显示顶点 $i$ 的传递值。

depth-first-directed($1$)
	depth-first-directed($2$)
		depth-first-directed($3$)
depth-first-directed($4$)
	depth-first-directed($5$)
		depth-first-directed($7$)
	depth-first-directed($6$)
	depth-first-directed($8$)
		depth-first-directed($9$)

生成的深度优先生成森林如图 2.2 以及反向拓扑顺序的 $post$ 值所示。 树的根总是显示在顶部。 [H T]

关于图 1 中可能的深度优先跨越森林。 2.2。靠近顶点的数字表示 $post$ 逆拓扑顺序的值。

如果以不同的顺序处理顶点，则生成的深度优先生成森林可能看起来不同。 当，e。例如，首先考虑顶点 4，然后所有顶点将被收集在一棵树中。 假设顶点 4 的邻居按 8,6,5,3 的顺序考虑，生成的树如图 2.2 所示。 [H T]

图 2 中图的另一种可能的深度优先生成树。 2.2。靠近顶点的数字表示 $post$ 逆拓扑顺序的值。

现在我们回到无向图。 与深度优先搜索类似的算法是首先访问顶点的所有邻居，然后再继续处理更远的顶点。 该算法称为广度优先搜索。 这意味着首先访问初始顶点的所有邻居。 这个初始顶点是正在构建的广度优先生成树的根。 当根据沿距根的最短路径的边数来测量时，这些邻居距根的距离为 1。 在图 2.1 的前面示例中，如果使用广度优先搜索构建生成树，则边 $\{1,2\}$ 将包含在生成树中，如下所示。 在算法的下一步中，将访问第一步中处理的顶点的所有邻居，依此类推。 于是，一个队列 可用于存储要处理的顶点。 当前顶点的邻居总是存储在队列的末尾。 最初，队列仅包含根。 算法表示如下，$level(i)$表示顶点$i$到根$r$的距离，$pred(i)$是$i$ 位于从 $r$ 开始的最短路径中，它定义了广度优先生成树。

algorithm breadth-first search($G,r$, [ref.] $comp,t$)
begin
	Initialize queue $Q:=\{r\}$;
	Initialize $level[r]:=0$; $level[i]:=-1$ (undefined) for all other vertices;
	$comp[r]:=t$;
	Initialize $pred[r]:=-1$;
	while $Q$ not empty
	begin
		Remove first vertex $i$ of $Q$;
		for all neighbors $j$ of $i$ do
			if $level[j]=-1$ then
			begin
				$level[j]:=level[i]+1$;
				$comp[j]:=t$;
				$pred[j]:=i$;
				add $j$ at the end of $Q$;
			end
	end
end

同样对于广度优先搜索，对于每个顶点，所有邻居都会被访问。 因此，每个边缘再次被触摸两次，这导致时间复杂度为$𝒪(|E|)$。 为了获得图的广度优先生成森林，必须在所有顶点的循环内调用针对所有尚未访问的顶点的过程，如上面介绍的算法 components() 中所示。

Example 2.3.

广度优先搜索 我们考虑与上例相同的图，如图 2.3 所示。 最初，队列包含源，这里再次为 1，并且除 $level[1]=0$ 之外的所有值 $level[i]$ 均为“未定义”(-1)。

$Q=\{0\}$,$level[1]=1$

[H T]

示例图（左）。 靠近顶点的数字表示在广度优先搜索期间访问顶点的可能顺序。 右侧显示了生成的广度优先生成树。

在处理顶点 1 时，其邻居顶点 2 和 3 将添加到队列中，即 $pred[2]=pred[3]=1$。 它们与源的距离为 1 ($level[2]=level[3]=1$)。

$Q=\{2,3\}$,$level[1]=0$,$level[2]=level[3]=1.$

处理下一个顶点 2。 它有两个邻居，顶点 1 和 4，但顶点 1 已经被访问过 $(level[1]\ne -1$)，因此只有顶点 4 与 $pred[4]=2$ 添加到 $Q$ 中，$level[4]=level[2]+1=2$。 本次迭代后情况如下：

$Q=\{3,4\}$、$level[1]=0$、$level[2]=level[3]=1$、$level[4]=2.$

处理顶点 3 将顶点 6 添加到队列中($level[6]=level[3]+1=2$、$pred[6]=3$)。 在下一次迭代开始时，采用顶点 4。 在它的四个邻居中，顶点 5 和 7 尚未被访问过。 因此$level[5]=level[7]=3$和$pred[5]=pred[7]=4$。 现在 $pred$ 和 $level$ 数组的所有值均已设置。 最后，处理顶点 6,5 和 7，变量不发生任何变化。

生成的广度优先生成树如图2.3右侧所示。 它还存储在到源的最短路径数组 $pred$ 中，例如。例如，从顶点 7 到顶点 1 的最短路径由前驱的迭代序列给出：$pred[7]=4,pred[4]=2,pred[2]=1$。

2 强连通分量

正如我们回忆的那样。 1，有向图$G=(V,E)$的强连通分量是顶点的最大子集，其中，对于每对$i,j$，有来自$i$ 到 $j$ 以及从 $j$ 到 $i$ 的定向路径存在于 $G$ 中。正如我们将在这里展示的，它们可以通过两次深度优先搜索来获得。

基本思路如下。 第一个对$G$执行深度优先搜索，获得深度优先生成森林以及数组$post$中的逆拓扑顺序。 接下来，构建反向图$G^R$，该图是通过使用与$G$中相同的顶点以及来自$G$的所有边获得的> 反转

$$G^R\equiv (V,E^R)E^R\equiv \{(j,i)|(i,j)\in E\}.$$ (1)

然后我们计算$G^R$的深度优先生成森林，但是我们以在第一次深度计算中获得的反向拓扑顺序的递减值来处理主循环中的顶点 -$G$ 的第一顺序。特别是，我们总是从接收到最高 $post$ 数字的顶点开始。 这样得到的深度优先生成森林的树就是$G$的强连通分量。原因是，对于每棵树，具有最高 $post$ 编号的顶点是可以到达深度优先树的所有顶点的顶点，即。即树的根。 当在这些顶点开始深度优先搜索反向图时，图一能够访问这些顶点，从这些顶点能够到达原始图中的根。 总的来说，这些顶点是可以到达根的顶点，并且可以从根开始到达的顶点，即。即，它们组成了强连通分量。 下面将给出详细的证明。 该算法可以总结如下：

algorithm scc($G$)
begin
	initialize tree$[i]:=0$ for all $i\in V$;
	$t:=1$; $c:=1$;
	while there is a vertex $i$ with $tree[i]$=0 do
		depth-first-directed($G$, $i$, $tree$, $t$, $post1$, $c$); t:=t+1
	calculate reverse graph $G^R$;
	initialize tree$[i]:=0$ for all $i\in V$;
	$t:=1$;
	$c:=1$;
	for all $i\in V$ in decreasing value of $post1[i]$ do
		if $tree[i]$=0 do
			depth-first-directed($G^R$, $i$, $tree$, $t$, $post2$, $c$); t:=t+1;
end

Example 2.4.

强连通分量 作为一个例子，我们考虑图2.2中的图。 我们假设反向拓扑顺序是在第一个示例运行中获得的，如页面 2.2 所示，因此按反向拓扑顺序的 $post$ 编号递减排列的顶点为

$$4,8,9,6,5,7,1,2,3$$

按照此顺序，深度优先搜索应用于反向图$G^R$，如图2.4所示。

[H T]

图形的反转图如图所示。 2.2.

因此，在调用 depth-first-directed($G^R$, 4, $tree$, $1$, $post2$, $c$) 时，顶点 7、5 和 6 将在 $i=4$ 的调用结束前按此顺序递归访问。接下来，在带有 $t=2$ 的主循环中，调用顶点 $i=8$ 的存储过程，该顶点在 $post1$ 中的值为第二高，然后调用顶点 $8$ 和 $9$ 的存储过程。 被处理。 对于第三个（$t=3$）迭代，为顶点 1 调用深度优先定向（），从而导致也访问顶点 3 和 2。 由此产生的深度优先跨越森林如右侧所示。

这意味着我们得到了三棵树，分别对应三个强连通分量$C_1=\{1,2,3\}$、$C_2=\{4,5,6,7\}$和$C_2=\{8,9\}$.

该算法由两个顶点循环组成，其中包含对深度优先定向（）的调用。 每个循环都需要时间 $𝒪(|V|+|E|)$，请参阅第 2 节。 1。 请注意，通过在深度优先定向（）调用完成后将每个顶点写入数组中，可以按递减的反向拓扑顺序获取顶点。 为了简洁起见，我们没有在上面的算法中包含这个数组。 这意味着只需以相反的顺序遍历数组即可在 scc() 中执行 for 循环，即：即，无需额外的时间成本。 由于计算反向图也可以在 $𝒪(|V|+|E|)$ 中完成，因此完整算法的运行时间为 $𝒪(|V|+|E|)$。 该算法有多种变体，只需要一次深度优先生成森林的计算，而不是两次，而且也不会发生反向图的计算。 相反，它们需要更新附加数据字段，因此它们有点难以理解。 对这些算法感兴趣的读者应该查阅标准文献[12,13,14]。

我们通过证明上述算法确实产生有向图的强连通分量来结束本节。 请注意，反向图的强连通分量与图本身的强连通分量完全相同。

Proof 2.5。

$(\to )$
假设两个顶点$i$和$j$是相互可达的，即。 e.，通过路径连接。 因此，它们在反向图中是相互可达的。 这意味着在森林的第二次计算期间，它们将位于同一棵树中。

$(\leftarrow )$

现在，我们假设 $i$ 和 $j$ 位于 $G^R$ 的深度优先森林计算的同一棵树中。让 $r$ 成为这棵树的根，即在 for 循环的顶层调用了深度优先定向()的顶点。由于for循环是按$post$值的递减顺序执行的，这意味着$r$的$post$值最高。 树的价值。 这特别意味着 $post[r]>post[i]$ 和 $post[r]>post[j]$ (*)。

我们通过提出矛盾来进行证明。 我们假设$i$和$j$不在同一个强连通分量中。

由于 $i$ 和 $j$ 与 $G^R$ 的根 $r$ 在同一棵树中，因此在反向图图 $G^R$ 中一定存在从根 $r$ 到 $i$ 以及从 $r$ 到 $j$ 的路径、因此，在 $G$ 中一定有从 $i$ 到 $r$ 和从 $j$ 到 $r$ 的路径。由于假定 $i$ 和 $j$ 不在同一个强连接组件中，因此在 $G$ 中要么没有从 $r$ 到 $i$ 的路径，要么在 $G$ 中没有从 $r$ 到 $j$ 的路径。

不失一般性，我们考虑第一种情况$r\to ̸i$。 有两种可能：

• $i$ is visited before $r$ in the calculation of the depth-first forest of $G$. But then, because there is a path from $i$ to $r$ in $G$, the call to depth-first-directed() for $r$ would finish before the call for $i$, hence we would have $post[i]>post[r]$. 这与(*)矛盾！

• $r$ 在 $i$ 之前被访问。由于没有从 $r$ 到 $i$ 的路径，因此当 $r$ 的调用结束时，顶点 $i$ 仍将未被访问，因此我们将再次得到 $post[i]>post[r]$. 这与(*)矛盾！

同样，当假设路径$r\to j$在$G$中不存在时，我们可以提出矛盾。这意味着 $i$ 和 $j$ 必须位于同一个强连接组件中。

3 最小生成树

用于构造给定图的最小生成树的算法（定义参见第3节）是贪婪。 这意味着算法在每一步都会做出成本最低的决定。 与第 1 章中介绍的 TSP 算法相反。 2、保证找到全局最小值。 Prim 算法的基本思想是，从最小权重的边开始，然后继续添加连接到已构造的子树的最小边，除非会产生循环：

algorithm Prim(G)
begin
	choose $\{i,j\}$ : ${\omega }_{ij}:=\min \{{\omega }_{km}|\{k,m\}\in E\}$;
	$S:=\{i,j\}$;
	$\overline{S}:=V\setminus \{i,j\}$;
	$T:=\left\{\{s,r\}\right\}$;
	$X:={\omega }_{ij}$;
	while do
	begin
		choose $\{i,j\}$ : $i\in S,j\in \overline{S}$ and ${\omega }_{ij}:=\min \{{\omega }_{km}|k\in S,m\in \overline{S},\{k,m\}\in E\}$;
		$S:=S\cup \{j\}$;
		$\overline{S}:=\overline{S}\backslash \{j\}$;
		$T:=T\cup \left\{\{i,j\}\right\}$;
		$X:=X+{\omega }_{ij}$;
	end
	return $(S,T)$;
end

Prim算法的动作如图3所示。 人们可以很容易地验证它实际上产生了一棵最小生成树：想象一下，情况并非如此，i。即，在算法中，您第一次在第 $k$ 步添加了错误的边 $\tilde{e}$。 现在想象一下，您有一个最小生成树，与 Prim 算法在第一个 $k-1$ 选定边中构建的树一致，但不包含 $\tilde{e}$。 如果将边 $\tilde{e}$ 添加到最小生成树，则会引入一个环，根据 Prim 的算法，该环至少包含一条权重较高的边。 删除后者从而得到权重更小的新生成树，这与初始生成树的极小性相矛盾。

由于每条边最多选择一条，因此 while 循环执行 $𝒪(|E|)$ 次。 在简单版本中，选择权重最小的边需要遍历所有边 ($𝒪(|E|)$)，而更精细的版本可以使用优先级队列 [12, 13, 14]，这样选择操作只需要 $𝒪(\log |E|)$ 时间，总共需要 $𝒪(|E|\log |E|)$ 运行时间。

[H T]

Prim 算法的图示。 该图包含五个顶点，编号从 1 到 5。 沿边的数字表示边权重。 生成树中包含的当前边以粗体显示。 从（a）开始，从最低成本边开始，到（d），连续添加新边，直到达到最小生成树。

3 随机图

1 两个整体

随机图理论的基本思想是研究图的集合，而不是单个特定的图实例。 使用概率工具，有时更容易显示具有特定属性的图的存在，反之亦然，查看具有给定属性（例如，顺序、大小、度数……）的典型图。出现。

最简单的想法可以追溯到 Erdős 和 Rényi 于 1960 年发表的一篇开创性论文[15]。 他们假设所有具有相同阶 $N$ 和大小 $M$ 的图都是等概率的。 该领域主要使用两种略有不同的集成：

集合$𝒢(N,M)$包含$N$顶点和$M$边的所有图。 该措施是平坦的，i。即，每个图都有相同的概率，参见，e。例如，图1。 请注意，通过排列顶点从给定图获得的所有图都是不同的图，即。即，它们是单独计算的。

[htb]

这两个图在 $𝒢(4,3)$ 中是等概率的，即使它们的结构完全不同。 左图是一棵连通树，而右图则没有连通并且包含一个环。

集合 $𝒢(N,p)$ 与 $0\le p\le 1$ 包含具有 $N$ 顶点的图。 对于每个顶点对$i,j$，以$p$的概率独立绘制边$\{i,j\}$。对于$p=0$，图没有边，对于$p=1$，图是完整的($K_N$)。 平均而言，给定 $p$ 的边数为

$$\overline{M}=p\left(\genfrac{}{}{0pt}{}{N}{2}\right)=p\frac{N!}{(N-2)!2!}=p\frac{N(N-1)}{2}$$ (2)

其中横线表示 $𝒢(N,p)$ 上的平均值。 这个集合在分析上更容易处理，所以我们主要使用 $𝒢(N,p)$。

特定情况$𝒢(N,1/2)$也可以被视为图的随机集合：$N$顶点的所有图都是等概率的，与它们的边数无关。

一种重要的陈述类型是$𝒢(N,p)$图满足几乎肯定（或概率为1)某些条件$C$。该表达式意味着，对于 $N\to \mathrm{\infty }$，从 $𝒢(N,p)$ 绘制的图满足此条件 $C$ 的概率收敛于 1。

2 图的演变

有时，通过 $N$ 顶点图的演化过程来想象集合 $𝒢(N,p)$ 是非常有启发性的，随着时间的推移，顶点图会获得越来越多的边。 这可以通过以下方式实现。 我们取$V=\{1,\mathrm{\dots },N\}$，对于所有$i,j\in V$、，我们独立地抽取一个随机数$x_{ij}$，均匀分布在$(0,1)$. 最初该图没有边。 现在，我们开始成长$p(t)$。 每当它超过数字 $x_{ij}$ 时，就会在顶点 $i$ 和 $j$ 之间添加一条边。 因此，在时间$t$，该图属于$𝒢(N,p(t))$。 这一演变有一些有趣的阶段：

• $p(t)\sim 1/N^2$：出现第一个孤立的边。

• $p(t)\sim 1/N^{3/2}$：第一个顶点的度数为 2，即。即，第一条边具有公共顶点。

• $p(t)\sim 1/N^{\alpha },$ 任意 $\alpha >1$：该图几乎肯定是一片森林。

• $p(t)\sim 1/N$：平均顶点度在$N\to \mathrm{\infty }$内保持有限，第一个循环出现，第一个宏观（即，顺序$𝒪(N)$)子图出现，宏观$q$-核心出现。

• $p(t)\simeq \ln (N)/N$：图形变为连接状态。

• $p(t)\simeq (\ln (N)+\ln (\ln (N))/N$：图形变为哈密顿量。

有关证明，请参阅第 • ‣ ‣ 第 0 章图简介上提到的 Bollobás 的书。

3 有限连通图：案例 toc$p=c/N$toc$𝒑\mathbf{=}𝒄\mathbf{/}𝑵$

最有趣的情况是 $p=c/N$ 给出的，其中图 $\overline{M}=c(N-1)/2$ 的中等大小随着图顺序 $N$ 线性增长。在本节中，我们首先讨论总边数$M$的波动，以及一些局部属性，例如度数和小循环的存在。 在接下来的两节中，我们最终切换到全局属性。 我们讨论随机图渗透，它描述了一种相变，从只有小的连通分量的图（即使是$N\to \mathrm{\infty }$)到也有一个巨大分量的图，该巨型分量统一了所有连通分量的有限部分。顶点岛即，其阶数也随着图阶数 $N$ 线性增长。最后一小节讨论了$q$核心的突然出现。

边数

对于 $𝒢(N,c/N)$ 的图，每对顶点都以 $c/N$ 的概率通过边连接，并以 $1-c/N$ 的概率保持不连接。 与 $𝒢(N,M)$-ensemble 相比，边的总数是一个随机变量，并且随样本的不同而波动。 因此，让我们计算它恰好具有 $M$ 边缘的概率 $P_M$。 这是由下式给出的

$$P_M=\left(\genfrac{}{}{0pt}{}{N(N-1)/2}{M}\right){\left[\frac{c}{N}\right]}^M{\left[1-\frac{c}{N}\right]}^{N(N-1)/2-M}.$$ (3)

组合前置因子描述了从 $N(N-1)/2$ 不同顶点对中选择 $M$ 边的可能数量，第二个因子给出了它们实际上由边连接的概率，而最后一个因素保证没有进一步的边缘。 在大$N$的限制下，对于$M\sim N$，其中$M\ll N(N-1)/2$，我们使用

$\left({\displaystyle \frac{N(N-1)}{2}}\right)\left({\displaystyle \frac{N(N-1)}{2}}-1\right)\mathrm{\cdots }\left({\displaystyle \frac{N(N-1)}{2}}-M+1\right)=$

${\left({\displaystyle \frac{N(N-1)}{2}}\right)}^M+𝒪\left(N^{2(M-1)}\right)$ (4)

和${(1-c/N)}^{zN}\approx \exp (-cZ)$，因此上面的表达式可以渐近近似为

$$P_M\simeq \frac{{(N(N-1)/2)}^M}{M!}{\left[\frac{c}{N}\right]}^M\exp (-c(N-1)/2).$$ (5)

代入 $\overline{M}=c(N-1)/2$，这将渐进地导致 泊松分布，均值为 $\overline{M}$，

$$P_M\simeq \exp \left(-\overline{M}\right)\frac{{\overline{M}}^M}{M!}.$$ (6)

边数$M$的波动可以通过$P_M$的标准差来估计，

$$\sigma (M)=\sqrt{\overline{{(M-\overline{M})}^2}}=\sqrt{\overline{M^2}-{\overline{M}}^2}.$$ (7)

我们首先计算

$\overline{M^2}$ $=$ $\overline{M}+\overline{M(M-1)}$ (8)

$=$ $\overline{M}+{\displaystyle \sum _{M=0}^{\mathrm{\infty }}}M(M-1)P_M$

$=$ $\overline{M}+\exp \left(-\overline{M}\right){\displaystyle \sum _{M=2}^{\mathrm{\infty }}}{\displaystyle \frac{{\overline{M}}^M}{(M-2)!}}$

$=$ $\overline{M}+{\overline{M}}^2\exp \left(-\overline{M}\right){\displaystyle \sum _{m=0}^{\mathrm{\infty }}}{\displaystyle \frac{{\overline{M}}^m}{m!}}$

$=$ $\overline{M}+{\overline{M}}^2.$

在第三行中，我们消除了由于 $M(M-1)$ 因素而消失的情况 $M=0,1$，在第四行中我们引入了 $m=M+2$，它从 0 运行到$\mathrm{\infty }$。 可以进行求和并给出$\exp (\overline{M})$。 使用方程式(7) 因此我们发现

$$\sigma (M)=\sqrt{\overline{M}},$$ (9)

这是中心极限定理的特例。 $\overline{M}=c(N-1)/2\to \mathrm{\infty }$的相对波动$\sigma (M)/\overline{M}=1/\sqrt{\overline{M}}$衰减为零，见图3。 在此限制下，边缘数的样本间波动变得越来越不重要，并且出于大多数实际考虑，可以用 $𝒢(N,\overline{M})$ 来识别系综 $𝒢(N,c/N)$。

[htb]

$\overline{M}=10,100,1000$ 的边数分布，按 $\overline{M}$ 重新缩放。 随着 $\overline{M}$ 的增加，分布明显变得尖锐。

学位分布

现在让我们讨论该图的度数。 我们感兴趣的是随机选择的顶点恰好具有 $d$ 度数的概率 $p_d$。所有$p_d$的集合称为度分布。 可以很容易地计算出：

$$p_d=\left(\genfrac{}{}{0pt}{}{N-1}{d}\right){\left[\frac{c}{N}\right]}^d{\left[1-\frac{c}{N}\right]}^{N-d-1}.$$ (10)

右侧术语的含义如下：因子 $\left(\genfrac{}{}{0pt}{}{N-1}{d}\right)$ 枚举 $d$ 潜在邻居的所有可能选择。 这些顶点中的每一个都以$c/N$的概率连接到中心顶点，而其他$N-d-1$顶点不允许与中心顶点相邻，即。即，它们各自贡献一个因子$(1-c/N)$。 在大$N$限制中​​，任何固定度$d$与图顺序$N$相比都很小，我们可以以类似的方式继续最后一小节并找到

$p_d$ $=$ $\underset{N\to \mathrm{\infty }}{lim}{\displaystyle \frac{(N-1)(N-2)\mathrm{\cdots }(N-d)}{N^d}}{\left[1-{\displaystyle \frac{c}{N}}\right]}^{N-d-1}{\displaystyle \frac{c^d}{d!}}$ (11)

$=$ $e^{-c}{\displaystyle \frac{c^d}{d!}},$

我。即，度数也根据泊松分布进行分布。 显然是归一化的，平均度为

${\displaystyle \sum _{d=0}^{\mathrm{\infty }}}d{p}_d$ $=$ ${\displaystyle \sum _{d=1}^{\mathrm{\infty }}}{e}^{-c}{\displaystyle \frac{c^d}{(d-1)!}}$ (12)

$=$ $c.$

这是很清楚的，因为任何顶点的邻居的预期数量是 $p(N-1)\to c$。 另请注意，该值的波动再次由标准差 $\sigma (c)=\sqrt{c}$ 给出，但如果 $c=𝒪(1)$ 则仍与 $c$ 相当。 因此，顶点之间的度波动也存在于热力学极限内，例如。例如，完全隔离的所有顶点的一小部分$e^{-c}$。

如果我们随机选择一条边并询问其一个末端顶点的度数，我们显然会发现不同的概率分布$q_d$，例如。例如，无法达到零度 ($q_0=0$)。 这个概率显然与 $p_d$ 以及 $d$ 成正比，通过归一化，我们发现

$$q_d=\frac{d{p}_d}{{\sum }_{d}d{p}_d}=\frac{d{p}_d}{c}=e^{-c}\frac{c^{d-1}}{(d-1)!}$$ (13)

对于所有$d>0$。 以这种方式选择的顶点的平均度数等于$c+1$，它包括所选边以及平均$c$附加多余边。 这些附加边的数量$d-1$将被表示为所考虑的顶点的过度度。

循环和局部树状结构

度数是最简单的局部属性。 我们可能会稍微超出这个范围，并要求小子图的平均数量。 让我们从 $k$ 顶点的子树开始，这些顶点因此具有 $k-1$ 边。 我们专注于标记的子树（即，顶点出现的顺序很重要），这些子树不一定是诱导的（即，可能有附加的边连接未计算在内的树的顶点）。 他们的预期数量与

$N(N-1)\mathrm{\cdots }(N-k+1){\left[{\displaystyle \frac{c}{N}}\right]}^{k-1}$ $=$ $N{c}^{k-1}+𝒪(1),$ (14)

指定$k-1$可能的$k(k-1)/2$特定边缘的组合因素被省略。 因此，这个数字随着图形顺序 $N$ 线性增长。另一方面，如果我们寻找有限长度的循环 $k$，我们必须找到 $k$ 边。 上述表达式需要一个附加因子 $c/N$，因此预期的周期数为 $𝒪(1)$，即。即，即使图形变得无限大，三角形、正方形等的数量仍然是有限的！ 如果人们将 $K_k$ 与 $k\ge 4$ 视为派系，情况会变得更加严重，如果 $N$ 变大，这些派系就会变得越来越可能完全不存在。 因此，如果我们在局部查看任何有限大小 $k$ 的诱导子图，这些几乎肯定是树木或森林。 该属性被表示为局部树形。

然而，也有循环，但它们的长度是$𝒪(\ln N)$[16]。 在统计物理方法中，我们将看到这些循环具有根本重要性，即使它们的长度不同。

另一个侧面评论涉及图的维数，即。即，在有限维空间中“绘制”大图的可能性。 如果查看任何 $D$ 维晶格，距离 $k$ 的邻居数量会随着 $k^D$ 的增长而增长。 另一方面，在平均度数固定的树中，这个数字呈指数级增长！ 从这个意义上说，随机图必须被认为是无限维的。 这乍一听起来很奇怪，但最终解释了本书后面将观察到的分析易处理性。

4 相变：巨型组件的出现

来自 Sec. 2 我们知道具有 $p=c/N$ 的随机图几乎肯定没有连接。 关于组件我们能说些什么？

考虑到上述的生长过程，我们可以想象，对于小的$c$来说，有许多小的组件，几乎所有的组件都是树。 如果 $c$ 增加，我们将添加新的边，并且一些先前断开连接的组件现在变为连接的。 组件数量减少，组件顶点数量（顺序）增加。 着眼于图 $G$ 的最大组成部分 $L^{(0)}(G)$，Erdős 和 Rényi [15] 于 1960 年证明了以下定理：

定理： 让$c>0$和$G_c$从$𝒢(N,c/N)$中绘制。 设置$\alpha =c-1-\ln c$。

(i) 如果 那么我们几乎肯定会发现

$$|L^{(0)}(G_c)|=\frac{1}{\alpha }\ln N+𝒪(\ln \ln N)$$

(ii) 如果 $c>1$ 我们几乎肯定有

$$|L^{(0)}(G_c)|=\gamma N+𝒪(N^{1/2})$$

其中 是唯一的解决方案

$$1-\gamma =e^{-c\gamma }.$$

所有较小的组件的顺序都是$𝒪(\ln N)$。

这个定理给出了一个非常有力的陈述：只要，所有组件的顺序都达到$𝒪(\ln N)$。 如果 $c>1$，则情况会发生显着变化。 出现一个巨型组件连接所有顶点的有限部分，但所有其他组件与巨型组件相比仍然很小，它们只有$𝒪(\ln N)$顶点。 这意味着在$c=1$时系统会经历相变。 与物理相变相反，它不是由温度、压力或其他外部控制参数的变化引起的，而是由平均顶点度$c$的变化引起的，即。即，通过图表的结构参数。 由于与渗流理论[17]有明显的相似性，这种相变在文献中也被称为随机图渗流。

该定理是随机图论最基本的结果之一，但我们没有提供完整的证明。 然而，有一个简单的论点，即组件结构在 $c=1$ 处发生变化。 它基于所有组件的局部树状结构，并在极限$N\to \mathrm{\infty }$中呈现。

如果我们选择任何顶点，平均而言它将有 $c$ 个邻居。 根据方程。 (13)，每个顶点都会有 $c$ 个额外的邻居，因此第一个顶点平均有 $c^2$ 个第二个邻居。 重复这个论证，我们得出结论，第 $k$ 个邻居的预期数量等于 $c^k$ （顶点 $j$ 称为第 $k$ 个邻居顶点$i$（如果图中连接两者的最小路径$G$恰好包含$k$边）。

现在我们可以看到 和 $c>1$ 差异的根源。 在第一种情况下，规定的过程呈指数下降，很可能在几步之后就消失了。 相反，如果我们有 $c>1$，则第 $k$ 个邻居的预期数量呈指数增长。 尽管如此，该过程在几个步骤后死亡的概率是有限的（例如，如果在第一步中死亡，即如果根本没有邻居，则 $e^{-c}$ ），但也有一个有限的概率永远进行下去的概率。

[htb]

顶点不属于巨型组件的概率的迭代解的示意图。 第一行显示随机边到达的顶点的自洽方程：带有半边的黑色方块表示到达的顶点未通过其多余边之一连接到巨型组件的概率。 发生这种情况的原因是它没有其他邻居，或者它连接到一个、两个等未与巨型组件连接的顶点。 第二行显示随机选择的顶点的结果方程，如阴影方块所示。

通过考虑以下迭代构造，可以使该论证更加严格：首先，我们计算概率$\pi$，即随机选择的链接的随机选择的末端顶点不通过其他边与图表。 在图 4 中，这由连接到半边的黑色方块表示。 该顶点可以具有一度，即。即，它没有其他能够将其连接到巨型组件的入射边，或者它连接到其他顶点，而这些顶点本身并未通过其多余边连接到巨型组件。 考虑到几乎所有小的连接组件都是树，这些邻居仅通过选定的顶点相互连接，并且 $d$ 邻居不连接到巨型组件的概率简单地等于 ${\pi }^d$. 使用概率分布$q_d$方程。 (13) 是随机边到达的顶点的度数，因此我们发现：

$\pi$ $=$ $q_1+q_2\pi +q_3{\pi }^2+q_4{\pi }^3+\mathrm{\dots }$ (15)

$=$ ${\displaystyle \sum _{d=1}^{\mathrm{\infty }}}{e}^{-c}{\displaystyle \frac{c^{d-1}}{(d-1)!}}{\pi }^{d-1}=e^{-c}{\displaystyle \sum _{d^{\prime }=0}^{\mathrm{\infty }}}{\displaystyle \frac{{(c\pi )}^{d^{\prime }}}{(d^{\prime })!}}$

$=$ $e^{-c(1-\pi )}.$

因此，对于 $c$ 的每个值都可以自洽地确定该量，并允许我们计算随机选择的顶点不属于巨型组件的概率 $1-\gamma$。 应用与之前类似的参数，该顶点可以是孤立的，也可以仅连接到其他顶点，这些顶点通过其多余的边不连接到巨型组件，参见图4的第二行。 由此我们发现

$1-\gamma$ $=$ $p_0+p_1\pi +p_2{\pi }^2+p_3{\pi }^3+\mathrm{\dots }$ (16)

$=$ ${\displaystyle \sum _{d=1}^{\mathrm{\infty }}}{e}^{-c}{\displaystyle \frac{c^d}{d!}}{\pi }^d$

$=$ $e^{-c(1-\pi )}.$

从这些方程中，我们首先看到，对于我们的随机图，$\pi =1-\gamma$。 将其代入最后一行，我们得到方程

$$1-\gamma =e^{-c\gamma }$$ (17)

正如定理中给出的。

[htb]

属于随机图最大组成部分的顶点分数，作为平均度 $c$ 的函数。这些符号是 $N=100,1000$ 的数值数据，始终超过 100 个随机生成的图表的平均值。 实线给出了渐近分析结果：在$c=1$之下，最大的分量是次广延的，在它之上是广延的。

让我们简单讨论一下$\gamma (c)$的形状。 对于$c=1+\epsilon$，与一样，我们也期望$\gamma$很小，并将上式在$\gamma$中展开为二阶：

$$1-\gamma =1-(1+\epsilon )\gamma +\frac{1}{2}{(1+\epsilon )}^2{\gamma }^2+𝒪({\gamma }^3).$$ (18)

术语 $1-\gamma$ 在两侧都取消。 除以 $\gamma$，并仅保留 $\epsilon$ 和 $\gamma$ 中的第一个顺序，因此我们发现

$$\gamma =2\epsilon .$$ (19)

因此，巨型组件的相对阶数开始在 $c-1$ 中线性增长（我们说巨型组件的临界指数等于 1），并且对于较大的 $c$ ，以指数方式快速收敛到 1。图 4 给出了完整的曲线以及有限随机图的数值数据。

5巨型toc的出现$q$toc$𝒒$-core

在秒。 5，我们引入了图的$q$核心作为最小顶点度数至少为$q$的最大子图。 最近，B. Pittel、J. Spencer 和 N. C. Wormald [18] 在一篇精彩的论文中解决了随机图中存在 $q$ 核的问题：准确分析那里给出的线性时间算法。 在这里，我们将给出他们的方法的易于理解的总结，不包括数学证明的技术细节。

让我们首先从数值实验开始：我们生成了具有 $N=\mathrm{50\hspace{0.17em}000}$ 顶点和各种平均度数 $c$ 的中等大小随机图，并应用了 $q$ -$q=2$和$q=3$的核心算法。 $q=2$ 的结果并不是非常令人惊讶：直到 $c=1$，2 核非常小，而它开始占据 $c>1$ 的所有顶点的有限部分t2>。 这与上一节在巨型组件上得到的结果是一致的：只要后者不存在，几乎所有顶点都收集在有限树中，因此不属于2核。 然而，在 $c=1$ 附近观察，可以看到巨型组件的出现存在微小差异。 而巨大的分量开始随着距临界点的距离线性增长，请参见等式： (19)，2芯以零斜率出现，见图5。 这意味着两个过程的临界指数似乎彼此不同。

$q\ge 3$ 的情况发生了巨大变化。 在相应的阈值 $c(q)$（随 $q$ 单调增加）处，$q$-核心出现不连续 – 立即统一有限分数所有顶点。 对于$q=3$，发现阈值是$c(3)\simeq 3.35$。 略低于这个平均程度，几乎所有图都没有广泛的 $q$ 核心。 在转变时，$3$核心的顺序突然跳到大约$0.27N$，即。即，它包含大约 27% 的所有顶点！

[htb]

属于 $q=2$（圆形）和 $q=3$（菱形）的 $q$ 核心的顶点分数。 数值数据来自 $N=\mathrm{50\hspace{0.17em}000}$ 顶点的单个图。 垂直线给出了阈值$c=3.35.$下3核大小的理论值

沃莫尔德法

描述这种行为的方法是由 Wormald [19] 在数学上提出的，然而，它是众所周知的，并以速率方程的名称应用于物理学。 它分析了 $q$ 核心算法的稍微修改版本。 在每个算法步骤中，仅随机选择一个度数小于 $q$ 的顶点并将其从图中删除。 Pittel等人分析中计算出的量是度分布$p_d$，它在算法抽取下发生变化。 这显然是确定算法停止点的完美候选者。 如果$p_d=0$对于所有，则剩余的子图是$q$-核心。

分析中的一个重要点（这里不会在数学上证明）是图动力学在热力学极限$N\to \mathrm{\infty }$内自平均。 经过一定数量的$T=tN=𝒪(N)$算法步骤后，几乎所有随机图都具有相同的度分布，这也几乎肯定与抽取顶点的随机顺序无关。 从技术上讲，这使我们能够对两种随机性进行平均，并确定算法的平均或预期行为。

在上一段中，我们已经通过引入时间$t=T/N$来重新调整算法步骤的数量。 即使在热力学极限下，这个量仍然是有限的，最初从 $t=0$ 运行到最多 $t=1$，其中完整的图将被删除。 进一步，该量以步骤$\mathrm{\Delta }t=1/N$前进，并因此在大$N$极限内变得连续。 最后的观察将使我们能够使用微分方程而不是离散时间差异。

在这些介绍性评论之后，我们可以通过首先注意到总顶点数演变为 $N(T)=(1-t)\cdot N$ 来开始分析，因为我们每一步删除一个顶点。 稍后介绍在$t=T/N$时刻有$d$个邻居的顶点数$N_d(T)$，以及对应的度分布$p_d(t)=N_d(T)/N(T)$，我们可以写出第$(T+1)$步骤中$N_d$的预期变化。 它包含两个不同的贡献：

• 第一个贡献涉及删除的顶点本身。 它仅出现在 $N_d$ 与 的方程中，因为没有删除当前度数较高的顶点。

• 第二个贡献来自于被移除顶点的邻居。 他们的度数减少一。

因此，我们找到下面的等式，其中我们详细解释了术语的含义：

$$N_d(T+1)-N_d(T)=-\frac{{\chi }_d{p}_d(t)}{\overline{\chi }}+\frac{\overline{d\chi }}{\overline{\chi }}\left[-\frac{d{p}_d(t)}{c(t)}+\frac{(d+1)p_{d+1}(t)}{c(t)}\right]$$ (20)

对所有学位$d$都有效。这里我们引入了 ${\chi }_d$ 作为度数最多 $q-1$ 的顶点的指示符，即。即，如果 则等于 1，否则等于 0。 与之前一样，上横线表示图表的平均值，i。例如，$\overline{\chi }={\sum }_d{\chi }_d{p}_d(t)$ 和 $\overline{d\chi }={\sum }_{d}d{\chi }_d{p}_d(t)$。 请注意，即使没有明确说明，这些平均值现在也取决于时间。 我们保留 $c(t)\equiv \overline{d}={\sum }_{d}d{p}_d(t)$ 的显式表示法。 所有项都具有以下形式：它们是相应过程在一步中平均发生的频率以及相应过程影响 $d$ 度顶点的概率的乘积。等式右边的第一项。 (20) 描述了所选顶点的移除（即，此过程在每个步骤中仅发生一次），指标 ${\chi }_d$ 保证仅度数为 第二项包含邻居：平均而言，有 $\overline{d\chi }/\overline{\chi }$ 个邻居，每个邻居的度数为 $d$，概率为 $q_d(t)=d{p}_d(t)/c(t)$。 损失项源自度数 $d$ 的顶点，然后再移除其关联边之一，增益项则源自度数 $d+1$ 的顶点。

在热力学极限中，方程左侧的差异。 (20) 成为导数：

$N_d(T+1)-N_d(T)$ $=$ ${\displaystyle \frac{(1-t+\mathrm{\Delta }t)p_d(t+\mathrm{\Delta }t)-(1-t)p_d(t)}{\mathrm{\Delta }t}}$ (21)

$=$ ${\displaystyle \frac{d}{dt}}\left\{(1-t)p_d(t)\right\}.$

最后两个方程得出度分布的一组封闭方程，

$$\frac{d}{dt}\left\{(1-t)p_d(t)\right\}=-\frac{{\chi }_d{p}_d(t)}{\overline{\chi }}+\frac{\overline{d\chi }}{\overline{\chi }}[-\frac{d{p}_d(t)}{c(t)}+\frac{(d+1)p_{d+1}(t)}{c(t)},]$$ (22)

这将在下文中解决。 首先，我们推导出 $p_d(t)$ 上平均值的一些全局方程。 最简单的一个可以通过对等式求和得到。 (22) 覆盖所有 $d$，这给出了平凡的一致性关系 $\frac{d}{dt}(1-t)=-1$。 首先乘以方程可以得到一个更有趣的方程。 (22) 除以 $d$，然后对所有 $d$ 求和。引入简写符号$m(t)=(1-t)c(t)$，我们发现

$\dot{m}(t)$ $=$ ${\displaystyle \frac{d}{dt}}\left\{(1-t){\displaystyle \sum _d}d{p}_d(t)\right\}$ (23)

$=$ ${\displaystyle \frac{\overline{d\chi }}{\overline{\chi }}}\left[-1-{\displaystyle \frac{\overline{d^2}}{c(t)}}+{\displaystyle \frac{\overline{d(d-1)}}{c(t)}}\right]$

$=$ $-2{\displaystyle \frac{\overline{d\chi }}{\overline{\chi }}}.$

初始条件为$m(t=0)=c$。

然而，求解方程 (21) 的主要问题是它们形成了一组无限的非线性微分方程。 因此，直接的解决方案远非显而易见。 我们的救赎在于这样一个事实：该算法从不直接触及 $d\ge q$ 度的顶点。 这些顶点仅通过随机删除其入射边之一来改变其属性。 因此，它们保持随机连接结构和泊松形状，只有有效连接发生变化。 这可以使用 ansatz 进行验证，其中 $\beta (t)$ 是有效连接 ($\beta (0)=c$)：

$$(1-t)p_d(t)=\frac{N_d(T)}{N}\stackrel{!}{=}{e}^{-\beta (t)}\frac{\beta {(t)}^d}{d!},\forall d\ge q.$$ (24)

这个 ansatz 引入了彻底的简化。 无限数量的概率由一个参数 $\beta (t)$ 参数化。 这个 ansatz 的有效性可以通过将其代入方程来证明。 (21) 任意 $d$。我们得到左侧

$$\mathrm{l}.\mathrm{h}.\mathrm{s}.=\dot{\beta }(t)[e^{-\beta (t)}\frac{\beta {(t)}^{d-1}}{(d-1)!}-e^{-\beta (t)}\frac{\beta {(t)}^d}{d!}]$$ (25)

对于右侧

$$\mathrm{r}.\mathrm{h}.\mathrm{s}.=\frac{\overline{d\chi }}{\overline{\chi }}[-e^{-\beta (t)}\frac{\beta {(t)}^d}{(d-1)!(1-t)c(t)}+e^{-\beta (t)}\frac{\beta {(t)}^{d+1}}{d!(1-t)c(t)}].$$ (26)

它们对于所有 $d\ge q$ 必须相等，我们可以比较两边同阶单项式的分量：

$$\dot{\beta }(t)=-\frac{\beta (t)}{m(t)}\frac{\overline{d\chi }}{\overline{\chi }}.$$ (27)

因此，方程在 ansatz (24) 下变得封闭，并且 $p_d(t)$ 不再有无数个方程，$d=q,q+1,\mathrm{\dots },$ 只有一个 $\beta (t)$ 仍然存在。 有趣的是，这个等式中的 $q$ 依赖性被删除了。

如果我们比较方程 (23) 和 (27)，我们发现

$$2\frac{\dot{\beta }(t)}{\beta (t)}=\frac{\dot{m}(t)}{m(t)}$$ (28)

使用初始条件，可以通过以下方式求解

$$m(t)=\frac{\beta {(t)}^2}{c}.$$ (29)

因此，函数 $m(t)$ 可以替换为等式（1）。 (27)，我们得到

$$\dot{\beta }(t)=-\frac{c}{\beta (t)}\frac{\overline{d\chi }}{\overline{\chi }}.$$ (30)

下一步，我们仍然需要从最后一个方程中删除 $\overline{\chi }$ 和 $\overline{d\chi }$。 当应用等式时，这可以通过使用归一化来获得。 (24)

$1$ $=$ ${\displaystyle \sum _{d=0}^{\mathrm{\infty }}}{p}_d(t)$ (31)

$=$ ${\displaystyle \sum _{d=0}^{\mathrm{\infty }}}{\chi }_d{p}_d(t)+{\displaystyle \sum _{d=q}^{\mathrm{\infty }}}{\displaystyle \frac{1}{1-t}}{e}^{-\beta (t)}{\displaystyle \frac{\beta {(t)}^d}{d!}}$

$=$ $\overline{\chi }+{\displaystyle \frac{1}{1-t}}{F}_q(\beta (t)).$

同理，我们得到平均度$c(t)$：

$$F_q(\beta ):=1-\sum _{d=0}^{q-1}{e}^{-\beta }\frac{{\beta }^d}{d!},$$ (32)

和

$c(t)$ $=$ ${\displaystyle \sum _{d=0}^{\mathrm{\infty }}}d{p}_d(t)$ (33)

$=$ ${\displaystyle \sum _{d=0}^{\mathrm{\infty }}}d{\chi }_d{p}_d(t)+{\displaystyle \sum _{d=q}^{\mathrm{\infty }}}{\displaystyle \frac{d}{1-t}}{e}^{-\beta (t)}{\displaystyle \frac{\beta {(t)}^d}{d!}}$

$=$ $\overline{d\chi }+{\displaystyle \frac{\beta (t)}{1-t}}{F}_{q-1}(\beta (t)).$

将其插入方程。 (30)，并使用等式： (29) 消除$c(t)=m(t)/(1-t)$,$\beta (t)$ 的方程最终变为：

$$\dot{\beta }(t)=-\frac{\beta (t)-c{F}_{q-1}(\beta (t))}{1-t-F_q(\beta (t))}.$$ (34)

因此，我们成功地将无限集 (22) 简化为单个方程。 (34)！ 尽管如此，这个方程是非线性的，因此对于任意的 $q$ 来说不容易求解。 然而，即使不一直求解该方程，而是通过仅确定算法的停止点（即 $q$)，也可以获得有关 $q$ 核心的重要信息。 -输入图的核心。

假设该图有一个巨大的 $q$ 核心。 它包含 $N(t_f)=(1-t_f)N$ 个顶点，其中 是算法的停止时间。 此时，所有剩余顶点的度数都是 $d\ge q$，因此我们有 $\overline{\chi }=\overline{d\chi }=0$ 和 ${\beta }_f=\beta (t_f)>0$。 根据 (31,33) 我们有

$1-t_f$ $=$ $F_q({\beta }_f)$

${\displaystyle \frac{{\beta }_f}{c}}$ $=$ $F_{q-1}({\beta }_f).$ (35)

第二个方程固定了${\beta }_f$，而$t_f$本身以及巨大的$q$核心的顺序直接来自第一个方程。 如果${\beta }_f$有两个或多个解决方案，则必须选择小于$c$的最大解决方案。 $\beta (t)$ 的初始条件是 $\beta (0)=c$，并且等式： (34) 产生负斜率，即。即，$\beta (t)$ 随着时间的推移而减少。

案例$𝒒\mathbf{=}\mathrm{𝟐}$

让我们首先考虑仅 $q=2$ 颜色的情况。 从数值实验中我们看到，随机图的 2 核似乎以平均程度 $c=1$ 连续设置。 我们可以从等式(5)开始确认这一点吗？

${\beta }_f=\beta (t_f)$ 的自洽方程变为

$$\frac{{\beta }_f}{c}=1-e^{-{\beta }_f},$$ (36)

如图5所示。 右侧从 $\beta =0$ 开始，斜率为 1，并渐近趋于 1。 左侧是斜率$1/c$的直线。 对于，方程的唯一解。 (36) 因此由 ${\beta }_f=0$ 给出，根据第一个方程 (5) 对应于 $1-t_f=0$，并且2 核的尺寸正在消失。 在 $c>1$ 处，右侧在原点处具有较小的斜率，但对于较大的 $\beta$ 仍然发散。 因此，这两条曲线有第二个交叉点 ${\beta }_f>0$，根据上一节末尾的讨论，必须选择该交叉点作为相关解。 然而，非零 ${\beta }_f$ 意味着非零 $1-t_f$，并且 2 核统一了随机图所有顶点的有限部分。

[htb]

方程的图形解(36)：实线显示$F_1(\beta )$，直线有斜率$1/c_i$和。 解由曲线之间的最大交叉点给出。 对于 $c\le 1$，唯一的交叉出现在 $\beta =0$ 中。 对于$c>1$，存在第二个正解。 它由箭头标记。

请注意，方程的非零解。 (36) 在 $c(2)=1$ 连续设置。 如果我们用 修复稍大的 $c=1+\epsilon$，我们发现

$$\frac{{\beta }_f}{1+\epsilon }=1-e^{-{\beta }_f}.$$ (37)

在 ${\beta }_f$ 和 $\epsilon$ 中展开这个方程，我们得到

$${\beta }_f(1-\epsilon +𝒪({\epsilon }^2))={\beta }_f\left(1-\frac{{\beta }_f}{2}+𝒪({\beta }_f^2)\right)$$ (38)

因此$\epsilon ={\beta }_f/2$。 对于停止时间，以及 2 核的大小，我们有

$1-t_f$ $=$ $1-e^{-{\beta }_f}(1+{\beta }_f)$ (39)

$=$ ${\displaystyle \frac{{\beta }_f^2}{2}}+𝒪({\beta }_f^3)$

$=$ $2{\epsilon }^2+𝒪({\epsilon }^3).$

因此，2 核渗透的临界指数为 $2$，这与本节开头提出的数值结果完全一致。

案例$q=3$

对于$q=3$,${\beta }_f=\beta (t_f)$的自洽方程变为

$$\frac{{\beta }_f}{c}=1-e^{-{\beta }_f}(1+{\beta }_f),$$ (40)

图形解决方案见图5。 与 2 核的重要区别在于，对于 $q=3$，右侧从斜率零开始。 因此，从解 $\beta =0$ 中连续发展出非零交叉点是不可能的。 事实上，直到$c(3)\simeq 3.35$，不存在进一步的交叉点，并且随机图的巨型分量的存在显然不足以证明巨型3核的存在。 然而，在$c(3)\simeq 3.35$处，两条曲线在一点${\beta }_f>0$处相互接触，如图5中的实线箭头所示，并且两个新的解决方案出现。 正如已经讨论过的，较大的一个是正确的。

[htb]

方程的图形解(40)：实线显示$F_2(\beta )$，直线有斜率$1/c_i$和。 解由曲线之间的最大交叉点给出。 对于 $c\le 3.35$，唯一的交叉出现在 $\beta =0$ 中。 对于$c>3.35$，存在另外两个正解。 正确的由箭头标记。

方程中新解的不连续出现。 (40) 也会导致 3 核的不连续出现。 正如在实验中观察到的，后者在 $c(3)\simeq 3.35$ 处从零大小跳跃到所有顶点的约 27%。 如果我们考虑更大的 $q$，例如，这一点会变得更加明显。例如，4 核出现在 $c(4)\simeq 5.14$ 处，并包含 $0.43N$ 顶点，5 核仅出现在 $c(5)\simeq 6.81$ 处，甚至包含 $0.55N$ 顶点。

随机图着色的结果

直接的结果是，我们看到几乎所有带有 的图形都可以用 $q$ 颜色着色，或者，以不同的方式表示，带有 的图形的色数几乎可以肯定，它的边界是 $q$。 当然，它也可以更小。 我们知道$q$核的存在不足以使图无法用$q$颜色着色，见图1.9。 正如1.8页定理证明中所述，$q$核心算法的反转可用于扩展$q$-的着色在线性时间内从核心到完整的图。 所以我们看到，即使问题在最坏的情况下很困难，几乎所有 的图都可以仅用 $q$ 颜色有效地着色。

Pittel、Spencer 和 Wormald 给出的分析与我们在第 1 章中给出的简单线性时间算法的分析非常相似。 8. 一般来说，算法的概率分析能够为几乎所有随机图的属性提供有用的界限。