数图论

图论1：基本概念

字数统计: 4.5k字   |   阅读时长: 18分

摘要: 图论的基本概念，参考徐俊明《图论及其应用》

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

本文记录图论中的基本概念和定理，证明省略，本文是个备忘录，需要细节的时候再查相应的资料即可。

总览参考文章 图论导引，本文是基本概念的内容。

符号总览

  • 图 $G = (V, E)$
  • 反图：$\overleftarrow{D}$
  • 补图：$G^{c} = (V, E^{c})$
  • 关联函数：$\psi: E \rightarrow V\times V$
  • n 阶竞赛图：$T_{n}$
  • 图的点数：$v(G) = |V|$
  • 图的边数：$\epsilon(G) = |E|$
  • 顶点：$v$ 的邻集：$N(v)$
  • 同构：$G \cong H$
  • 全自同构群：$Aut(G)$
  • 完全图：$K_{n}$
  • 完全有向图：$K_{n}^{* }$
  • 二部图：$G = X \bigtriangleup Y$
  • 完全二部图：$K_{m,n}$
  • 星图：$K_{1,n}$
  • 最大顶点度：$\Delta(G)$
  • 最小顶点度：$\delta(G)$
  • 顶点度：$d_{G}(v)$
  • 边度：$\xi_{G}(e)$
  • 最小边度：$\xi(G)$
  • 出度：$d_{D}^{+}(v)$
  • 入度：$d_{D}^{-}(v)$
  • 最大出度，最小出度，最大入度，最小入度：$\Delta^{+}(D)$, $\delta^{+}(D)$, $\Delta^{-}(D)$, $\delta^{-}(D)$
  • 距离：$d_{G}(u,v)$
  • 直径：$D(G)$
  • 子图：$G’ \subseteq G$
  • 导出子图：$G’ \lhd G$，$D[V’]$，$G[V’]$
  • 长为 $i$ 的圈：$C_{i}$
  • 连通分量个数：$\omega(D)$
  • 强连通分量个数：$\vec{\omega}(D)$
  • 围长（最短圈的长度）：$g(D)$
  • 长度为 $n-1$ 的路径：$P_{n}$
  • 平均距离：$m(G)$
  • 不同点对的距离和：$\sigma(G)$
  • 邻接矩阵：$A(G)$
  • 关联矩阵：$M(G)$
  • 两个有向图的并：$D_{1} \cup D_{2}$
    • 点不交：$D_{1} + D_{2}$
    • 边不交：$D_{1}\oplus D_{2}$

图上的重要集合及其符号

一些重要的符号：$G = (V, E)$ 为简单图，$v \in V, e \in E$。

符号 含义
$G-v$ 或 $G \setminus v$ 从 $G$ 中去掉 $v$ 以及所有与 $v$ 关联的边后得到的图。
$G-e$ 从 $G$ 中去掉 $e$ 之后得到的图。
$G \setminus e$ 去掉 $e$，再把 $e$ 的两个端点 $v_{1}, v_{2}$ 合二为一(收缩边 $e$) 得到的简单图。
$G+e$ 或 $G+(u,v)$ $e \notin E$ 但 $e$ 的两条边 $u,v \in V$，表示 $G$ 中加入边 $e$ 后得到的图。

对于有向图 $D = (V, E)$，$S$ 和 $T$ 是 $V$ 中的两个不相交的非空真子集。

  • $E_{D}(S, T)$ : $D$ 中起点在 $S$ 而终点在 $T$ 的边集。可以简写为 $(S, T)$。
  • $E_{D}[S, T] = E_{D}(S, T) \cup E_{D}(T, S)$。可以简写为 $[S, T]$。
  • 若 $T = \overline{S} = V \setminus S$，可以将 $E_{D}(S, \overline{S})$ 简记为 $E_{D}^{+}(S)$，$E_{D}(\overline{S}, S)$ 为 $E_{D}^{-}(S)$，$E_{D}[S, \overline{S}]$ 为 $E_{D}[E]$。记$d_{D}^{+}(S) = |E_{D}^{+}(S)|$, $d_{D}^{-}(S) = |E_{D}^{-}(S)|$。
  • $N_{D}^{+}(S)$ 为 $E_{D}^{+}(S)$ 中边的终点集($S$ 的外邻集)；$N_{D}^{+}(S)$ 为起点集($S$ 的内邻集)。
  • 若 $D$ 为简单图，则有 $d_{D}^{+}(v) = |N_{D}^{+}(v)|$，$d_{D}^{-}(v) = |N_{D}^{-}(v)|$。

