7-2路与回路 在现实世界中,常常要考虑这样的问题:如 何从一个图中的给定结点出发,沿着一些边连续 移动而达到另一指定结点,这种依次由点和边组 成的序列,就形成了路的概念
7-2 路与回路 在现实世界中，常常要考虑这样的问题：如 何从一个图中的给定结点出发，沿着一些边连续 移动而达到另一指定结点，这种依次由点和边组 成的序列，就形成了路的概念
学习本节要熟悉如下术语(22个 路、路的长度、回路、迹、通路、圈、 连通、连通分支、连通图、点割集 割 点连通度、边割集、割边、边连通度、可达、 单侧连通、强连通、弱连通、强分图、弱分图 单侧分图 掌握5个定理,一个推论
学习本节要熟悉如下术语(22个)： 路、 路的长度、 回路、 迹、 通路、 圈、 连通、 连通分支、 连通图、 点割集、 割点、 点连通度、 边割集、 割边、 边连通度、 可达、 单侧连通、 强连通、 弱连通、 强分图、 弱分图、 单侧分图 掌握5个定理，一个推论
路 定义7-21给定图G=,设vny1,…,n∈V,e1,…,en∈E,其 中e是关联于结点vy的边,交替序列vev1e2envn称为结点vo 到vn的路(拟路径 Pseudo path)。 v0和v分别称为路的起点和终点, 边的数目n称作路的长度。 当v=vn时,这条路称作回路(闭路径 closed walk)。 若一条路中所有的边e1,…,en均不相同称作迹(路径wk)。 若一条路中所有的结点v,V1…,vn均不相同,称作通路 (Path) 闭的通路,即除v=Vn之外,其余结点均不相同的路,称作圈 (回路 circuit)。 见图7-21中路的例子
一、路 定义7-2.1 给定图G=,设 v0 ,v1 ,…,vnV， e1 ,…,enE, 其 中ei是关联于结点vi-1 ,vi的边，交替序列v0e1v1e2…envn称为结点v0 到vn的路（拟路径Pseudo path） 。 v0和vn分别称为路的起点和终点， 边的数目n称作路的长度。 当v0=vn时，这条路称作回路（闭路径closed walk） 。 若一条路中所有的边e1 , …, en均不相同,称作迹（路径walk） 。 若一条路中所有的结点v0 , v1 ,…, vn均不相同,称作通路 （Path） 。 闭的通路,即除v0=vn之外，其余结点均不相同的路，称作圈 （回路circuit） 。 见图7-2.1中路的例子
例如 e? 2 e斗 e占 80v5 路迹 g V1e2v3e3V2e3V3e4v2eV5e7V3 V5e8v4e5V2e6V5e7V3e4V2 通路:4eV5e6V2ev1e2V3 圈:v2e1v1e23erv5e6v2
例如 路：v1e2v3e3v2e3v3e4v2e6v5e7v3 迹：v5e8v4e5v2e6v5e7v3e4v2 通路：v4e8v5e6v2e1v1e2v3 圈：v2e1v1e2v3e7v5e6v2
在简单图中一条路voev1e2,enVn,由它的 结点序列v,Ⅵ1,∴,V确定,所以简单图的路, 可由其结点序列表示。在有向图中,结点数大于 的一条路亦可由边序列e1e2en表示
在简单图中一条路v0e1v1e2…envn，由它的 结点序列v0，v1，…，vn确定，所以简单图的路， 可由其结点序列表示。在有向图中，结点数大于 一的—条路亦可由边序列e1e2…en表示
定理7-2.1在一个具有n个结点的图中,如果从结 点v到结点v存在一条路,则从结点v到结点v必存在 条不多于n-1条边的路。 口证明思路:多于n-1条边的路中必有重复出现的结 点,反复删去夹在两个重复结点之间的边之后,剩余 的边数不会超过n-1条边 定理7-2.1的推论在一个具有n个结点的图中, 如果从结点v到结点v存在一条路,则从结点v到结点 v必存在一条边数小于n的通路
定理7-2.1 在一个具有n个结点的图中，如果从结 点vj到结点vk存在一条路，则从结点vj到结点vk必存在 一条不多于n-1条边的路。 证明思路：多于n-1条边的路中必有重复出现的结 点，反复删去夹在两个重复结点之间的边之后，剩余 的边数不会超过n-1条边。 定理7-2.1的推论 在一个具有n个结点的图中， 如果从结点vj到结点vk存在一条路，则从结点vj到结点 vk必存在一条边数小于n的通路
定理721的证明 如果从结点v到vk存在一条路,该路上的结 点序列是vy1Yk,如果在这条中有条边,则 序列中必有|+1个结点,若>n-1,则必有结点vs, 它在序列中不止出现一次,即必有结点序列 sys.vk,在路中去掉从vs到vs的这些边, 仍是v到vk的一条路,但此路比原来的路边数要 少,如此重复进行下去,必可得到一条从v到vk 的不多于n-1条边的路
定理7-2.1的证明 如果从结点vj到vk存在一条路，该路上的结 点序列是vj…vi…vk，如果在这条中有l条边，则 序列中必有 l+1个结点，若l>n-1，则必有结点vs， 它在序列中不止出现一次，即必有结点序列 vj…vs…vs…vk，在路中去掉从vs到vs的这些边， 仍是vj到vk的一条路，但此路比原来的路边数要 少，如此重复进行下去，必可得到一条从vj到vk 的不多于n-1条边的路
2 e 2 e31e2 2 20 2 eA eA e5 e了 e5 el e5 e/ 60v5 如在图721中有5个结点。v1到v3的一条路为: V1e2vRe3v2e3v3eav2ekVse7V 73 此路中有6条边,去掉e3有路 23e4v2e65e 有4条边。 v1到v3最短的路为v1e2V3
如在图7-2.1中有5个结点。 v1到v3的一条路为： v1e2v3e3v2e3v3e4v2e6v5e7v3 此路中有6条边，去掉e3有路 v1e2v3e4v2e6v5e7v3 有4条边。 v1到v3最短的路为v1e2v3
无向图的连通性 1、连通 定义7-2.2在无向图G中,如果从结点u和结点v 之间若存在一条路,则称结点u和结点v是连通的 (connected) 结点之间的连通性是结点集V上的等价关系,对 应该等价关系,必可将作出一个划分,把Ⅴ分成非空 子集V,V2,…,Vm,使得两个结点v和v是连通的,当 且仅当它们属于同一个V。把子图G(V1),G(V2),…, G(Vn)称为图G的连通分支( connected components), 图G的连通分支数记为w(G)。 见281页图7-22
二、无向图的连通性： 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)
a 图722