数图论

图论1-基本概念

字数统计: 3.3k字   |   阅读时长: 13分

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

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

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

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

$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 的定向图。

$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’$ 的邻集为 $N(V’) = \{u \in V | \exists v \in V’, uv \in E \} = \bigcup\limits_{v \in V’}N(v)$

$4 度，正则图

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

定义：$e=uv$ 的边度为 $\xi(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(e) = \xi(G)$, 则 G 是边正则图。

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

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

定义：点 v 的出度为 D 中以 y 为起点的有向边数目，记为 $d_{D}^{+}(v)$；点 v 的入度为 D 中以 y 为终点点的有向边数目，记为 $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)$ 的补图为 $\overline{G} = (V, \overline{E})$。 其中 $\overline{E} = \dbinom{V}{2} \setminus E$

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

定义：边数为零的图称为零图。阶为 1 的图称为平凡图。

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

Petersen 图：常作为反例出现

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

定义：对于图 $G’ = (V’, E’)$ 和图 $G = (V, E)$，若 $V’ \subseteq V$ 且 $E’ \subseteq E$，称 $G’$ 为 $G$ 的子图。记为 $G’ \subseteq G$。 若 $V’ = V$，则 $G’$ 是 G 的生成子图(支撑子图)。若对任意 $u,v \in V’$，只要 $uv \in E$，就有 $uv \in E’$，则 $G’$ 为 G 的导出子图，记为$G’ \lhd G$, 此时 $G’$ 也记为 $G[V’]$

$7 途径，迹，路径，圈

定义：$G$ 中，一个从顶点到顶点，点边交替出现且相邻的点和边关联的序列称为途径(chain/walk)，起点和终点相同的途径为闭途径(closed chain)。边不重的途径称为迹(trail)，起点和终点相同的迹称为闭迹(circuit)。顶点不重复的途径称为路(path)，起点和终点相同的路称为圈(cycle)。

定义：G 中，(闭)途径，(闭)迹，路，圈所含的边数称其为长度。

长度为 i 的圈记为 $C_{i}$

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

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

定义：简单图 G 中，长度为奇数和偶数的圈分别称为寄圈，偶圈。对于$u,v \in V$，从 u 到 v 的具有最小长度的路称为 u 到 v 的最短路，其长度称为 u 到 v 的距离。记为 $d_{G}(u,v)$或$d(u,v)$，图 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 = (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)$(之前定义过点的邻集，这里是点集的邻集)。

$9 连通图，连通分量

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

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

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

有向图 D 的情况：

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

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

$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)$，若 $G-v$ 的连通分量个数 大于 G 的连通分量个数，则 v 为割点，否则 v 为连通点。若 $G-e$ 的连通分量数大于 G 的连通分量数，则 e 为割边，也成为桥，否则称为连通边。不含割点的连通图称为块(block)

$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}$ 称为星图。

每个有向图 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 为简单图，从 G 到 H 的同构是一个双射 $f : V(G) \to V(H)$，使得 $\forall u,v \in V(G), uv \in E(G) \Leftrightarrow f(u)f(v) \in E(H)$

定义：图 G 的自同构是一个从 G 到 G 的同构。G 的所有自同构在映射乘法下构成一个群，成为 G 的全自同构群，记为 $Aut(G)$。若 $\forall u,v \in V(G), \exists 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