无向图也有类似记号：$E_{G}[S]$, $[S,T]$, $N_{G}(S)$(之前定义过点的邻集，这里是点集的邻集)。

$1 图

$V$ 是非空集，$V$ 上的一个二元关系 $e$ 是 $V$ 上的元素对，即 $e \in V \times V$。

集合 $V$ 和定义在 $V$ 上的二元关系的集合 $R$ 构成一个有序二元组 $(V, R)$，此二元组称为数学结构。

定义：图是一个二元组，记为 $G = (V, E)$，其中 $V$ 是顶点集，$E$ 是 $V$ 的所有 2-子集(即二元关系集)所组成的集合的一个子集，称为边集。当表示二元关系的数对是无序数对时，$G$ 为无向图，当表示二元关系的数对是有序数对时，$G$ 为有向图。

记点数为 $v(G) = |V|$，记边数为 $\epsilon(G) = |E|$。

有时也把图定义为 $G = (V, E, \psi)$，其中 $\psi$ 为 $E$ 到 $V \times V$ 的函数，称为关联函数。

有向图和无向图的差别仅在于 $\psi(E)$ 中的元素是 $V$ 中的元素的有序对还是无序对。

无向图是特殊的有向图：将无向图 $G$ 的每条边用两条有向边代替(无序对改为两个有序对)，得到有向图 $D$，称为 $G$ 的对称有向图。

图论的研究内容常常与边的方向没有关系，因此讨论与边的方向无关的有向图 $D$ 时，去掉边的方向(有序对视为无序对并去重)得到无向图 $G$，称为 $D$的基础图。

将 $G$ 的每条边都指定一个方向，得到有向图，称为 $G$ 的定向图。

如果一个图 $G$ 的顶点集和边集都是有穷的，称 $G$ 是有穷图。

$2 自环，重边，简单图

定义：图 $G$ 中，组成边 $e$ 这个 2-子集中的顶点称为 $e$ 的端点，若边 $e$ 的两个端点相同，则 $e$ 为自环。若边 $e_{1}, e_{2}$ 具有完全相同的端点，称其为重边。若 $G$ 既无自环，又无重边，则 $G$ 为简单图。

定义：有向图中两个端点相同但方向互为相反的两条边称为对称边。

计算机中讨论的图论算法一般针对的都是简单图。

结论：以 $[n]$ 为点集的简单图共有 $2^{\dbinom{n}{2}}$ 个。

$3 关联，点相邻，边相邻

定义：图 $G = (V, E)$ 中，边集确定了点集的一个二元关系，点 $u$, $v$ 之间有一条边，记为 $uv \in E$，$u$, $v$ 是这条边的端点，称它们相邻。$u$, $v$ 与这条边关联。若边 $e$, $f$ 有一个端点相同，称 $e$, $f$ 相邻。

定义：图 $G = (V, E)$ 中，点 $v$ 的邻集 $N(v)$ 定义为 $N(v) = \{u \in V | uv \in E\}$，与 $v$ 相邻的顶点称为 $v$ 的邻居。

对 $V’ \subseteq V$，$V’$ 的邻集为：

$4 度，正则图

定义：图 $G = (V, E)$ 中，点 $v$ 的度$d_{G}(v)$ 为与 $v$ 关联的边数(自环计两次)。$G$ 中顶点的最大度记为 $\Delta(G)$, 最小度记为 $\delta(G)$，如果 $\Delta(G) = \delta(G)$，则 $G$ 为正则图，具体地，$\Delta(G) = \delta(G) = k$，称为 k-正则图。

定义：$e=uv$ 的边度为 $\xi_{G}(e) = d_{G}(u) + d_{G}(v) - 2$，图的最小边度：$\xi(G) = \min\{\xi_{G}(e); e \in E(G)\}$，显然 $\xi(G) \leq \Delta(G) + \delta(G) - 2$，若 $G$ 的每条边 $e$ 都有 $\xi_{G}(e) = \xi(G)$, 则 $G$ 是边正则图。

定义：度为 0 的点称为孤立点。

对于有向图 $D$，有以下概念：

定义：点 $v$ 的出度为 $D$ 中以 $v$ 为起点的有向边数目，记为 $d_{D}^{+}(v)$；点 $v$ 的入度为 $D$ 中以 $v$ 为终点点的有向边数目，记为 $d_{D}^{-}(v)$，顶点度 $d_{D}(v) = d_{D}^{+}(v) + d_{D}^{-}(v)$。

定义：若 $d_{D}^{+}(v) = d_{D}^{-}(v)$ ，称 $v$ 为平衡点。每个顶点都为平衡点的有向图称为平衡有向图，完全有向图 $K_{n}^{*}$ 是平衡图。

