本节对应原书 PDF 第 156–159 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。
6.2.1 通路与回路
通路与回路是图论中的两个重要而又基本的概念,本节将给出这两个概念. 本节中所给出的定义一般说来既适合无向图,又适合有向图,否则将加以说明或重新给出关于有向图所涉及的定义.
定义 6.13 给定图 G=\langle V,E\rangle. 设 G 中顶点和边的交替序列为 \Gamma=v_0e_1v_1e_2\cdots e_lv_l.
若 \Gamma 满足如下条件：v_{i-1} 和 v_i 是 e_i 的端点(G 为有向图时,要求 v_{i-1} 是 e_i 的始点,v_i 是 e_i 的终点),i=1,2,\cdots,l,则称 \Gamma 为 v_0 到 v_l 的通路. v_0,v_l 分别称为此通路的起点和终点. \Gamma 中所含边的数目 l 称为 \Gamma 的长度. 当 v_0=v_l 时,称通路为回路.
若 \Gamma 中所有边各异,则称 \Gamma 为简单通路,此时,又若 v_0=v_l,则称 \Gamma 为简单回路.
若 \Gamma 的所有顶点各异,所有边也各异,则称 \Gamma 为初级通路或路径. 此时,又若 v_0=v_l,则称 \Gamma 为初级回路或圈,并将长度为奇数的圈称为奇圈,长度为偶数的圈称为偶圈.
若 \Gamma 中有边重复出现,则称 \Gamma 为复杂通路,又若 v_0=v_l,则称 \Gamma 为复杂回路.
对定义 6.13 给出下面几点说明.
(1) 回路是通路的特殊情况.
(2) 初级通路(回路)是简单通路(回路),但反之不真.
(3) 通路(回路)表示法如下：
① 定义给出的顶点与边的交替序列表示法：\Gamma=v_0e_1v_1e_2\cdots e_lv_l,回路：v_0e_1v_1e_2\cdots e_lv_0(因 v_l=v_0).
② 也可以只用边表示通路(回路)：\Gamma=e_1e_2\cdots e_l,若为回路,则 e_1 与 e_l 相邻.
③ 在简单图中,也可以只用顶点表示通路(回路)：\Gamma=v_0v_1\cdots v_{l-1}v_l,回路：v_0v_1\cdots v_{l-1}v_0(v_l=v_0).
(4) 在无向图中,长度为 1 的圈由环给出,长度为 2 的圈由两条平行边给出. 在简单图中,圈长至少为 3. 在有向图中,长度为 1 的圈由环给出. 有向简单图中,圈长至少为 2.
解读：四种「通路」是层层加码的关系——通路只要求首尾相接，简单通路再加「边不重复」，初级通路（路径）再加「顶点不重复」。回路只是把起点和终点重合，其余条件照旧，所以「简单回路」不等于「初级回路」。
定理 6.3 在一个 n 阶图中,若从顶点 u 到 v(u\neq v)存在通路,则从 u 到 v 存在长度小于等于 n-1 的初级通路.
证明 设 \Gamma=v_0e_1v_1\cdots e_lv_l(v_0=u,v_l=v)为 u 到 v 的通路,若 \Gamma 上无重复出现的顶点,则 \Gamma 为初级通路. 否则必存在 t<s,v_t=v_s,在 \Gamma 中去掉 v_t 到 v_s 的一段,所得通路仍为 u 到 v 的通路. 不妨仍记为 \Gamma. 若 \Gamma 上还有重复出现的顶点,就做同样的处理,直到无重复出现的顶点为止. 最后得到的通路是 u 到 v 的初级通路. 显然它的长度应小于等于 n-1.
类似可证下面定理.
定理 6.4 在一个 n 阶图中,如果存在 v 到自身的简单回路,则从 v 到自身存在长度不超过 n 的初级回路.
解读：定理 6.3 的证明手法是「砍圈」：只要路径上出现重复顶点，就把中间那一段绕行删掉，通路仍然成立。因为 n 个顶点最多出现一次，剩下的长度自然不超过 n-1。
6.2.2 无向图的连通性与连通度
定义 6.14 在无向图 G 中,若顶点 v_i 与 v_j 之间存在通路,则称 v_i 与 v_j 是连通的. 规定 v_i 与自身是连通的.
若无向图 G 是平凡图,或 G 中任二顶点都是连通的,则称 G 是连通图,否则称 G 是非连通图.
设 G=\langle V,E\rangle 为一无向图,设
则 R 是自反的,对称的,并且是传递的,因而 R 是 V 上的等价关系. 设 R 的不同的等价类分别为 V_1,V_2,\cdots,V_k,称它们的导出子图 G[V_1],G[V_2],\cdots,G[V_k] 为 G 的连通分支,其连通分支的个数记为 p(G). 若 G 是连通图,则 p(G)=1. 若 p(G)\geqslant 2,则 G 一定是非连通图.
设 v_i,v_j 为无向图 G 中的任意两个顶点. 若 v_i 与 v_j 是连通的,则称 v_i 与 v_j 之间长度最短的通路为 v_i 与 v_j 之间的短程线. 短程线的长度称为 v_i 与 v_j 之间的距离,记作 d(v_i,v_j). 若 v_i 与 v_j 不连通,规定 d(v_i,v_j)=\infty. 距离有如下性质：
(1) d(v_i,v_j)\geqslant 0,并且当且仅当 v_i=v_j 时,等号成立;
(2) 满足三角不等式,即对于任意 3 个顶点 v_i,v_j,v_k,有 d(v_i,v_j)+d(v_j,v_k)\geqslant d(v_i,v_k);
(3) d(v_i,v_j)=d(v_j,v_i).
在图 6.12 中,a 与 d 之间的短程线有两条：aed,d(a,d)=2. a 与 g 之间的短程线有一条：afg,d(a,g)=2. 易知,d(a,b)=1,d(a,h)=\infty.
图 6.12
对于无向连通图 G 来说,常由删除 G 中的一些顶点或删除一些边,而破坏其连通性. 所谓从 G 中删除顶点 v,是指从 G 中去掉 v 及其关联的一切边. 从 G 中删除顶点子集 V' 是指从 G 中删除 V' 中的所有顶点. 用 G-v 表示从 G 中删除 v,用 G-V' 表示从 G 中删除 V'.
所谓从 G 中删除边 e,是指从 G 中去掉边 e,记作 G-e. 删除边集的子集 E',是指从 G 中删除 E' 中所有边,记作 G-E'.
设图 G 为图 6.13 中(a)所示. G-a 为图 6.13(b)所示,G-e 为(c)所示,G-\{a,c\} 为图 6.13(d)所示,G-e_6 为图 6.13(e)所示,G-\{e_2,e_5\} 为图 6.13(f)所示.
图 6.13
定义 6.15 设无向图 G=\langle V,E\rangle. 若存在顶点集 V'\subset V,使得 p(G-V')>p(G),而对于任意的 V''\subset V',均有 p(G-V'')=p(G),则称 V' 是 G 的点割集. 若图 G 的某个点割集中只有一个顶点,则称该顶点为割点.
若存在边子集 E'\subset E,使得 p(G-E')>p(G),而对于任意的 E''\subset E',均有 p(G-E'')=p(G),则称 E' 是 G 的边割集,简称割集. 若 G 的某边割集中只有一条边,则称该边为割边或称为桥.
在图 6.13(a)中,\{e\},\{a,c\},\{a,d\} 等都是点割集,其中 e 是割点. 而 \{a\},\{b,e\},\{a,c,d\} 等都不是点割集. \{e_6\},\{e_1,e_5\},\{e_1,e_3\} 等都是边割集,其中 e_6 是桥. 而 \{e_1,e_6\},\{e_2,e_3,e_1\} 等都不是边割集.
关于点割集和边割集,有以下几点：
(1) 完全图 K_n 无点割集,因为从 K_n 中删除 k(k\leqslant n-1) 个顶点后,所得图仍然是连通的.
(2) n 阶零图既无点割集,也无边割集.
(3) 若 G 是连通图,E' 为 G 的边割集,则 p(G-E')=2. 理由如下：显然,p(G-E')\geqslant 2. 又任取 e\in E',令 E''=E'-\{e\}. 根据定义,p(G-E'')=p(G)=1. 而删去一条边至多增加一个连通分支,故 p(G-E')=2.
(4) 若 G 是连通图,V' 是 G 的点割集,则 p(G-V')\geqslant 2. 而且可能 p(G-V')>2,这是因为删去一个顶点可能产生多个连通分支.
解读：点割集定义里的「极小性」条件容易被忽略：V' 必须自己是使分支数增加的集合，而它的任何真子集都不能做到。所以 \{a,c,d\} 这种「多带了一个用不上的点」的集合不算点割集。
对一个连通图来说,若它存在点割集和边割集,就可以用含元素个数最少的点割集和边割集来刻画它的连通程度.
定义 6.16 设 G 为一个无向连通图. 设
则称 \kappa(G) 为 G 的点连通度. 令
则称 \lambda(G) 为 G 的边连通度.
规定非连通图的点连通度和边连通度都是 0.
从定义可以看出以下几点：
(1) 若 G 是平凡图,则 \kappa(G)=\lambda(G)=0. 这里约定：\min\varnothing=0.
(2) 若 G 是完全图 K_n,由于 G 无点割集,当删除 n-1 个顶点后,G 成为平凡图,所以 \kappa(G)=n-1.
(3) 若 G 中存在割点,则 \kappa(G)=1;若 G 中存在割边(桥),则 \lambda(G)=1.
在图 6.13(a)中图既有割点 e,又有桥 e_6,所以它的 \kappa 与 \lambda 均为 1. 圈图 C_n(n\geqslant 3) 的 \kappa=\lambda=2. 而轮图 W_n(n\geqslant 4) 的 \kappa=\lambda=3.
对于任何图 G 来说,它的点连通度 \kappa,边连通度 \lambda 与最小度 \delta 有如下定理给出的关系.
定理 6.5 对于任何无向图 G,有
解读：定理 6.5 的记忆方式是「点最脆弱」：删点比删边更省事，所以点连通度最小；而每个顶点最多关联 \delta 条边，所以边连通度不超过最小度。
6.2.3 有向图的连通性及其分类
定义 6.17 设 D=\langle V,E\rangle 为一有向图. 设 v_i,v_j 为 D 中任意两个顶点. 若从 v_i 到 v_j 有通路,则称 v_i 可达 v_j,规定 v_i 到自身总是可达的. 设 v_i,v_j 为 D 中任意两个顶点. 若 v_i 可达 v_j, v_j 也可达 v_i,则称 v_i 与 v_j 是相互可达的. v_i 与自身是相互可达的.
同无向图的情况类似,若 v_i 可达 v_j,则称 v_i 到 v_j 长度最短的通路为 v_i 到 v_j 的短程线,短程线的长度称为 v_i 到 v_j 的距离,记作 d\langle v_i,v_j\rangle. d\langle v_i,v_j\rangle 除记法及无对称性外,有与 d(v_i,v_j) 相类似的性质.
定义 6.18 设 D 为一有向图. 如果略去 D 中各边的方向所得无向图是连通图,则称 D 是弱连通图或连通图. 若 D 中任意两个顶点至少一个可达另一个,则称 D 是单向连通图. 若 D 中任意两个顶点都是相互可达的,则称 D 是强连通图.
显然,一个有向图是强连通的,它一定是单向连通的;若是单向连通的,它必为弱连通的. 但反之都不真.
图 6.14 所示各图中,图(a)是强连通的,当然也是单向连通和弱连通的. 图(b)是单向连通的,也是弱连通的,但不是强连通的. 图(c)是弱连通的,不是单向连通的,更不是强连通的.
图 6.14
可用下面方法来判断一个有向图 D 是否为强连通的或是否为单向连通的.
判别法 1：若有向图 D 中存在经过每个顶点至少一次的回路. 则 D 是强连通的.
判别法 2：若有向图 D 中存在经过每个顶点至少一次的通路,则 D 是单向连通的.
由判别法 1 可知图 6.14(a)是强连通的,图 6.14(b)是单向连通的.
其实,判别法给出的条件也是必要的.
解读：三种有向连通性是逐级放松的：强连通要求任意两点双向可达，单向连通只要求任意两点至少一个方向可达，弱连通则干脆把箭头抹掉再看是否连通。判定时用「经过所有顶点的回路/通路」比逐对检查更省事。