本节对应原书 PDF 第 147–156 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。
6.1.1 无向图与有向图
为了给出无向图和有向图的严格定义，先给出无序积与多重集合的概念.
两个元素构成的集合 \{a,b\} 称为无序对. 设 A，B 为二集合，称
为 A 与 B 构成的无序积，记作 A\&B. 为方便起见，将无序积 A\&B 的元素无序对 \{a,b\} 记为 (a,b). 例如，取 A=\{a,b,c\}，B=\{1,2\}，则
需要注意，无序积中的无序对的两个元素不分次序，同时又可以是相同的，如上例中的 (a,a)，(b,b)，(c,c)，(1,1)，(2,2) 等.
元素可以重复出现的集合称为多重集合，简称多重集. 元素在多重集合中出现的次数称为该元素的重复度. 例如，在多重集 \{a,b,b,c,c,c,d,d,d,d\} 中，a,b,c,d 的重复度分别为 1,2,2,3. 在多重集 \{(a,a),(a,b),(a,b)\} 中，元素 (a,a)，(a,b) 的重复度分别为 1,2. 当将集合 \{1,2,3\} 看成多重集时，1,2,3 的重复度均为 1.
下面先给出无向图的定义.
定义 6.1 一个无向图 G 是一个二元组 \langle V,E\rangle，即 G=\langle V,E\rangle，其中 V 是一个非空的有穷集合，称为 G 的顶点集，V 中的元素称为顶点或结点；E 是无序积 V\&V 的一个有穷的多重子集，称 E 为 G 的边集，其元素称为无向边或简称为边.
在一个图 G=\langle V,E\rangle 中，为了表示 V，E 分别是 G 的顶点集和边集，常将 V 记成 V(G)，E 记成 E(G).
无向图的另一种更直观的表示方法是用图形表示，用小圆圈表示 V 中的顶点，用连接顶点 a,b 的线段 (a,b). 在画图过程中，顶点的位置和边的形状及边之间是否除顶点外还相交都是比较随意的. 反之给定一个图 G=\langle V,E\rangle 的图形表示，也很容易将该图的顶点集和边集写出来，不过一般情况下不需要这样做. 在有些图的图形中，顶点不标定名字，都只用小圆圈表示，称这样的图为非标定图. 自然地，称顶点标定名字的图为标定图. 给定图 G=\langle V,E\rangle，其中，V=\{v_1,v_2,v_3,v_4,v_5\}，E=\{(v_1,v_2),(v_1,v_2),(v_1,v_3),(v_3,v_2),(v_3,v_3),(v_3,v_4)\}，图 6.1(a)给出了 G 的图形表示. 在标定图中还可以给边另起名字. 如在图 6.1 中(a)中，e_1=(v_1,v_2)，e_2=(v_1,v_2)，e_3=(v_1,v_3) 等.
图 6.1
下面再给出有向图的定义.
定义 6.2 一个有向图 D 是一个二元组 \langle V,E\rangle，即 D=\langle V,E\rangle，其中顶点集 V 同无向图中的顶点集；边集 E 是卡氏积 V\times V 的有穷的多重子集，其中元素称为有向边或简称为边.
同无向图的情况类似，有时用 V(D)，E(D) 分别表示有向图 D 的顶点集和边集. 也可以用图形表示有向图，与无向图图形的区别是用带箭头的线段表示有向边，表示边 \langle a,b\rangle 的线段上的箭头从 a 指向 b. 给定有向图 D=\langle V,E\rangle，其中，V=\{v_1,v_2,v_3,v_4\}，E=\{\langle v_2,v_1\rangle,\langle v_2,v_1\rangle,\langle v_3,v_4\rangle,\langle v_4,v_3\rangle,\langle v_3,v_1\rangle,\langle v_2,v_4\rangle,\langle v_1,v_1\rangle\}，其图形为图 6.1(b)所示.
解读：无向边的「端点无序」和有向边的「端点有序」是同一条定义里最容易混淆的地方——(a,b) 与 (b,a) 是同一条无向边，而 \langle a,b\rangle 与 \langle b,a\rangle 是两条不同的有向边。
无向图和有向图通称为图. 习惯上用 G 表示无向图，D 表示有向图. 有时也用 G 泛指一个图(有向的或无向的)，而 D 只表示有向图.
关于图还有下述概念.
(1) 有 n 个顶点的图称作 n 阶图.
(2) 没有边(即边集 E=\varnothing)的图称作零图. 1 阶零图称作平凡图. 平凡图只有一个顶点，没有边.
(3) 在定义中规定顶点集非空，但在图的运算中可能产生顶点集为空集的结果. 为此规定顶点集为空集的图称作空图，记作 \varnothing.
(4) 在无向图 G=\langle V,E\rangle 中，设 e=(v_i,v_j)\in E，称 v_i,v_j 是 e 的端点，e 与 v_i(v_j) 关联. 若 v_i\neq v_j，则称 v_i(v_j) 与 e 的关联次数为 1；若 v_i=v_j，则称 v_i 与 e 的关联次数为 2；若 v_k 不是 e 的端点，则称 v_k 与 e 的关联次数为 0.
若两个顶点之间至少有一条边，则称这两个顶点相邻. 若两条边至少有一个共同的端点，则称这两条边相邻.
例如，在图 6.1(a)中，v_1 和 v_2 是 e_1 的端点，v_1 与 v_2,v_3 相邻，而与 v_4,v_5 不相邻. e_1 与 e_2,e_3,e_4 相邻，而与 e_5,e_6 不相邻.
(5) 在有向图 D=\langle V,E\rangle 中，设 e=\langle v_i,v_j\rangle\in E，称 v_i,v_j 是 e 的端点，v_i 是 e 的始点，v_j 是 e 的终点. e 与 v_i(v_j) 关联.
若从 v_i 到 v_j 有一条边，则称这两个顶点相邻，并称 v_i 邻接到 v_j，v_j 邻接于 v_i. 若一条边的终点是另一条边的始点，则称这两条边相邻.
例如，在图 6.1(b)中，e_2 的始点是 v_2，终点是 v_1，v_1 和 v_2 是 e_2 的端点. v_3 与 v_1,v_1 相邻，v_3 邻接到 v_1，v_4 邻接到 v_3. e_5 与 e_3,e_4,e_6 相邻，e_2 与 e_1 相邻，但与 e_3,e_4,e_7 不相邻，当然与 e_5,e_6 也不相邻.
(6) 在无向图和有向图中，没有边关联的顶点称作孤立点，两个端点重合的边称作环.
例如，图 6.1(a)中 v_5 是孤立点，e_6 是环. (b)中没有孤立点，e_1 是环.
6.1.2 顶点的度数与握手定理
定义 6.3 设 G=\langle V,E\rangle 为一无向图，v_i\in V，称 v_i 作为边的端点的次数之和为 v_i 的度数，简称为度，记作 d_G(v_i). 在不引起混淆情况下，简记为 d(v_i). 注意，每个环提供给它的端点 2 度.
设 D=\langle V,E\rangle 为一个有向图，v_i\in V，称 v_i 作为边的始点的次数之和为 v_i 的出度，记作 d_D^+(v_i)，简记为 d^+(v_i)；称 v_i 作为边的终点的次数之和为 v_i 的入度，记作 d_D^-(v_i)，简记为 d^-(v_i)；称 v_i 作为边的端点的次数之和为 v_i 的度数或度，记作 d_D(v_i)，简记为 d(v_i). 显然，d(v_i)=d^+(v_i)+d^-(v_i).
在图 6.1(a)中，d(v_1)=d(v_2)=3,d(v_3)=5,d(v_4)=1,d(v_5)=0. 在图 6.1(b)中，d^+(v_1)=1(由环 e_1 提供的)，d^-(v_1)=4,d(v_1)=5.d^+(v_2)=3,d^-(v_2)=0,d(v_2)=3,\cdots.
在图中，称度数为 1 的顶点为悬挂顶点，与它关联的边为悬挂边. 在图 6.1(a)中，v_4 是悬挂顶点，e_5 是悬挂边.
另外，称 \Delta(G)=\max\{d(v)\mid v\in V(G)\} 为 G 的最大度，\delta(G)=\min\{d(v)\mid v\in V(G)\} 为 G 的最小度. 在不会引起混淆的情况下，常把 \Delta(G) 简记作 \Delta，把 \delta(G) 简记作 \delta. 在图 6.1(a)中，\Delta=5,\delta=0. 图 6.1(b)中，\Delta=5,\delta=3.
设 D 为一有向图，又称
为 D 的最大出度；称
为 D 的最小出度；称
为 D 的最大入度；称
为 D 的最小入度. 在不引起混淆的情况下，常将 \Delta^+(D),\delta^+(D),\Delta^-(D),\delta^-(D) 分别简记为 \Delta^+,\delta^+,\Delta^-,\delta^-.
下面给出图论中的基本定理.
定理 6.1 设 G=\langle V,E\rangle 为任意一图(无向的或有向的)，V=\{v_1,v_2,\cdots,v_n\}，边的条数 |E|=m，则
证明 图中任何一条边均有两个端点. 在计算各顶点的度数之和时，每条边提供 2 度，当然 m 条边共提供 2m 度，这就是各顶点的度数之和.
此定理常常被称为握手定理，它有下面推论.
推论 任何图(有向图或无向图)中，度数为奇数的顶点个数是偶数.
证明 设 G=\langle V,E\rangle 为任意一图. 设
显然有,V_1\cap V_2=\varnothing,V_1\cup V_2=V. 由握手定理可知,
由于 2m,\sum_{v\in V_2}d(v) 为偶数,所以 \sum_{v\in V_1}d(v) 也为偶数. 可是,v\in V_1 时,d(v) 为奇数,奇数个奇数之和才能为偶数,所以 |V_1| 为偶数. 这就证明了我们的结论.
解读：握手定理只用了「每条边恰好贡献 2 度」这一点，所以它对无向图和有向图同时成立；由此推出的「奇度顶点成对出现」是后面判定度数列能否成图的第一道关卡。
对于有向图来说,还有下面定理.
定理 6.2 设 D=\langle V,E\rangle 为一有向图,V=\{v_1,v_2,\cdots,v_n\},|E|=m,则
证明 在有向图中,每条边均有一个始点和一个终点. 于是在计算 D 中各顶点的出度之和及入度之和时,每条边各提供一个出度和一个入度. 当然 m 条边共提供 m 个出度和 m 个入度,因而定理成立.
设 V=\{v_1,v_2,\cdots,v_n\} 为 n 阶图 G 的顶点集,称 d(v_1),d(v_2),\cdots,d(v_n) 为 G 的度数列. 图 6.1(a)的度数列为 3,3,5,1,0,其中有 4 个奇数. 图 6.1(b)的度数列为 5,3,3,3,全是奇数. 对于有向图还可分出度列和入度列. 在图 6.1(b)中,出度列为 1,3,2,1;入度列为 4,0,1,2.
例 6.1 (1) 以下两组数能构成无向图的度数列吗? 为什么?
① 2,3,4,5,6,7 ② 1,2,2,3,4
(2) 已知图 G 中有 11 条边,有 1 个 4 度顶点,4 个 3 度顶点,其余顶点的度数均小于等于 2,问 G 中至少有几个顶点?
(3) 已知 5 阶有向图 D 的顶点集 V=\{v_1,v_2,v_3,v_4,v_5\}. 它的度数列和出度列分别为 3,3,2,3,3 和 1,2,1,2,1. 试求 D 的入度列.
解 (1) ①中有 3 个奇数,所以不能构成图的度数列,否则将与握手定理的推论矛盾.
②中有两个奇数,可以找到多个图以②作度数列. 图 6.2 中的两个图均以②为度数列.
图 6.2
(2) 由握手定理可知,G 中各顶点的度数之和为 22. 1 个 4 度顶点,4 个 3 度顶点共占去 16 度. 还剩下 6 度,其余顶点的度数若全是 2,还需要 3 个顶点,所以 G 中至少有 1+4+3=8 个顶点.
(3) 对于任意的 v_i\in V(D),均有
因而 d^-(v_i)=d(v_i)-d^+(v_i),容易算出入度列为 2,1,1,1,2.
例 6.2 无向图 G 有 11 条边,2,3,4,5,6 度顶点各 1 个,其余顶点均为悬挂顶点(即 1 度顶点),求 G 中悬挂顶点个数.
解 设 G 有 x 个悬挂顶点. 由握手定理立即可解出 x:
可知 x=2.
例 6.3 设 n 阶 m 条边的无向图 G 中,m=n+1,证明 G 中存在顶点 v,d(v)\geqslant 3.
证明 用归谬法(反证法)证明之.
否则,\forall v\in V(G),均有 d(v)\leqslant 2,则由握手定理有
即 2n+2\leqslant 2n,这是个矛盾. 所以,存在 v,d(v)\geqslant 3.
例 6.4 证明：空间不存在有奇数个面且每个面均有奇数条棱的多面体.
证明 用归谬法(反证法)证明之. 假设存在多面体 P,它有奇数个面,且每个面均有奇数条棱. 做无向图 G=\langle V,E\rangle,V=\{v\mid v 为 P 的面\},记 V=\{v_1,v_2,\cdots,v_n\},则 n 为奇数,E=\{\{u,v\}\mid u,v\in V\wedge u 与 v 有公共棱\},记 |E|=m. 由握手定理可知
d(v_i) 全为奇数,n 为奇数,奇数个奇数之和为奇数,故上面等式是个矛盾,所以原命题为真.
解读：例 6.4 的关键是「把多面体的面看成图的顶点、公共棱看成边」——换一个视角后，题目就变成了握手定理推论的直接应用。
例 6.5 设 G 为 9 阶无向图,G 的每个顶点的度数不是 5 就是 6. 证明 G 中至少有 5 个 6 度顶点或至少有 6 个 5 度顶点.
证明 方法一：用分情况证明法.
设 G 中 5 度顶点与 6 度顶点的个数分别为 n_1 和 n_2,由握手定理推论可知,n_1 必为偶数,因而 n_1 只能为 0,2,4,6,8. 所以,n_1,n_2 的取值只有下面 5 种情况：
(1) n_1=0,n_2=9
(2) n_1=2,n_2=7
(3) n_1=4,n_2=5
(4) n_1=6,n_2=3
(5) n_1=8,n_2=1
(1),(2),(3)至少有 5 个 6 度顶点,(4),(5)至少有 6 个 5 度顶点.
方法二：用反证法.
否则,G 中至多有 4 个 6 度顶点,并且至多有 5 个 5 度顶点,但由握手定理的推论可知,G 至多有 4 个 5 度顶点,这蕴涵着 G 中至多有 8 个顶点,与 G 为 9 阶图矛盾,故原命题为真.
6.1.3 简单图、完全图、正则图、圈图、轮图、方体图
定义 6.4 在无向图中,关联一对顶点的无向边如果多于 1 条,称这些边为平行边,平行边的条数称为重数.
在有向图中,关联一对顶点的有向边如果多于 1 条,并且它们的始点与终点相同(即它们的方向相同),则称这些边为有向平行边,简称平行边.
含平行边的图称为多重图. 既不含平行边也不含环的图称为简单图.
易知,n 阶简单无向图的 \Delta\leqslant n-1.
图 6.1(a)中,e_1 与 e_2 是平行边,该图既有平行边,又有环,当然不是简单图. 图 6.1(b)中,e_2 与 e_7 是平行边,但 e_5 与 e_6 不是平行边(它们的方向不同). 当然它也不是简单图. 图 6.2(a)是既无平行边也无环的图,因而它是简单图. 图 6.2(b)也不是简单图(因为它含环).
在本小节下面的几个定义,都是针对简单图定义的.
定义 6.5 设 G=\langle V,E\rangle 是 n 阶无向简单图. 若 G 中的任何顶点都与其余的 n-1 个顶点相邻,则称 G 为 n 阶无向完全图,记作 K_n.
D=\langle V,E\rangle 是 n 阶有向简单图. 若对于任意的顶点 u,v\in V(u\neq v),既有 \langle u,v\rangle\in E,又有 \langle v,u\rangle\in E,则称 D 是 n 阶有向完全图.
在图 6.3 中,图(a),图(b)分别是无向完全图 K_3 和 K_5,图(c)是 3 阶有向完全图.
图 6.3
在无向完全图 K_n 中,边数 m=\mathrm{C}_n^2=\dfrac{n(n-1)}{2},在 n 阶有向完全图中,边数 m=2\mathrm{C}_n^2=n(n-1).
定义 6.6 设 G=\langle V,E\rangle 是无向简单图. 若 \Delta(G)=\delta(G)=k(各顶点度数均等于 k),则称 G 为 k-正则图.
图 6.3(a)为 2-正则图,图 6.3(b)为 4-正则图. 其实,K_n 都是正则图,且为 (n-1)-正则图. 请读者举出 5 阶 2-正则图,6 阶 3-正则图的例子.
由握手定理可知,n 阶 k-正则图的边数 m=k\cdot n/2.
定义 6.7 (1) 设 G=\langle V,E\rangle 为 n(n\geqslant 3) 阶无向简单图,V=\{v_1,v_2,\cdots,v_n\},E=\{(v_1,v_2),(v_2,v_3),\cdots,(v_{n-1},v_n),(v_n,v_1)\},则称 G 为 n 阶无向圈图,简称 n 阶圈图,记作 C_n.
(2) 设 D=\langle V,E\rangle 为 n(n\geqslant 2) 阶有向简单图,V=\{v_1,v_2,\cdots,v_n\},E=\{\langle v_1,v_2\rangle,\langle v_2,v_3\rangle,\cdots,\langle v_{n-1},v_n\rangle,\langle v_n,v_1\rangle\},则称 D 为 n 阶有向圈图,也可记为 C_n.
在图 6.4 中,图(a),图(b),图(c)分别为无向圈图 C_3,C_4 和 C_5,而图(d),图(e),图(f)分别为有向圈图 C_3,C_4,C_5. 无向圈图 C_n 均为 2-正则图.
图 6.4
定义 6.8 在无向圈图 C_{n-1}(n\geqslant 4) 内放置一个顶点,使该顶点与 C_{n-1} 上的每个顶点均相邻,所得简单图称为 n 阶轮图,记为 W_n.
图 6.5(a),(b),(c)所示分别为 W_4,W_5 和 W_6.
图 6.5
定义 6.9 设 G=\langle V,E\rangle 为 2^n(n\geqslant 1) 阶无向简单图,
则称 G 为 n 方体图,记为 Q_n.
图 6.6(a),(b),(c)分别为 Q_1,Q_2,Q_3.
图 6.6
解读：K_n、C_n、W_n、Q_n 这四个图类不是孤立的：C_n 是 2-正则图，W_n 是 C_{n-1} 加一个与所有顶点相邻的中心点，Q_n 则是把 n 位 0-1 串当顶点、按「恰好一位不同」连边——记住构造方式比记图形更可靠。
6.1.4 子图、补图
定义 6.10 设 G=\langle V,E\rangle,G'=\langle V',E'\rangle 是两个图(两图同为无向的,或同为有向的). 若 V'\subseteq V 且 E'\subseteq E,则称 G' 是 G 的子图,G 是 G' 的母图,记作 G'\subseteq G;若 G'\subseteq G 且 G'\neq G(即 V'\subset V 或 E'\subset E),则称 G' 是 G 的真子图;若 G'\subseteq G,且 V'=V,则称 G' 是 G 的生成子图.
设 \varnothing\neq V_1\subseteq V,以 V_1 为顶点集,以两个端点均在 V_1 中的全体边为边集的 G 的子图称为 V_1 导出的导出子图,记作 G[V_1].
设 \varnothing\neq E_1\subseteq E,以 E_1 为边集,以 E_1 中的边关联的顶点的全体为顶点集的 G 的子图称为 E_1 导出的导出子图,记作 G[E_1].
图 6.7(a),(b),(c)都是图(a)的子图,其中图(b),(c)是真子图. 图(a),(c)是图(a)的生成子图. 图(b)既可以看成 V_1=\{d,e,f\} 的导出子图 G[V_1],也可以看成 E_1=\{e_5,e_6,e_7\} 的导出子图 G[E_1]. 图(c)又可看成 E_2=\{e_1,e_3,e_5,e_7\} 导出的导出子图 G[E_2].
图 6.7
定义 6.11 设 G=\langle V,E\rangle 是 n 阶无向简单图. 以 V 为顶点集,以所有能使 G 成为完全图 K_n 的添加边组成的集合为边集的图称为 G 相对于 K_n 的补图,简称为 G 的补图,记作 \bar{G}.
图 6.8(b)是图(a)的补图,当然图(a)也是图(b)的补图. 显然,K_n 的补图为 n 阶零图,反之亦然.
图 6.8
解读：生成子图与导出子图的差别在「边能不能自己挑」——生成子图只要求顶点全保留、边随意删；导出子图的边必须由选定的顶点（或边）全部带出，不能只删一半。
6.1.5 图的同构
图是描述事物之间关系的手段,在画图时,由于顶点的位置及边的曲、直都没有什么规定,因而同一个事物之间的关系可能画出不同形状的图来,这就引出了图同构的概念.
定义 6.12 设 G_1=\langle V_1,E_1\rangle,G_2=\langle V_2,E_2\rangle 为两个无向图(有向图). 若存在双射函数 f:V_1\to V_2,使得对于任意的 e=(v_i,v_j)\in E_1 当且仅当 e'=(f(v_i),f(v_j))\in E_2(e=\langle v_i,v_j\rangle\in E_1 当且仅当 e'=\langle f(v_i),f(v_j)\rangle\in E_2),且 e 与 e' 的重数相同,则称 G_1 与 G_2 同构,记作 G_1\cong G_2.
从定义不难看出,图之间的同构关系是等价关系. 若 G_1=\langle V_1,E_1\rangle,G_2=\langle V_2,E_2\rangle 同构,则必有 |V_1|=|V_2|,|E_1|=|E_2|. 若它们都是标定图,可调整一个图的顶点次序,使 G_1 与 G_2 有相同的度数列. 我们还可以找出同构的两个图所应满足的许多必要条件,但这些条件不是充分的. 到目前为止,还没有找到判断两个图是否同构的简便方法,只能对一些简单图根据定义进行判别. 另外,可用破坏必要条件的方法来判断某些图之间不是同构的.
在图 6.9 中,(a)\cong(b),(c)\cong(d),(e)\cong(f). 在图(a)和图(b)中,设 f:V_1\to V_2,v_1,v_2,v_3,v_4,v_5 分别为 a,b,c,d,e 的像,可简记为 a\leftrightarrow v_1,b\leftrightarrow v_2,c\leftrightarrow v_3,d\leftrightarrow v_4,e\leftrightarrow v_5. 可验证,在这个映射下,保持边与顶点之间的关联关系,所以(a)\cong(b). 类似可证(c)\cong(d),(e)\cong(f). 但(c)不同构于(e),在(c)中存在着彼此相邻的 3 个顶点,但在(e)中不存在彼此相邻的 3 个顶点,所以(c)与(e)不同构. 图之间的同构关系具有传递性,因而(c)与(f)也不同构.
图 6.9
例 6.6 画出 4 阶 3 条边的所有非同构的无向简单图.
解 用握手定理及推论、简单图的性质(\Delta\leqslant n-1)解本题. 由握手定理可知,画出的图度数之和应为 6,将 6 分配给 4 个顶点,每个顶点至少得 0,至多得 3(因为 \Delta\leqslant 4-1=3),又要求其中含偶数个奇数,于是所得图的度数列只有以下 3 种：①1,1,1,3;②1,1,2,2;③0,2,2,2. 再根据每种度数列画出所有非同构的图,本题中,每种度数均有一个非同构的无向简单图,因而共有 3 个非同构的无向简单图满足要求,如图 6.10(a),(b),(c)所示. 有时同一个度数列可以对应多个非同构的无向简单图,见例 6.7.
图 6.10
例 6.7 画出以 1,1,1,2,2,3 为度数列的 3 个非同构的无向简单图.
解 图 6.11 所示 3 个无向简单图均以 1,1,1,2,2,3 为度数列,它们彼此非同构.
图 6.11
解读：例 6.6 的解题顺序值得记住——先用握手定理定「度数和」，再用 \Delta\leqslant n-1 定「每个度的上界」，最后用「奇度顶点个数为偶数」筛出可行的度数列，画图是最后一步。