第三十三章：图的基本概念与性质

 前置知识：树的基本概念及性质

为了保证学习效果，请保证已经掌握前置知识之后，再来学习本章节！如果在阅读中遇到困难，也可以回到前面章节查阅。

学习目标

• 掌握图的基本概念
• 掌握图的一些性质

图的概念

基本概念

图 (Graph) 是一个二元组 G=(V(G), E(G))G=(V(G),E(G)) 。其中 V(G)V(G) 是非空集，称为 点集 (Vertex set) ，对于 VV 中的每个元素，我们称其为 顶点 (Vertex) 或 节点 (Node) ，简称 点 ； E(G)E(G) 为 V(G)V(G) 各结点之间边的集合，称为 边集 (Edge set) 。

常用 G=(V,E)G=(V,E) 表示图。

当 V,EV,E 都是有限集合时，称 GG 为 有限图 。

当 VV 或 EE 是无限集合时，称 GG 为 无限图 。

图有多种，包括 无向图 (Undirected graph) ， 有向图 (Directed graph) ， 混合图 (Mixed graph) 等

若 GG 为无向图，则 EE 中的每个元素为一个无序二元组 (u, v)(u,v) ，称作 无向边 (Undirected edge) ，简称 边 (Edge) ，其中 u, v \in Vu,v∈V 。设 e = (u, v)e=(u,v) ，则 uu 和 vv 称为 ee 的 端点 (Endpoint) 。

若 GG 为有向图，则 EE 中的每一个元素为一个有序二元组 (u, v)(u,v) ，有时也写作 u \to vu→v ，称作 有向边 (Directed edge) 或 弧 (Arc) ，在不引起混淆的情况下也可以称作 边 (Edge) 。设 e = u \to ve=u→v ，则此时 uu 称为 ee 的 起点 (Tail) ， vv 称为 ee 的 终点 (Head) ，起点和终点也称为 ee 的 端点 (Endpoint) 。并称 uu 是 vv 的直接前驱， vv 是 uu 的直接后继。

若 GG 为混合图，则 EE 中既有向边，又有无向边。

若 GG 的每条边 e_k=(u_k,v_k)ek​=(uk​,vk​) 都被赋予一个数作为该边的 权 ，则称 GG 为 赋权图 。如果这些权都是正实数，就称 GG 为 正权图 。

图 GG 的点数 \left| V(G) \right|∣V(G)∣ 也被称作图 GG 的 阶 (Order) 。

形象地说，图是由若干点以及连接点与点的边构成的。

图上的关系

点与点——邻接

在无向图 G = (V, E)G=(V,E) 中，对于两顶点 uu 和 vv ，若存在边 (u, v)(u,v) ，则称 uu 和 vv 是 相邻（邻接）的 。

一个顶点 v \in Vv∈V 的 邻域 (Neighborhood) 是所有与之相邻的顶点所构成的集合，记作 N(v)N(v) 。

PS：邻接表存储的就是邻域，并且由此得名。

点与边——关联

在无向图 G = (V, E)G=(V,E) 中，若点 vv 是边 ee 的一个端点，则称 vv 和 ee 是 **关联的 **。

度数

与一个顶点 vv 关联的边的条数称作该顶点的 度 (Degree) ，记作 d(v)d(v) 。特别地，对于边 (v, v)(v,v) ，则每条这样的边要对 d(v)d(v) 产生 22 的贡献。

对于无向简单图，有 d(v) = \left| N(v) \right|d(v)=∣N(v)∣ 。

在有向图 G = (V, E)G=(V,E) 中，以一个顶点 vv 为起点的边的条数称为该顶点的 出度 (Out-degree) ，记作 d^+(v)d+(v) 。以一个顶点 vv 为终点的边的条数称为该节点的 入度 (In-degree) ，记作 d^-(v)d−(v) 。显然 d^+(v)+d^-(v)=d(v)d+(v)+d−(v)=d(v) 。

握手定理（又称图论基本定理）：对于任何无向图 G = (V, E)G=(V,E) ，有 \sum_{v \in V} d(v) = 2 \left| E \right|∑v∈V​d(v)=2∣E∣ ，即无向图中结点度数的总和等于边数的两倍。有向图中结点的入度之和等于出度之和等于边数。

推论： 在任意图中，度数为奇数的点必然有偶数个。

若 d(v) = 0d(v)=0 ，则称 vv 为 孤立点 。

若 d(v) = 1d(v)=1 ，则称 vv 为 **叶节点 / 悬挂点 ** 。

若 2 \mid d(v)2∣d(v) ，则称 vv 为 偶点 。