定义：$\Delta^{+}(D)$, $\delta^{+}(D)$, $\Delta^{-}(D)$, $\delta^{-}(D)$，分别为有向图 D 的最大出度，最小出度，最大入度，最小入度。这四个参数均为 k 的有向图称为 k正则有向图。

  • 定理(图论第一定理)：对于有向图 $\forall D=(V, E)$, 均有 $\sum\limits_{v \in V}d_{D}^{+}(v) = \sum\limits_{v \in V}d_{D}^{-}(v) = \epsilon(D)$。
  • 推论：$\forall G=(V, E)$, 均有 $\sum\limits_{v \in V}d_{G}(v) = 2\epsilon(G)$。
  • 推论：$\forall G=(V, E)$, 奇度顶点的个数必为偶数。
  • 结论：$\forall G=(V, E), \sum\limits_{v\in V}d(v)$必为偶数。

$5 n阶图，完全图，补图

定义：图 $G = (V, E)$ 有 n 个顶点，G 为 n 阶图，任意两顶点均相邻的简单图为完全图，n阶完全图记为 $K_{n}$，n阶完全有向图记为 $K_{n}^{* }$。

由定义，$\epsilon(K_{v}) = \binom{v}{2}$、$\epsilon(K_{v}^{* }) = 2\binom{v}{2}$。

定义：边数为零的图称为零图。阶为 1 的图称为平凡图，边数点数均为零的图称为空图。

定义：完全图的定向图称为竞赛图，这种图描述了 $|V|$ 个选手参加的某项循环比赛的结果，n 阶竞赛图记为 $T_{n}$。

Petersen 图：常作为反例出现。

定义：对于简单图 $D$，补图 $D^{c}$ 是指与 $D$ 有相同顶点集的简单图，并且：

无向图的补图的一些性质：

  • $G$ 中的独立集在在 $G^{c}$ 中为团；$G$ 中的团在在 $G^{c}$ 中为独立集。
  • 若 $G$ 不连通，则 $G^{c}$ 一定连通。

定义：对于简单图 $D$（或简单无向图 $G$），如果 $D \cong D^{c}$（或 $G \cong G^{c}$），则称其为自补图，

  • 若有向图 $D$ 是自补图，则 $\epsilon = \frac{1}{4}v(v-1)$
  • 若无向图 $G$ 是自补图，则 $\epsilon = \frac{1}{4}v(v-1)$ 且 $v \equiv 0,1 \mod 4$

$6 子图，生成子图，导出子图

定义：对于图 $G’ = (V’, E’)$ 和图 $G = (V, E)$，若 $V’ \subseteq V$ 且 $E’ \subseteq E$，称 $G’$ 为 $G$ 的子图。记为 $G’ \subseteq G$。

对于子图 $G’ \subseteq G$，若 $\forall u, v\in V(G’)$ 有 $(u, v) \in E(G)$，则称 $G’$ 为 $G$ 的完全子图，也称为团(clique)。

对于子图 $G’ \subseteq G$，若 $\forall u, v\in V(G’)$ 有 $(u, v) \notin E(G), (v, u)\notin E(G)$，则称 $V(G’)$ 为 $G$ 的独立集。

$G’ \subseteq G$，若 $V’ = V$，则 $G’$ 是 $G$ 的生成子图(支撑子图)。

$G’ \subseteq G$，若对任意 $u,v \in V’$，只要 $uv \in E$，就有 $uv \in E’$，则 $G’$ 为 G 的导出子图，记为$G’ \lhd G$, 此时 $G’$ 也记为 $G[V’]$。导出子图 $G[V \setminus V’]$ 记为 $G - V’$，若 $V’$ 仅含一个点 $v$，也可以记为 $G - v$。

$D_{1} \subseteq D$, $D_{2} \subseteq D$，若 $V(D_{1}) \cap V(D_2) = \varnothing$，称 $D_{1}$ 和 $D_{2}$ 是点不交的。若 $E(D_{1}) \cap E(D_2) = \varnothing$，称 $D_{1}$ 和 $D_{2}$ 是边不交的。

$H = D_{1} \cup D_{2}$ 是 $D_{1}$ 和 $D_{2}$ 的并。其中 $V(H) = V(D_{1}) \cup V(D_{2})$、$E(H) = E(D_{1}) \cup E(D_{2})$。若 $D_{1}$ 和 $D_{2}$ 点不交，记为 $D_{1} \cup D_{2} = D_{1} + D_{2}$。若 $D_{1}$ 和 $D_{2}$ 边不交，记为 $D_{1} \cup D_{2} = D_{1} \oplus D_{2}$。

