返 回 上一页 下一页
路与回路
重点：1、通路，回路，简单通路，回路，初级通路，回路的定义，
2、图的连通性的概念，
3、短程线，距离的概念。
1、通路
(回路)——
中顶点和边的交替序列
，其中
(无向图)，或
(有向图)，
——始点，
——终点，称
为
到
的通路。当
时，
为回路。
2、简单通路，简单回路。
简单通路
(迹)——通路中所有的边
互不相同。
简单回路
(闭迹)——回路中所有的边互不相同。
复杂通路
(回路)——通路 (回路)中有边重复出现。
3、初级通路，初级回路。
初级通路
(路径)——通路中所有的顶点
互不相同。
初级回路
(圈)——回路中所有的顶点
互不相同。
由定义知：初级通路 (回路)
简单通路 (回路)，但反之不真。
4、通路，回路的长度——中边的数目。
例1、
图(1)中，从
到
的通路有：
长度3
长度6
长度6
…………
其中
为初级通路，
为简单通路，
是复杂通路。
图(2)中过
的回路 (从到)有：
长度3
长度4
长度7
…………
其中，
为初级回路(圈)，为复杂回路。
5、图中最短的回路。
无向图中，环构成的回路长为 
，两平行边构成的回路长为
。
有向图中，环构成的回路长为 ，两条方向相反的边构成的回路长为。
如图：
6、性质。
定理：在一个
阶图中，若从顶点
到
存在通路
，则从到存在长度小于等于
的通路。
推论：在一个阶图中，若从顶点到存在通路，则从到存在长度小于等于的初级通路。
定理：在一个阶图中，若到自身存在回路，则从到自身存在长度小于等于的回路。
推论：在一个阶图中，若到自身存在一个简单回路，则从到自身存在长度小于等于的初级回路。
由以上定理可知，在阶图中，
1、连通，可达。
无向图中，从到存在通路，称到是连通的(双向)。
有向图中，从到存在通路，称可达。(注意方向)
不论无向图，有向图，规定 到自身都是连通或可达的。
2、短程线，距离。
若
之间无通路(或不可达)，规定
距离
满足：
(1)
，
时，等号成立。
(2)
若是无向图，还具有对称性， 
。
3、无向图的连通。
为连通图——
是平凡图，或中任两点都是连通的。
为非连通图——中至少有两点不连通。
设是一个无向图，
是中顶点之间的连通关系，则是等价关系。设将
划分成
个等价类：
，由它们导出的子图
称为的连通分支，其个数记为
。
4、有向图的连通。
强连通单向连通弱连通
例2、
上图中，(1)为强连通，(2)，(3)为单向连通，(4)为弱连通，(5)为非连通图。
返 回 上一页 下一页