离散件9-图的道路与连通ppt课件.ppt

《离散件9-图的道路与连通ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二节图的道路与连通一、无向图的道路1。定义：图G中由结点和边交替构成的序列p=v0e1v1e2v2...ekvk称为由v0到vk的一条道路，其中每条ei和vi-1及vi关联。v0称为道路p的起点，vk称为道路p的终点。p中的边数k称为道路的长度。只由一个结点构成的道路称为零道路。例：下图中p1=v1e1v1e2v2e2v1e5v4e8v3e6v2p2=v1e2v2e6v3e8v4e5v1e4v3e9v5p3=v1e5v4e8v3e6v2（简记为：p3=v1v4v3v2）p4=v6都是道路。v1v2v3v4v6v

2、5e9e10e12e8e7e2e4e5e6e3e1e112。道路的分类：①迹：任何满足道路定义的道路。②简单道路：边不重复出现的道路。③基本道路：结点不重复出现的道路。例：上图中，p1是迹，p2是简单道路，p3是基本道路，p4是零道路。3。回路：起点和终点相同的道路。边不重复出现的回路称为简单回路。结点不重复出现的回路称为圈。例：下图中，c1是一般回路，c2是简单回路，c3是圈。例：下图中c1=v1e1v1e2v2e7v4e8v3e4v1e3v2e2v1c2=v1e1v1e2v2e3v1e5v4e8v3e4v1c

3、3=v1e5v4e10v6e12v5e9v3e4v1（c3可简记为：c3=v1v4v6v5v3v1）都是回路。c1是一般回路，c2是简单回路，c3是圈。v1v2v3v4v6v5e9e10e12e8e7e2e4e5e6e3e1e114。定理：设G是n阶图，如果存在从结点u到v的道路，则必存在长度不超过n-1的道路。证明要点：如果结点u到v的道路p的长度超过n-1，则p中至少有n+1个结点，因而道路中至少有一个结点出现两次，如viei...v1，则去掉ei...vi后仍是结点u到v的道路，但是道路长度至少短1。重复这

4、一过程，即得所需结论。二、无向图的连通问题1。定义:如果存在从结点u到结点v的道路，则称u到v是连通的。结点集V上的“连通”关系具有性质：自反、对称、传递。2。如果图G中任何两个结点都是连通的，则称G是连通图。3。图G中的极大连通子图称为图G的支，图G的支数记为(G)。图G连通当且仅当(G)=1。例：下图中(G)=3。v1v6v4v7v5v2v3v84。连通图G=(V,E)的点割集定义：设SV，如果(G-S)>1，则称S是G的一个点割集。①S是G的一个点割集，而S的任何真子集都不是点割集时，称S是G的一

5、个基本点割集。如S1={v2，v5}，S2={v2，v6},S3={v2，v7}，S4={v3，v5},S5={v4}②由单个结点（如u）构成的点割集简称为割点。v1v6v4v7v5v2v3定理结点u是图G的割点当且仅当存在两结点v和w，使v到w的任何道路都经过u。证明要点：“”,当u是割点时，则Gu至少有2支，从这2支中各选一个结点即可。“”,反之，如果v到w的任何道路都经过u，则去掉u后，v和w各在Gu的1支中，即u是割点。5。连通图G=(V,E)的边割集定义：设FE，如果(G-F)>1，则称F是

6、G的一个边割集。①F是G的一个边割集，而F的任何真子集都不是边割集时，称F是G的一个基本边割集。如F1={v2v3，v3v7}，F2={v2v3，v5v7},F3={v1v4}，F4={v2v4，v2v6，v5v6},F5={v4v6，v2v6，v2v5，v3v7}②由单条边（如uv）构成的边割集简称为割边。v1v6v4v5v2v3v7定理边e是图G的割边当且仅当e不在G的任何回路上。证明要点：“”:当e是割边时，则Ge有2支，因而e不在G的任何回路上。“”:反之，如果e不在任何回路上，则去掉e后，e关联的

7、两个结点各在Ge的1支中，即e是割边。6.图的连通度(限无环图G)(1)点连通度:记为К(G),定义为最小基本点割集基数,当GKnК(G)n1,当GKn例如下图中,К(G)2v1v6v4v5v2v3v7v8(2)边连通度:记为λ(G),定义为最小基本边割集基数,当GK1λ(G)0,当GK1例如下图中,К(G)2,λ(G)2v1v6v4v5v2v3v7v8练习:求下列图的К(G),λ(G),和К(G)=2λ(G)=2=2К(G)=2λ(G)=2=2К(G)=2λ(G)=3=4(3)连通

8、度定理:К(G)λ(G)证明要点:首先,每个结点关联的边构成一个边割集,于是λ(G).下面证明К(G)λ(G)：首先注意对每个基本边割集F，(G-F)=2；其次设F含λ(G)条边，G-F的2支为G1和G2，若G不是二部图，则去掉这支中与F关联的全部结点即可；若G是二部图，则交替删去这2支中与F关联的结点即可。四、有向图的道路1。定义：如果图G中由结点和边交替