$7 途径，迹，路径，圈

定义：$G$ 中，一个从顶点到顶点，点边交替出现且相邻的点和边关联的序列称为途径(chain/walk)，途径中所含的边数称其为长度。例如下面是一个起点为 $v_{i_{0}}$ 终点为 $v_{i_{k}}$ 的途径 $W$，长度为 $k$：

起点和终点相同的途径为闭途径(closed chain)。边不重的途径称为迹(trail)，起点和终点相同的迹称为闭迹(circuit)。顶点不重复的途径称为路(path)，起点和终点相同的路称为圈(cycle)。长度为 $i$ 的圈记为 $C_{i}$。

1
2
3
途径 Chain/Walk  -> 闭途径      点、边均可能重复
迹 Trail         -> 闭迹 (回)   边互不相同
路 Path          -> 闭路 (圈)   点互不相同

长度为 $n-1$ 的路径记为 $P_{n}$。

对于有向图 $D$，从 $u$ 到 $v$ 的有向途径(迹、路)，记为 $(u, v)$ 途径(迹、路)。

在简单图中，两个顶点之间最多一条边，因此在讨论(闭)途径，(闭)迹，路，圈时，所用的记号可将边省略。

$8 奇圈，偶圈，距离(最短路)，围长，直径

定义：简单图 $G$ 中，长度为奇数和偶数的圈(回)分别称为奇圈(回)，偶圈(回)。对于$u,v \in V$，从 $u$ 到 $v$ 的具有最小长度的路称为 $u$ 到 $v$ 的最短路，其长度称为 $u$ 到 $v$ 的距离。记为 $d_{G}(u,v)$ 或 $d(u,v)$，图 $G$ 的围长是 $G$ 中最短圈的长度，记为 $g(G)$。

有向图 $D$ 上，距离的定义类似，约定若 $D$ 中不存在 $(u,v)$ 路，则 $d_{D}(u,v) = \infty$。

定义：简单图 $G$(或$D$)，若 $\forall 3 \leq n \leq |V|$，$G$(或$D$) 中存在长为 $n$ 的圈(或有向圈)，则 $G$(或$D$)为泛圈的。如果对任意点 $\forall v \in V$ 且 $\forall 3 \leq n \leq |V|$，$G$(或$D$) 中存在长为 $n$ 且包含 $v$ 的圈(或有向圈)，则 G(或D)为点泛圈的。

定义：图 G 的直径为 $D(G) := \max\{d(u,v)|u,v\in G\}$。

定理：G 为简单图，若 $\delta(G) \ge 2$ 则 G 中必含有圈。

若 $G$ 是非平凡连通无向图，或者强连通有向图，则定义平均距离如下：

其中不同点对的距离和记为 $\sigma(G) = \sum\limits_{x,y\in V}d_{G}(x,y)$。

$9 连通图，连通分量，割点，桥

定义：图 $G$ 中任意两点 $u, v$ 之间都有路，则 $G$ 为连通图。

定义：若图 $G$ 的顶点集 $V$ 可划分为若干非空子集 $V_{i}$，使得：两点属于同一子集 $\Leftrightarrow G$ 中有路连接它们。则每个子顶点集 $V_{i}$ 的导出子图 $D[V_{i}]$ 为 $G$ 的一个连通分量，连通分量个数记为 $\omega(D)$。

定理：若图 $G = (V, E)$ 连通，则 $|E| \ge |V| - 1$。

对于有向图 $D$，分为强连通和单向连通。

定义：$u, v \in V$，D 中既存在 $(u,v)$ 路又存在 $(v,u)$ 路，则成 $u$ 和 $v$ 是强连通的。

定义：$u, v \in V$，D 中存在 $(u,v)$ 路或存在 $(v,u)$ 路，则成 $u$ 和 $v$ 是单向连通的。

定义：若图 $D$ 的顶点集 $V$ 可划分为若干非空子集 $V_{i}$，使得：两点 $u, v$ 属于同一子集 $\Leftrightarrow D$ 中既有 $(u, v)$ 路又有 $(v, u)$ 路连接它们。则每个子顶点集 $V_{i}$ 的导出子图 $D[V_{i}]$ 为 $D$ 的一个强连通分量，强连通分量个数记为 $\vec{\omega}(D)$。

$D 强连通 \Rightarrow D 连通$