若 2 \nmid d(v)2∤d(v) ，则称 vv 为 奇点 。图中奇点的个数是偶数。

若 d(v) = \left| V \right| - 1d(v)=∣V∣−1 ，则称 vv 为 支配点 。

对一张图，所有节点的度数的最小值称为 GG 的 最小度 ，记作 \delta (G)δ(G) ；最大值称为 最大度 ，记作 \Delta (G)Δ(G) 。即： \delta (G) = \min_{v \in G} d(v)δ(G)=minv∈G​d(v) , \Delta (G) = \max_{v \in G} d(v)Δ(G)=maxv∈G​d(v) 。

对于任何有向图 G = (V, E)G=(V,E) ，有：

\sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v) = \left| E \right|∑v∈V​d+(v)=∑v∈V​d−(v)=∣E∣

若对一张无向图 G = (V, E)G=(V,E) ，每个顶点的度数都是一个固定的常数 kk ，则称 GG 为 kk - 正则图 ( kk -Regular Graph) 。

如果给定一个序列 a，可以找到一个图 G，以其为度数列，则称 a 是 可图化 的。

如果给定一个序列 a，可以找到一个简单图 G，以其为度数列，则称 a 是 可简单图化 的。

简单图

自环 (Loop) ：对 EE 中的边 e = (u, v)e=(u,v) ，若 u = vu=v ，则 ee 被称作一个自环。

重边/平行边 (Multiple edge) ：若 EE 中存在两个完全相同的元素（边） e_1, e_2e1​,e2​ ，则它们被称作（一组）重边。

简单图 (Simple graph) ：若一个图中 没有自环和重边，它被称为简单图。非空简单无向图中一定存在度相同的结点。

如果一张图中有自环或重边，则称它为 多重图 (Multigraph) 。

​ 在无向图中 (u, v)(u,v) 和 (v, u)(v,u) 算一组重边，而在有向图中， u \to vu→v 和 v \to uv→u 不为重边。

​ 在题目中，如果没有特殊说明，是可以存在自环和重边的，在做题时需特殊考虑。

路径

途径 (Walk) / 链 (Chain) ：一个点和边的交错序列，其中首尾是点—— v_0, e_1, v_1, e_2, v_2, \ldots, e_k, v_kv0​,e1​,v1​,e2​,v2​,…,ek​,vk​ ，有时简写为 v_0 \to v_1 \to v_2 \to \cdots \to v_kv0​→v1​→v2​→⋯→vk​ 。其中 e_iei​ 的两个端点分别为 v_{i-1}vi−1​ 和 v_ivi​ 。通常来说，边的数量 kk 被称作这条途径的 长度 （如果边是带权的，长度通常指路径上的边权之和，题目中也可能另有定义）。（以下设 w = \left[ v_0, e_1, v_1, e_2, v_2, \cdots, e_k, v_k \right]w=[v0​,e1​,v1​,e2​,v2​,⋯,ek​,vk​] 。)

迹 (Trail) ：对于一条途径 ww ，若 e_1, e_2, \cdots, e_ke1​,e2​,⋯,ek​ 两两互不相同，则称 ww 是一条迹。

路径 (Path) （又称 简单路径 (Simple path) )：对于一条迹 ww ，除了 v_0v0​ 和 v_kvk​ 允许相同外，其余点两两互不相同，则称 ww 是一条路径。

回路 (Circuit) ：对于一个迹 ww ，若 v_0 = v_kv0​=vk​ ，则称 ww 是一个回路。

环/圈 (Cycle) （又称 简单回路/简单环 (Simple circuit) )：对于一条简单路径 ww ，若 v_0 = v_kv0​=vk​ ，则称 ww 是一个环。

连通

无向图

对于一张无向图 G = (V, E)G=(V,E) ，对于 u, v \in Vu,v∈V ，若存在一条途径使得 v_0 = u, v_k = vv0​=u,vk​=v ，则称 uu 和 vv 是 连通的 (Connected) 。由定义，任意一个顶点和自身连通，任意一条边的两个端点连通。

若无向图 G = (V, E)G=(V,E) ，满足其中任意两个顶点均连通，则称 GG 是 连通图 (Connected graph) ， GG 的这一性质称作 连通性 (Connectivity) 。

若 HH 是 GG 的一个连通子图，且不存在 FF 满足 H\subsetneq F \subseteq GH⊊F⊆G 且 FF 为连通图，则 HH 是 GG 的一个 连通块/连通分量 (Connected component) （极大连通子图）。

有向图

