随机图理论基础。

# 符号约定

在这篇文章中，我们约定以花体 \mathscr 表示集族，以空心大写字体 \mathbb 表示概率范畴下的量，如概率 $\mathbb{P}$, 期望 $\mathbb{E}$, 方差 $\mathbb{D}$ 等。对于一般的图，我们以正常的大写字母 $G$ 表示。

# 随机图模型基础

# 定义

定义 1 以$𝒢_{n,m}$ 表示含有$n$ 个顶点，$m$ 条边的所有图组成的集合。对每个$G \in 𝒢_{n,m}$，定义概率$\mathbb{P}(G) = \binom{\binom{n}{2}}{m}^{-1}$。这样，我们将通过$n$ 个顶点按此概率生成的图称为一个标准随机图 (uniform random graph)，记作$\mathbb{G}_{n,m} = ([n],E_{n,m})$。

定义 2
此外，我们引入一个概率$p \in [0,1]$ 作为在图中加入一条边的概率。于是得到图$G \in 𝒢_{n,m}$ 的概率为$\mathbb{P}(G) = p^m(1-p)^{\binom{n}{2}-m}$。我们将按此概率生成的图称为一个二项随机图 (binomial random graph)，记作$\mathbb{G}_{n,p} = ([n],E_{n,p})$。

随机图的这两个模型之间存在明显的相关关系。比如，如果确定$\mathbb{G}_{n,p}$ 的边数为$m$，则边数为$m$ 的各图的出现是等可能的，概率均为$\binom{\binom{n}{2}}{m}^{-1}$。这根据条件概率显然可以得到。

对于数目较大的$n$，我们认为在边出现的概率为$p$ 的前提下，边数$m$ 的最可能值为$m = \binom{n}{2}p \approx \tfrac{n^2p}{2}$。或者说$p \approx \tfrac{2m}{n^2}$，此时两种图将会产生相似的性质。下面，我们将进一步量化相似性质这一概念。

引理 1 我们定义图的性质$𝒫$是$𝒢_{n}$ 的一个子集，设概率$p = m/\binom{n}{2}$，其中$m = m(n) \to \infty$，且$\binom{n}{2}-m \to \infty$。则对于充分大的$n$，我们有

$$\frac{1}{\sqrt{2\pi m}}\mathbb{P}(\mathbb{G}_{n,m} \in 𝒫) \leq \mathbb{P}(\mathbb{G}_{n,p}\in \mathbb{P})\leq \frac{1}{\sqrt{2\pi}}\binom{n}{2}\mathbb{P}(\mathbb{G}_{n,m} \in 𝒫).$$

证明

$$\mathbb{P}(\mathbb{G}_{n,p} \in 𝒫) = \sum_{k=0}^\binom{n}{2}\mathbb{P}(\mathbb{G}_{n,p}\in 𝒫||E_{n,p}| = k)\mathbb{P}(|E_{n,p}| = k) = \sum_{k=0}^\binom{n}{2}\mathbb{P}(\mathbb{G}_{n,k}\in 𝒫)\mathbb{P}(|E_{n,p}| = k) ≥ \mathbb{P}(\mathbb{G}_{n,m}\in 𝒫)\mathbb{P}(|E_{n,p}| = m).$$

根据斯特林公式$k!≈\sqrt{2\pi k}(\tfrac{k}{e})^k$ 估计$\mathbb{P}(|E_{n,p}| = m)$，并简记$\binom{n}{2} ≜ N$，有

$$\mathbb{P}(|E_{n,p}| = m) = \binom{N}{m}p^m(1-p)^{N-m} ≈ \frac{\sqrt{2\pi N}N^N p^m(1-p)^{N-m}}{2\pi\sqrt{m(N-m)}}\approx \sqrt{\frac{N}{2\pi m (N-m)}} \geq \frac{1}{\sqrt{2\pi m}}.$$

代入原式即可证明。

同样地，我们也可以向上放缩，得到$\mathbb{P}(\mathbb{G}_{n,p} \in 𝒫) = \sum_{k=0}^\binom{n}{2}\mathbb{P}(\mathbb{G}_{n,p}\in 𝒫||E_{n,p}| = k)\mathbb{P}(|E_{n,p}| = k) = \sum_{k=0}^\binom{n}{2}\mathbb{P}(\mathbb{G}_{n,k}\in 𝒫)\mathbb{P}(|E_{n,p}| = k) ≤ \binom{n}{2}\mathbb{P}(\mathbb{G}_{n,m}\in 𝒫)\mathbb{P}(|E_{n,p}| = m).$

同样根据斯特林公式估计，有

