伴随二部图、图论第一定理

摘要: 图论第一定理

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

二部图是一类结构简单又非常重要的图。在文章 二分图判定定理与算法 中我们介绍过二部图判定定理及算法。

对于任意有向图 $D$，都对应一个二部无向图，称为伴随二部图。伴随二部图的重要应用是证明图论第一定理。

图论第一定理可以用于 Spencer 引理在二维情况下的证明，而 Spencer 引理在布劳威尔不动点定理中有所应用，由布劳威尔不动点定理又可以进一步推导出纳什均衡的存在性。

本文我们首先介绍伴随二部图的构造方法，然后基于伴随二部图，推导出看起来比较显然的图论第一定理。

---

伴随二部图

设 $D = (V(D), E(D), \phi_{D})$ 为有向图，其中：

$$V(D) = \{x_{1}, x_{2}, \cdots, x_{v}\} \\ E(D) = \{a_{1}, a_{2}, \cdots, a_{\epsilon}\} \\$$

构造二部划分为 $\{X, Y\}$ 的 2 部无向图 $G = (X\cup Y, E(G), \phi_{G})$，其中：

$$X = \{x_{1}', x_{2}', \cdots, x_{v}'\} \\ Y = \{x_{1}'', x_{2}'', \cdots, x_{v}''\} \\ E(G) = \{e_{1}, e_{2}, \cdots, e_{\epsilon}\}$$

并且对于 $\forall l = 1, 2, \cdots, \epsilon, e_{l} \in E(G)$ 有：

$$\phi_{G}(e_{l}) = x_{i}'x_{j}'' \Leftrightarrow \exists a_{l} \in E(D), \phi_{D}(a_{l}) = (x_{i}, x_{j})$$

在有向图中每个节点 $x$ 都对应伴随 2 部图的 2 个节点 $x’$ 和 $x’’$，其中 $x’$ 代表有向图上该节点的出边，$x’’$ 代表有向图上该节点的入边。

从 $D$ 的伴随二部图 $G$ 的构造方式可以知道 $v(G) = 2v(D)$，$\epsilon(G) = \epsilon(D)$。

---

图论第一定理

定理(图论第一定理)：对于任意有向图 $D$ 均有：

$$\sum\limits_{x\in V(D)}d_{D}^{+}(x) = \sum\limits_{x\in V(D)}d_{D}^{-}(x) = \epsilon(D)$$

其中 $d_{D}^{+}(x)$ 表示 $x$ 的出度、$d_{D}^{-}(x)$ 表示 $x$ 的入度。该定理说的是对于任意有向图，总出度等于总入度等于总边数。

---

证明：

设 $D$ 是有向图，考虑 $D$ 的伴随二部图 $G$，它的二部划分为 $\{X, Y\}$，于是由伴随二部图的构造方式有：

$$v(G) = 2v(D) \\ \epsilon(G) = \epsilon(D)$$

由于 $\forall x \in V(D)$ 有：

$$d_{G}(x') = d_{D}^{+}(x) \\ d_{G}(x'') = d_{D}^{-}(x)$$

又因为 $G$ 为二部图，因此：

$$\epsilon(G) = \sum\limits_{x\in X}d_{G}(x) = \sum\limits_{y\in Y}d_{G}(y), \quad 2\epsilon(G) = \sum\limits_{x\in V(G)}d_{G}(x)$$

于是：

$$\begin{align} \sum\limits_{x\in V(D)}d_{D}^{+}(x) &= \sum\limits_{x\in X}d_{G}(x') = \epsilon(G) \\ &= \sum\limits_{x\in Y}d_{G}(x'') = \sum\limits_{x\in V(D)}d_{D}^{-}(x) \\ \end{align}$$

因此有 $\sum\limits_{x\in V(D)}d_{D}^{+}(x) = \epsilon(D) = \sum\limits_{x\in V(D)}d_{D}^{-}(x)$。$\Box$

---

推论1：对于任意无向图 $G$ 有 $\sum\limits_{x\in V(G)}d_{G}(x) = 2\epsilon(G)$

---

证明：

设 $D$ 是 $G$ 的对称有向图，则 $\epsilon(D) = 2\epsilon(G)$，对于 $\forall x\in V$ 均有 $d_{G}(x) = d_{D}^{+}(x) = d_{D}^{-}(x)$，由图论第一定理，有：

$$\sum\limits_{x\in V(G)}d_{G}(x) = \sum\limits_{x\in V(D)}d_{D}^{+}(x) = \epsilon(D) = 2\epsilon(G)$$

$\Box$

---

推论2：任意无向图 $G$ 的奇度点为偶数个。

---

证明：

记 $V_{o}, V_{e}$ 为 $G$ 中奇度点集与偶度点集。由前面的推论1，有：

$$\sum\limits_{x\in V_{o}}d_{G}(x) + \sum\limits_{x\in V_{e}}d_{G}(x) = 2\epsilon(G)$$

$\Box$

---