对于一张有向图 G = (V, E)G=(V,E) ，对于 u, v \in Vu,v∈V ，若存在一条途径使得 v_0 = u, v_k = vv0​=u,vk​=v ，则称 uu 可达 vv 。由定义，任意一个顶点可达自身，任意一条边的起点可达终点。（无向图中的连通也可以视作双向可达。）

若一张有向图的节点两两互相可达，则称这张图是 强连通的 (Strongly connected) 。

若一张有向图的边替换为无向边后可以得到一张连通图，则称原来这张有向图是 弱连通的 (Weakly connected) 。

与连通分量类似，也有 弱连通分量 (Weakly connected component) （极大弱连通子图）和 强连通分量 (Strongly Connected component) （极大强连通子图）。

nn 个顶点的强连通图最多 n(n-1)n(n−1) 条边，最少 nn 条边。

图的连通性也是竞赛的一个常见考点，相关算法请后面将学习，现在先理解其概念即可。

稀疏图/稠密图

若一张图的边数远小于其点数的平方，那么它是一张 稀疏图 (Sparse graph) 。

若一张图的边数接近其点数的平方，那么它是一张 稠密图 (Dense graph) 。

这两个概念并没有严格的定义，一般用于讨论 时间复杂度 为 O(|V|^2)O(∣V∣2) 的算法与 O(|E|)O(∣E∣) 的算法的效率差异（在稠密图上这两种算法效率相当，而在稀疏图上 O(|E|)O(∣E∣) 的算法效率明显更高）。

补图

对于无向简单图 G = (V, E)G=(V,E) ，它的 补图 (Complement graph) 指的是这样的一张图：记作 \bar GGˉ ，满足 V \left( \bar G \right) = V \left( G \right)V(Gˉ)=V(G) ，且对任意节点对 (u, v)(u,v) ， (u, v) \in E \left( \bar G \right)(u,v)∈E(Gˉ) 当且仅当 (u, v) \notin E \left( G \right)(u,v)∈/E(G) 。

反图

对于有向图 G = (V, E)G=(V,E) ，它的 反图 (Transpose Graph) 指的是点集不变，每条边反向得到的图，即：若 GG 的反图为 G'=(V, E')G′=(V,E′) ，则 E'=\{(v, u)|(u, v)\in E\}E′={(v,u)∣(u,v)∈E} 。

特殊的图

完全图

若无向简单图 GG 满足任意不同两点间均有边，则称 GG 为 完全图 (Complete graph) ， nn 阶完全图记作 K_nKn​ 。若有向图 GG 满足任意不同两点间都有两条方向不同的边，则称 GG 为 有向完全图 (Complete digraph) 。

零图

边集为空的图称为 零图 (Null graph) ， nn 阶零图记作 N_nNn​ 。易知， N_nNn​ 为 K_nKn​ 互为补图。

竞赛图

若有向简单图 GG 满足任意不同两点间都有恰好一条边（单向），则称 GG 为 竞赛图 (Tournament graph) 。

环图/圈图

若无向简单图 G = \left( V, E \right)G=(V,E) 的所有边恰好构成一个圈，则称 GG 为 环图/圈图 (Cycle graph) ， nn ( n \geq 3n≥3 ) 阶圈图记作 C_nCn​ 。易知，一张图为圈图的充分必要条件是，它是 22 - 正则连通图。

星图/菊花图

若无向简单图 G = \left( V, E \right)G=(V,E) 满足，存在一个点 vv 为支配点，其余点之间没有边相连，则称 GG 为 星图/菊花图 (Star graph) ， n + 1n+1 ( n \geq 1n≥1 ) 阶星图记作 S_nSn​ 。

轮图

若无向简单图 G = \left( V, E \right)G=(V,E) 满足，存在一个点 vv 为支配点，其它点之间构成一个圈，则称 GG 为 轮图 (Wheel Graph) ， n + 1n+1 ( n \geq 3n≥3 ) 阶轮图记作 W_nWn​ 。

链

若无向简单图 G = \left( V, E \right)G=(V,E) 的所有边恰好构成一条简单路径，则称 GG 为 链 (Chain/Path Graph) ， nn 阶的链记作 P_nPn​ 。易知，一条链由一个圈图删去一条边而得。

树

如果一张无向连通图不含环，则称它是一棵 树 (Tree) 。相关内容详见 树基础 。

平面图

如果一张图可以画在一个平面上，且没有两条边在非端点处相交，那么这张图是一张 平面图 (Planar graph) 。一张图的任何子图都不是 K_5K5​ 或 K_{3, 3}K3,3​ 是其为一张平面图的充要条件。对于简单连通平面图 G=(V, E)G=(V,E) 且 V\ge 3V≥3 ， |E|\le 3|V|-6∣E∣≤3∣V∣−6 。