最新图论课件第三章图的连通性教学讲义ppt课件.ppt

《最新图论课件第三章图的连通性教学讲义ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论课件第三章图的连通性第三章图的连通性主要内容一、割边、割点和块二、图的连通度与敏格尔定理三、图的宽直径简介教学时数安排6学时讲授本章内容图的连通性刻画2本次课主要内容(一)、割边及其性质(二)、割点及其性质(三)、块及其性质割边、割点和块3“充分性”如果e不是G的割边，则G-e连通，于是在G-e中存在一条u---v路，显然：该路并上边e得到G中一个包含边e的圈，矛盾。推论1e为连通图G的一条边，如果e含于G的某圈中，则G-e连通。证明：若不然，G-e不连通，于是e是割边。由定理1，e不在G的任意圈中，矛盾！例1求证:(1)若G的每个顶点的度数均为偶数，则G没有割边;(2)若G为

2、k正则二部图(k≧2)，则G无割边。证明:(1)若不然，设e=uv为G的割边。则G-e的含有顶点u的那个分支中点u的度数为奇，而其余点的度数为偶数，与握手定理推论相矛盾！7(2)若不然，设e=uv为G的割边。取G-e的其中一个分支G1,显然，G1中只有一个顶点的度数是k-1,其余点的度数为k。并且G1仍然为偶图。假若G1的两个顶点子集包含的顶点数分别为m与n，并且包含m个顶点的顶点子集包含度为k-1的那个点，那么有：km-1=kn。但是因k≧2，所以等式不能成立！注：该题可以直接证明G中任何一条边均在某一圈中，由定理1得出结论。边割集简介边割集跟回路、树等概念一样，是图论中重要概念

3、。在应用上，它是电路网络图论的基本概念之一。所以，下面作简单介绍。8定义2一个具有n个顶点的连通图G,定义n-1为该连通图的秩；具有p个分支的图的秩定义为n-p。记为R(G)。(1)R(G-S)=n-2;定义3设S是连通图G的一个边子集，如果：(2)对S的任一真子集S1,有R(G-S1)=n-2。称S为G的一个边割集，简称G的一个边割。例2边子集：S1=｛a,c,e｝,S2=｛a,b,｝,S3=｛f｝是否是下图G的边割？agedcbhfi图G9解:S1不是；S2与S3是。定义4在G中，与顶点v关联的边的集合，称为v的关联集，记为：S(v)。agedcbhfi图G例3关联集是割集吗？

4、为什么？答：不一定！如在下图中，关联集｛a,c,e｝是割集，但是，关联集｛d,e,f｝不是割集。10定义5在G中，如果V=V1∪V2,V1∩V2=Φ,E1是G中端点分属于V1与V2的G的边子集，称E1是G的一个断集。agedcbhfi图G在上图G中：｛d,e｝,｛f｝,｛e,d,f｝等都是G的断集。一个图若按断集S来画，形式为：S11注：割集、关联集是断集，但逆不一定。断集和关联集之间的关系为：定理2任意一个断集均是若干关联集的环和。定理3连通图G的断集的集合作成子图空间的一个子空间，其维数为n-1。该空间称为图的断集空间。(其基为n-1个线性无关的关联集)例4求出下图G的所有断集

5、。edcbaf123412解：容易知道：S(1),S(2),S(3)是线性无关断集。cba1234S(1)daf123S(2)ecf1234S(3)dcbf1234ebaf123413edca1234edb1234上图形成的断集空间为：定义6设G是连通图，T是G的一棵生成树。如果G的一个割集S恰好包含T的一条树枝，称S是G的对于T的一个基本割集。14例如：在图G中fedcba图GG的相对于T的基本割集为：｛a,e｝,｛f,c｝,｛f,b,e｝,｛d｝.关于基本割集，有如下重要结论：定理4连通图G的断集均可表为G的对应于某生成树T的基本割集的环和。15定理5连通图G对应于某生成树T的

6、基本割集的个数为n-1,它们作成断集空间的一组基。注：到目前为止，我们在子图空间基础上，先后引进了图的回路空间和断集空间，它们都是子图空间的子空间，这些概念，均是网路图论的基本概念，当然也是代数图论的基本概念。(二)、割点及其性质定义7在G中，如果E(G)可以划分为两个非空子集E1与E2,使G[E1]和G[E2]以点v为公共顶点，称v为G的一个割点。16在图G1中，点v1,v2均是割点；在G2中，v5是割点。v1v2v3v4e3e1e2e4e5e6图G1v1v3v2v4v5图G2定理6G无环且非平凡，则v是G的割点，当且仅当证明：“必要性”设v是G的割点。则E(G)可划分为两个非空

7、边子集E1与E2,使G[E1],G[E2]恰好以v为公共点。由于G没有环，所17以，G[E1],G[E2]分别至少包含异于v的G的点，这样，G-v的分支数比G的分支数至少多1，所以：“充分性”由割点定义结论显然。定理7v是树T的顶点，则v是割点，当且仅当v是树的分支点。证明：“必要性”若不然，有deg(v)=1,即v是树叶，显然不能是割点。“充分性”设v是分支点，则deg(v)>1.于是设x与y是v的邻点，由树的性质，只有唯一路连接x与y，所以G-v分离x与y.即v为