7-2 路与回路在现实世界中，常常要考虑这样的问题：如何从一个图中的给定结点出发，沿着一些边连续移动而达到另一指定结点，这种依次由点和边组成的序列，就形成了路的概念。
学习本节要熟悉如下术语 (22个 )：
路,路的长度,迹、回路,通路,圈、
连通,连通分支,点割集、连通图,割点、
点连通度,边割集,边连通度、割边,可达、
单侧连通,强连通,强分图、弱连通,弱分图、
单侧分图掌握 5个定理，一个推论。
一、路定义 7-2.1 给定 图 G=<V,E>,设 v0,v1,…,vn?V,e1,…,en?E,其中 ei是关联于结点 vi-1,vi的边，交替序列 v0e1v1e2…e nvn称为结点 v0
到 vn的 路 （ 拟路径 Pseudo path） 。
v0和 vn分别称为路的 起点 和 终点,
边的数目 n称作路的 长度 。
当 v0=vn时，这条路称作 回路 （ 闭路径 closed walk） 。
若一条路中所有的边 e1,…,en均不相同,称作 迹 （ 路径 walk） 。
若一条路中所有的结点 v0,v1,…,vn均不相同,称作 通路
（ Path） 。
闭的通路,即除 v0=vn之外，其余结点均不相同的路，称作 圈
（ 回路 circuit） 。
见图 7-2.1中路的例子。
例如路,v1e2v3e3v2e3v3e4v2e6v5e7v3
迹,v5e8v4e5v2e6v5e7v3e4v2
通路,v4e8v5e6v2e1v1e2v3
圈,v2e1v1e2v3e7v5e6v2
在简单图中一条路 v0e1v1e2…e nvn，由它的结点序列 v0,v1,…,vn确定，所以简单图的路，
可由其结点序列表示。在有向图中，结点数大于一的 — 条路亦可由边序列 e1e2…e n表示。
定理 7-2.1 在一个具有 n个结点的图中，如果从结点 vj到结点 vk存在一条路，则从结点 vj到结点 vk必存在一条不多于 n-1条边的路 。
证明思路：多于 n-1条边的路中必有重复出现的结点，反复删去夹在两个重复结点之间的边之后，剩余的边数不会超过 n-1条边 。
定理 7-2.1的推论 在一个具有 n个结点的图中，
如果从结点 vj到结点 vk存在一条路，则从结点 vj到结点
vk必存在一条边数小于 n的通路 。
定理 7-2.1的 证明如果从结点 vj到 vk存在一条路，该路上的结点序列是 vj…v i…v k，如果在这条中有 l条边，则序列中必有 l+1个结点，若 l>n-1，则必有结点 vs，
它在序列中不止出现一次，即必有结点序列
vj…v s…v s…v k，在路中去掉从 vs到 vs的这些边，
仍是 vj到 vk的一条路，但此路比原来的路边数要少，如此重复进行下去，必可得到一条从 vj到 vk
的不多于 n-1条边的路。
如在图 7-2.1中有 5个结点。 v1到 v3的一条路为：
v1e2v3e3v2e3v3e4v2e6v5e7v3
此路中有 6条边，去掉 e3有路
v1e2v3e4v2e6v5e7v3
有 4条边。
v1到 v3最短的路为 v1e2v3
二、无向图的连通性：
1、连通见 281页图 7-2.2
定义 7-2.2 在无向 图 G中，如果从结点 u和结点 v
之间若 存在一条路，则称结点 u和结点 v是 连通的
（ connected） 。
结点之间的连通性是结点集 V上的等价关系，对应该等价关系，必可将作出一个划分，把 V分成非空子集 V1,V2,…,Vm,使得两个结点 vj和 vk是连通的，当且仅当它们属于同一个 Vi 。 把子图 G(V1),G(V2),…,
G(Vm)称为图 G的 连通分支 （ connected components）,
图 G的连通分支数记为 W(G) 。
2、连通图定义 7-2.3：若图 G只有一个连通分支，则称
G是连通图。
显然在连通图中，任意两个结点之间必是连通的。
再见 281页图 7-2.2图
7-2.2(a)是连通图对于连通图，常常由于删除了图中的点或边，而影响了图的连通性。
删除结点,所谓在图中删除 结点 v,即是把 v以及与 v关联的边都删除。
删除边,所谓在图中删除某条边,即是把该边删除。
见 282页图 7-2.3
v3
v2
v1
v6
v4
(a) v5 v5v1
v2
v3 v6
v4
(c)
e
v3
v2
v6
v4
(b) v5
e
3、割点定义 7-2.4 设无向 图 G =<V,E>是 连通图,若有结点集 V1?V,使图 G中 删除了 V1的所有结点后,所得到的子图是不连通图,而删除了 V1的任何真子集后,所得到的子图仍是 连通图,则称 V1
是 G的一个 点割集 (cut-set of nodes) 。 若某一个点构成一个点割集，则称该点为割点。
如 282页图 7-2.4(a)中的点 s就是割点。
s
a
b
c
d
a
b
c
d
ba
点连通度：是为了产生一个不连通图需要删去的点的最少数目，也称为连通度，记为 k(G) 。
即 k(G)=min{|V1|| 是 G的点割集 } 称为图 G的 点连通度
(node-connectivity) 。
(1)若 G是平凡图则 V1=?,k(G)=0
(2)k(Kn)=n-1
(3)若图存在割点，则 k(G)=1
(4)规定非连通图的连通度 k(G)=0
v5
v1
v2
v3
v4
v5
v1
v3
v4
点割集 V1={v2}
4、割边定义 7-2.5 设无向 图 G =<V,E>是 连通图,若有边集 E1?E，使图 G中 删除了 E1的所有边后，所得到的子图是不连通图，而删除了 E1的任何真子集后，所得到的子图仍是 连通图，则称 E1是 G的一个 边割集
(cut-set of edges) 。 若某一条边就构成一个边割集，
则称该边为 割边 或 桥 。
割边 e使图 G满足 W(G-e)>W(G) 。
边 连通度 (edge-connectivity)? (G)定义,非平凡图的边连通度为
(G)=min{ |E1| | E1是 G的边割集 }
边连通度?(G)是为了产生一个不连通图需要删去的边的最少数目。
(1)若 G是平凡图则 E1=?,(G)=0
(2)若 G存在割边，则?(G)=1，
(3)规定非连通图的边连通度为?(G)=0
5,定理 7-2.2 对于任何一个 图 G,有 k(G)≤?(G)≤ δ (G) 。
在 7-2.2节定义了图的最小度：
δ(G)=min(deg(v),v?V)
下面的定理给出了点连通度 k(G),边连通度?(G)和图的最小度?(G)之间的关系。
证明：
若 G不连通，则 k(G)=?(G)=0，故上式成立。
若 G连通,可分两步证明上式也成立：
1)先证明?(G)≤?(G)：
如果 G是平凡图，则?(G)=0≤?(G)，
若 G是非平凡图，则因每一结点的所有关联边必含一个边割集,(因?(G)=min{deg(v)|v?V}，
设 u?V使的 deg(u)=δ(G)，与 u相关联的?条边必包含一个边割集，至少这?条边删除使图不连通。 )
故?(G)≤?(G)。
2)再证 k(G)≤?(G)：
(a)设?(G)=1，即 G有一割边，显然这时 k(G)=l，上式成立。
(b)设?(G)≥2，则必可删去某?(G)条边，使 G不连通，
而删去其中?(G)-1条边，它仍是连通的，且有一条桥
e=(u,v)。对?(G)-1条边中的每一条边都选取一个不同于 u,v的端点，把这些端点删去则必至少删去
(G)-1条边。若这样产生的图是不连通的，则
k(G)≤?(G)-1<?(G)，若这样产生的图是连通的，则
e仍是桥，此时再删去 u或 v就必产生一个不连通图，
故 k(G)≤?(G)。由 1)和 2)得 k(G)≤?(G)≤?(G)。
6.定理 7-2.3 一个连通 无向图 G的结点 v是割点的充分必要条件是存在两个结点 u和 w,使得结点 u和 w的每一条路都通过 v。
证明思路：
1) 先证,v是割点?存在结点 u和 w的每条路都通过 v
若 v是连通图 G=<V,E>割点，设删去 v得到的子图 G’,则 G’至少包含两个连通分支 G1=<V1,E1>和 G2=<V2,E2> 。 任取 u?V1，
w?V2,因为 G是连通的，故在 G中必有一条连结 u和 w的路 C,但 u
和 w在 G’中属于两个不同的连通分支，故 u和 w必不连通，因此 C
必须通过 v,故 u和 w之间的任意一条路都通过 v 。
2)再证,存在结点 u和 w的每条路都通过 v?v是割点若连通图 G中的某两个结点的每一条路都通过 v，则删去 v得到子图 G’,在 G’中这两个结点必然不连通，故 v是图 G的割点。
三、有向图的连通性：
1、可达：
在无向图 G中，从结点 u到 v若存在一条路，则称结点 u到结点 v是可达的。
有向图的可达性,对于任何一个有向 图 G=<V,E>,从结点 u和到结点 v有一条路,称为从 u可达 v。
可达性 (accesible),是结点集上的二元关系，它是自反的和传递的，但是一般来说不是对称的。故可达性不是等价关系。
如果 u可达 v，它们之间可能不止一条路，在所有这些路中，最短路的长度称为 u和 v之间的距离（或短程线），记作 d<u,v>，它满足下列性质：
d<u,v>≥0
d<u,u> =0
d<u,v> + d<v,w> ≥ d<u,w>
有关距离的概念对无向图也适用，把
D=max d<u,v>,u,v∈ V
称作图的直径。
如果从 u到 v是不可达的，则通常写成 d<u,v> =∞
注意：当 u可达 v，且 v也可达 u时,d<u,v> 不一定等于
d< v,u >
2,定义 7-2.6 在简单有向 图 G中，任何一对结点 间，
至少有一个结点到另一个结点是可达的，则称这个图是 单侧连通 的 。如果对于图 G中的任何一对结点两者之间是相互可达的，则称这个图是 强连通 的。如果在图 G中略去边的方向，将它看成无向图后，图是连通的，则称该图为 弱连通 的。
显然，强连通图 → 单侧连通图 → 弱连通图。而逆推均不成立。
v2
v3 v4
v1
(a)强连通
v2
v3 v4
v1
(b)单侧连通
v2
v3 v4
v1
(c)弱连通证明：充分性：如 G中有一条有向回路，经过每一点至少一次，则 G中任意两点 u,v∈ V,u可以沿着该有向回路的一部分的而到达 v，则 G是强连通图。
3、定理 7-2.4：一个有向图是强连通的充分必要条件是 G有一个回路，它至少包含每个结点一次。
必要性：任取 u,v∈ V，图 G是强连通图，则 u→v
有有向路,v→u 也有有向路，则 u→v→u 构成了一个有向回路，如果该有向回路没有包含 w，而 u→w,
w→u 均有有向路，则 u→v→u→w→u 又是一个有向回路，一直下去可以将图中所有的点均包含进去。
4、定义 7-2.7：在简单有向图中，具有强连通性质的最大子图，称为强分图；具有单侧连通性质的最大子图，称为单侧分图；具有弱连通性质的最大子图，称为弱分图。
v4
v2 v3
v1
(b)
v4
v2 v3
v1
(a)
v5
练习 286,287页习题定理 7-2.5 在有向图 G=<V,E>中，它的每一个结点位于且只位于一个强分图中。
证明思路：
1)先证,每一个结点 必 位于一个强分图中。
2)再证,每一个结点 只 位于一个强分图中。
学习本节要熟悉如下术语 (22个 )：
路,路的长度,迹、回路,通路,圈、
连通,连通分支,点割集、连通图,割点、
点连通度,边割集,边连通度、割边,可达、
单侧连通,强连通,强分图、弱连通,弱分图、
单侧分图掌握 5个定理，一个推论。
一、路定义 7-2.1 给定 图 G=<V,E>,设 v0,v1,…,vn?V,e1,…,en?E,其中 ei是关联于结点 vi-1,vi的边，交替序列 v0e1v1e2…e nvn称为结点 v0
到 vn的 路 （ 拟路径 Pseudo path） 。
v0和 vn分别称为路的 起点 和 终点,
边的数目 n称作路的 长度 。
当 v0=vn时，这条路称作 回路 （ 闭路径 closed walk） 。
若一条路中所有的边 e1,…,en均不相同,称作 迹 （ 路径 walk） 。
若一条路中所有的结点 v0,v1,…,vn均不相同,称作 通路
（ Path） 。
闭的通路,即除 v0=vn之外，其余结点均不相同的路，称作 圈
（ 回路 circuit） 。
见图 7-2.1中路的例子。
例如路,v1e2v3e3v2e3v3e4v2e6v5e7v3
迹,v5e8v4e5v2e6v5e7v3e4v2
通路,v4e8v5e6v2e1v1e2v3
圈,v2e1v1e2v3e7v5e6v2
在简单图中一条路 v0e1v1e2…e nvn，由它的结点序列 v0,v1,…,vn确定，所以简单图的路，
可由其结点序列表示。在有向图中，结点数大于一的 — 条路亦可由边序列 e1e2…e n表示。
定理 7-2.1 在一个具有 n个结点的图中，如果从结点 vj到结点 vk存在一条路，则从结点 vj到结点 vk必存在一条不多于 n-1条边的路 。
证明思路：多于 n-1条边的路中必有重复出现的结点，反复删去夹在两个重复结点之间的边之后，剩余的边数不会超过 n-1条边 。
定理 7-2.1的推论 在一个具有 n个结点的图中，
如果从结点 vj到结点 vk存在一条路，则从结点 vj到结点
vk必存在一条边数小于 n的通路 。
定理 7-2.1的 证明如果从结点 vj到 vk存在一条路，该路上的结点序列是 vj…v i…v k，如果在这条中有 l条边，则序列中必有 l+1个结点，若 l>n-1，则必有结点 vs，
它在序列中不止出现一次，即必有结点序列
vj…v s…v s…v k，在路中去掉从 vs到 vs的这些边，
仍是 vj到 vk的一条路，但此路比原来的路边数要少，如此重复进行下去，必可得到一条从 vj到 vk
的不多于 n-1条边的路。
如在图 7-2.1中有 5个结点。 v1到 v3的一条路为：
v1e2v3e3v2e3v3e4v2e6v5e7v3
此路中有 6条边，去掉 e3有路
v1e2v3e4v2e6v5e7v3
有 4条边。
v1到 v3最短的路为 v1e2v3
二、无向图的连通性：
1、连通见 281页图 7-2.2
定义 7-2.2 在无向 图 G中，如果从结点 u和结点 v
之间若 存在一条路，则称结点 u和结点 v是 连通的
（ connected） 。
结点之间的连通性是结点集 V上的等价关系，对应该等价关系，必可将作出一个划分，把 V分成非空子集 V1,V2,…,Vm,使得两个结点 vj和 vk是连通的，当且仅当它们属于同一个 Vi 。 把子图 G(V1),G(V2),…,
G(Vm)称为图 G的 连通分支 （ connected components）,
图 G的连通分支数记为 W(G) 。
2、连通图定义 7-2.3：若图 G只有一个连通分支，则称
G是连通图。
显然在连通图中，任意两个结点之间必是连通的。
再见 281页图 7-2.2图
7-2.2(a)是连通图对于连通图，常常由于删除了图中的点或边，而影响了图的连通性。
删除结点,所谓在图中删除 结点 v,即是把 v以及与 v关联的边都删除。
删除边,所谓在图中删除某条边,即是把该边删除。
见 282页图 7-2.3
v3
v2
v1
v6
v4
(a) v5 v5v1
v2
v3 v6
v4
(c)
e
v3
v2
v6
v4
(b) v5
e
3、割点定义 7-2.4 设无向 图 G =<V,E>是 连通图,若有结点集 V1?V,使图 G中 删除了 V1的所有结点后,所得到的子图是不连通图,而删除了 V1的任何真子集后,所得到的子图仍是 连通图,则称 V1
是 G的一个 点割集 (cut-set of nodes) 。 若某一个点构成一个点割集，则称该点为割点。
如 282页图 7-2.4(a)中的点 s就是割点。
s
a
b
c
d
a
b
c
d
ba
点连通度：是为了产生一个不连通图需要删去的点的最少数目，也称为连通度，记为 k(G) 。
即 k(G)=min{|V1|| 是 G的点割集 } 称为图 G的 点连通度
(node-connectivity) 。
(1)若 G是平凡图则 V1=?,k(G)=0
(2)k(Kn)=n-1
(3)若图存在割点，则 k(G)=1
(4)规定非连通图的连通度 k(G)=0
v5
v1
v2
v3
v4
v5
v1
v3
v4
点割集 V1={v2}
4、割边定义 7-2.5 设无向 图 G =<V,E>是 连通图,若有边集 E1?E，使图 G中 删除了 E1的所有边后，所得到的子图是不连通图，而删除了 E1的任何真子集后，所得到的子图仍是 连通图，则称 E1是 G的一个 边割集
(cut-set of edges) 。 若某一条边就构成一个边割集，
则称该边为 割边 或 桥 。
割边 e使图 G满足 W(G-e)>W(G) 。
边 连通度 (edge-connectivity)? (G)定义,非平凡图的边连通度为
(G)=min{ |E1| | E1是 G的边割集 }
边连通度?(G)是为了产生一个不连通图需要删去的边的最少数目。
(1)若 G是平凡图则 E1=?,(G)=0
(2)若 G存在割边，则?(G)=1，
(3)规定非连通图的边连通度为?(G)=0
5,定理 7-2.2 对于任何一个 图 G,有 k(G)≤?(G)≤ δ (G) 。
在 7-2.2节定义了图的最小度：
δ(G)=min(deg(v),v?V)
下面的定理给出了点连通度 k(G),边连通度?(G)和图的最小度?(G)之间的关系。
证明：
若 G不连通，则 k(G)=?(G)=0，故上式成立。
若 G连通,可分两步证明上式也成立：
1)先证明?(G)≤?(G)：
如果 G是平凡图，则?(G)=0≤?(G)，
若 G是非平凡图，则因每一结点的所有关联边必含一个边割集,(因?(G)=min{deg(v)|v?V}，
设 u?V使的 deg(u)=δ(G)，与 u相关联的?条边必包含一个边割集，至少这?条边删除使图不连通。 )
故?(G)≤?(G)。
2)再证 k(G)≤?(G)：
(a)设?(G)=1，即 G有一割边，显然这时 k(G)=l，上式成立。
(b)设?(G)≥2，则必可删去某?(G)条边，使 G不连通，
而删去其中?(G)-1条边，它仍是连通的，且有一条桥
e=(u,v)。对?(G)-1条边中的每一条边都选取一个不同于 u,v的端点，把这些端点删去则必至少删去
(G)-1条边。若这样产生的图是不连通的，则
k(G)≤?(G)-1<?(G)，若这样产生的图是连通的，则
e仍是桥，此时再删去 u或 v就必产生一个不连通图，
故 k(G)≤?(G)。由 1)和 2)得 k(G)≤?(G)≤?(G)。
6.定理 7-2.3 一个连通 无向图 G的结点 v是割点的充分必要条件是存在两个结点 u和 w,使得结点 u和 w的每一条路都通过 v。
证明思路：
1) 先证,v是割点?存在结点 u和 w的每条路都通过 v
若 v是连通图 G=<V,E>割点，设删去 v得到的子图 G’,则 G’至少包含两个连通分支 G1=<V1,E1>和 G2=<V2,E2> 。 任取 u?V1，
w?V2,因为 G是连通的，故在 G中必有一条连结 u和 w的路 C,但 u
和 w在 G’中属于两个不同的连通分支，故 u和 w必不连通，因此 C
必须通过 v,故 u和 w之间的任意一条路都通过 v 。
2)再证,存在结点 u和 w的每条路都通过 v?v是割点若连通图 G中的某两个结点的每一条路都通过 v，则删去 v得到子图 G’,在 G’中这两个结点必然不连通，故 v是图 G的割点。
三、有向图的连通性：
1、可达：
在无向图 G中，从结点 u到 v若存在一条路，则称结点 u到结点 v是可达的。
有向图的可达性,对于任何一个有向 图 G=<V,E>,从结点 u和到结点 v有一条路,称为从 u可达 v。
可达性 (accesible),是结点集上的二元关系，它是自反的和传递的，但是一般来说不是对称的。故可达性不是等价关系。
如果 u可达 v，它们之间可能不止一条路，在所有这些路中，最短路的长度称为 u和 v之间的距离（或短程线），记作 d<u,v>，它满足下列性质：
d<u,v>≥0
d<u,u> =0
d<u,v> + d<v,w> ≥ d<u,w>
有关距离的概念对无向图也适用，把
D=max d<u,v>,u,v∈ V
称作图的直径。
如果从 u到 v是不可达的，则通常写成 d<u,v> =∞
注意：当 u可达 v，且 v也可达 u时,d<u,v> 不一定等于
d< v,u >
2,定义 7-2.6 在简单有向 图 G中，任何一对结点 间，
至少有一个结点到另一个结点是可达的，则称这个图是 单侧连通 的 。如果对于图 G中的任何一对结点两者之间是相互可达的，则称这个图是 强连通 的。如果在图 G中略去边的方向，将它看成无向图后，图是连通的，则称该图为 弱连通 的。
显然，强连通图 → 单侧连通图 → 弱连通图。而逆推均不成立。
v2
v3 v4
v1
(a)强连通
v2
v3 v4
v1
(b)单侧连通
v2
v3 v4
v1
(c)弱连通证明：充分性：如 G中有一条有向回路，经过每一点至少一次，则 G中任意两点 u,v∈ V,u可以沿着该有向回路的一部分的而到达 v，则 G是强连通图。
3、定理 7-2.4：一个有向图是强连通的充分必要条件是 G有一个回路，它至少包含每个结点一次。
必要性：任取 u,v∈ V，图 G是强连通图，则 u→v
有有向路,v→u 也有有向路，则 u→v→u 构成了一个有向回路，如果该有向回路没有包含 w，而 u→w,
w→u 均有有向路，则 u→v→u→w→u 又是一个有向回路，一直下去可以将图中所有的点均包含进去。
4、定义 7-2.7：在简单有向图中，具有强连通性质的最大子图，称为强分图；具有单侧连通性质的最大子图，称为单侧分图；具有弱连通性质的最大子图，称为弱分图。
v4
v2 v3
v1
(b)
v4
v2 v3
v1
(a)
v5
练习 286,287页习题定理 7-2.5 在有向图 G=<V,E>中，它的每一个结点位于且只位于一个强分图中。
证明思路：
1)先证,每一个结点 必 位于一个强分图中。
2)再证,每一个结点 只 位于一个强分图中。