$$\mathbb{P}(|E_{n,p}| = m) = \binom{N}{m}p^m(1-p)^{N-m} ≈ \frac{\sqrt{2\pi N}N^N p^m(1-p)^{N-m}}{2\pi\sqrt{m(N-m)}}\approx \sqrt{\frac{N}{2\pi m (N-m)}} \leq \frac{1}{\sqrt{2\pi}}.$$

此时代入上式，可得

$$\sqrt{2\pi}\mathbb{P}(\mathbb{G}_{n,p} \in 𝒫) \leq \binom{n}{2}\mathbb{P}(\mathbb{G}_{n,m} \in 𝒫).$$

即原式成立。

但是，我们发现上面的估计是不准确的，且可以构造出几乎取到等号的例子。于是我们考虑对性质$𝒫$加以限制，得到更好的估计。

定义 2 如果$G \in 𝒫$蕴含$G+e \in 𝒫$，那么我们称性质$𝒫$是单调递增的 (monotone increasing)。例如，图的连通性和哈密顿性 (即是否为哈密顿图) 是单调递增的，但是否为欧拉图不是单调递增的。如果空图$\bar K_n \notin 𝒫$且完全图$K_n \in 𝒫$，那么我们称性质$𝒫$是不平凡的。类似地，如果$G \in 𝒫$蕴含$G-e \in 𝒫$，那么我们称性质$𝒫$是单调递减的 (monotone decreasing)。例如，图的平面性 (是否为平面图) 是一个单调递减的。

显然，若性质$𝒫$是单调递增的，那么$\bar 𝒫$是单调递减的。于是，在通常情况下，只需要考虑单调递增的性质。

对于单调递增的性质$𝒫$，我们容易得到若$p<p'$，$m<m'$，则$\mathbb{P}(\mathbb{G}_{n,p} \in 𝒫) \leq \mathbb{P}(\mathbb{G}_{n,p'} \in 𝒫)$，$\mathbb{P}(\mathbb{G}_{n,m} \in 𝒫) \leq \mathbb{P}(\mathbb{G}_{n,m'} \in 𝒫)$。(构建对应关系则易于证明)

在此基础上，我们可以类似引理 1 给出一个对$\mathbb{G}_{n,m}$ 和$\mathbb{G}_{n,p}$ 的估计。但由于性质$𝒫$是单调的，因此估计会更加准确。

引理 2 对单调递增的性质$𝒫$，若$N = \binom{n}{2}$，$p = \tfrac{m}{N}$，对满足$Np \to \infty$ 且$N(1-p)/(Np)^\tfrac{1}{2} \to \infty$ 的充分大的$N$ 及某概率$p$，有

$$\mathbb{P}(\mathbb{G}_{n,m} \in 𝒫) \leq 3\mathbb{P}(\mathbb{G}_{n,p} \in 𝒫).$$

以上是我们所说的$\mathbb{G}_{n,p}$ 与$\mathbb{G}_{n,m}$ 的关系。于是，我们研究随机图时，可以以其中一个作为突破点进行研究。

对于$\mathbb{G}_{n,p_1}$ 与$\mathbb{G}_{n,p_2}$，我们规定它们的并为$\mathbb{G}_{n,p} = \mathbb{G}_{n,p_1}\cup\mathbb{G}_{n,p_2}$，其中$1-p = 1 - p_1 - p_2 + p_1p_2$。其中，$\mathbb{G}_{n,p_1}$ 与$\mathbb{G}_{n,p_2}$ 独立，其各自生成边后去掉重复的边，就得到了图$\mathbb{G}_{n,p}$。这时我们可以说$\mathbb{G}_{n,p_1} \subseteq \mathbb{G}_{n,p}$。

类似地，对$\mathbb{G}_{n,m_1}$ 和$\mathbb{G}_{n,m_2}$，我们类似地称$\mathbb{G}_{n,m_1+m_2}$ 是$\mathbb{G}_{n,m_1}$ 与$\mathbb{G}_{n,m_2}$ 的并。

# 度序列

我们知道，顶点的度是简单图的一个基本量。对于属于同一图$G \in 𝒢(n,p)$ 的两个相异顶点$x,y \in V$，在$n$ 较大时，我们一般认为两点的度$d_G(x)$ 与$d_G(y)$ 是独立的随机变量

度序列 (degree sequence)

# 排序问题

熟知的是，对$n$ 个元素组成的全序关系，基于比较的排序复杂度为$\mathcal O(n\log n)$ 次。但基于比较的排序存在一个缺点，就是后面的排序对象需要根据前面的答案进行确定。

在排序算法中，我们将宽度 (width) 定义为在任何一轮问题中进行的最大探测数，将深度 (depth) 定义为算法所需要的最大轮数。于是，在不限制宽度和深度的前提下，排序算法的比较次数下限为$\log_2 n!$ 级别。