定理：
  • 图 D 或 G 连通 $\Leftrightarrow$ 对 V 的任意非空真子集 S 均有 $[S, \overline{S}] \neq \varnothing$
  • 图 D 强连通 $\Leftrightarrow$ 对 V 的任意非空真子集 S 均有 $(S, \overline{S}) \neq \varnothing$ 且 $(\overline{S}, S) \neq \varnothing$

定义：$v \in V(G), e \in E(G)$，若 $\omega(G-v) > \omega(G)$，则 $v$ 为割点，否则 $v$ 为连通点。

若 $\omega(G-e) > \omega(G)$，则 $e$ 为割边，也称为桥，否则称为连通边。不含割点的连通图称为块(block)。$D$ 中不含割点的极大连通子图称为图 $D$ 的块。

$10 二部图

定义：若图 $G$ 的顶点集可以划分为两个非空子集 $X$ 和 $Y$，使得任意一条边都有一个端点在 $X$，另一个端点在 $Y$，则 $G$ 为二部图，记为 $G = X \bigtriangleup Y$，$X$ , $Y$ 为 $G$ 的一个二部划分。

若 $X$ 的每个顶点与 $Y$ 中每个顶点都相邻，则$G$为完全二部图，若 $|X| = m, |Y| = n$，则记此完全二部图为 $K_{m,n}$，$K_{1,n}$ 称为星图。

若 $|X| = |Y| = n$，则完全二部图 $K_{n,n}$ 也记为 $K_{n}(2)$，类似地可以定义完全 k 部图 $K_{n}(k)$。

由定义，$\epsilon(K_{m,n}) = mn$、$\epsilon(K_{n}(k)) = \frac{1}{2}k(k-1)n^{2}$。

每个有向图 $D$ 都对应一个无向二部图 $G$，$G$ 的构造方式：将每个点 $v$ 都对应到无向图的 $v’$ 和 $v’’$，对于每条有向边 $e = uv$ ，对应无向图中的边 $u’v’’$。称其为有向图 D 的伴随二部图。$v(G) = 2v(D)$, $\epsilon(G) = \epsilon(D)$。

定理：图 $G = (V, E)$ 是二部图 $\Leftrightarrow G$ 不含奇圈

有向图的情况：

定理(二部图判定定理)：强连通图 $D = (V, E)$ 是二部图 $\Leftrightarrow G$ 不含奇圈

$11 同构，自同构

定义：$G$ 和 $H$ 为简单图，如果存在一个双射 $f : V(G) \to V(H)$，使得：

称 $G$ 与 $H$ 同构。记为 $G \cong H$。

同构的图有相同的结构，不同的仅在于顶点和边的名称。用顶点和边都没有名称的图形表示作为同构图等价类中的代表元素。图形表示如果顶点确定了标号，称为标号图。

定义：图 $G$ 的自同构是一个从 $G$ 到 $G$ 的同构。$G$ 的所有自同构在映射乘法下构成一个群，称为 $G$ 的全自同构群，记为 $Aut(G)$。若 $\forall u,v \in V(G)$, 存在 $G$ 的一个自同构把 $u$ 映射到 $v$，$G$ 称为顶点传递的。

同构关系是一种等价关系。这种等价关系将同阶图分成若干等价类，同构的图属于一类。

通常情况下，对同构的图不加以区分。

$12 关联矩阵，邻接矩阵

定义：对图 $G = (V, E)$ 的顶点与边编号：$V = \{v_{1}, v_{2}, …, v_{n}\}$, $E = \{e_{1}, e_{2}, …, e_{m}\}$。G 的关联矩阵为 $M(G) = (M_{ij})_{m \times n}$, 其中 $m_{ij} = 1$ 当且仅当 $v_{i}$ 与 $e_{j}$ 关联，否则 $m_{ij} = 0$。G 的邻接矩阵为 $A(G) = (a_{ij})_{m \times n}$, 其中 $a_{ij} = 1$ 当且仅当 $v_{i}$ 与 $v_{j}$ 相邻，否则 $a_{ij} = 0$。

有了邻接矩阵和关联矩阵，图论和矩阵论和群论可以互相研究。

例如：考虑置换

则由

定义的 n 阶方阵 $P = (p_{ij})$ 为置换方阵。同构的两个图的邻接矩阵是置换相似的，而关联矩阵是置换相抵的。

以上例子中，图的同构是图论的概念，置换是群论的概念，矩阵的相似和相抵是矩阵论的概念。

定理(邻接矩阵定理)： A 是有向图 $D = (V, E)$ 的邻接矩阵，则 $A^{k}$ 中的 (i,j) 元素是 D 中长为 k 的$(v_{i}, v_{j})$链的数目。
Share