7-2路与回路 在现实世界中,常常要考虑这样的问题:如 何从一个图中的给定结点出发,沿着一些边连续 移动而达到另一指定结点,这种依次由点和边组 成的序列,就形成了路的概念
7-2 路与回路 在现实世界中，常常要考虑这样的问题：如 何从一个图中的给定结点出发，沿着一些边连续 移动而达到另一指定结点，这种依次由点和边组 成的序列，就形成了路的概念
学习本节要熟悉如下术语(22个 路、路的长度、回路、迹、通路、圈、 连通、连通分支、连通图、点割集 割 点连通度、边割集、割边、边连通度、可达、 单侧连通、强连通、弱连通、强分图、弱分图 单侧分图 掌握5个定理,一个推论
学习本节要熟悉如下术语(22个)： 路、 路的长度、 回路、 迹、 通路、 圈、 连通、 连通分支、 连通图、 点割集、 割点、 点连通度、 边割集、 割边、 边连通度、 可达、 单侧连通、 强连通、 弱连通、 强分图、 弱分图、 单侧分图 掌握5个定理，一个推论
路 定义7-21给定图G=<V,E>,设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=<V,E>,设 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表示