图论1-基本概念

  |  

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

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:潮汐朝夕
我的知乎:潮汐朝夕
我的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