返 回 上一页 下一页

 

路与回路

一、通路,回路


二、图的连通性

重点: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)为非连通图。

返 回 上一页 下一页