离散数学第八章-(第2讲)课件.ppt

1、8.2 路与图的连通性路与图的连通性1、路的定义、路的定义：在图：在图G=中，设中，设v0，v1，vnV,e1,e2 en E，其中其中ei是关联于结点是关联于结点vi-1,vi的边，结的边，结点与边的交替序列点与边的交替序列v0 e1 v1 en vn称为联结称为联结v0到到vn的的路路。v1v4v5v2v3e1e2e3e4e5e6e7e8v1v4v5v2v3e1e2e3e4e5e6e7e8v0v3v4v1v2e1e2e3e4e5e6e7e8路的其它概念路的其它概念（1）在路）在路 v0 e1 v1 en vn 中，中，v0和和vn分别称作分别称作路的起点与终点路的起点与终点。（2）一条路中

2、所有的边的数目称作）一条路中所有的边的数目称作路的长度路的长度。（3）一条路中所有的边均不相同，则此路称作）一条路中所有的边均不相同，则此路称作迹迹。（4）一条路中所有的结点均不相同，则此路称作）一条路中所有的结点均不相同，则此路称作通路通路。显然：通路必为迹，而迹不一定是通路。显然：通路必为迹，而迹不一定是通路。v0v3v4v1v2e1e2e3e4e5e6e7e8路的其它概念路的其它概念（5）在路）在路 v0 e1 v1 en vn 中中，若若v0=vn 则路称作则路称作回路回路。（6）除）除v0=vn 外，其余结点和所有边均不相同的回路，称作外，其余结点和所有边均不相同的回路，称作圈圈 (

3、基本回路基本回路)。（7）所有边均不相同的回路，称作所有边均不相同的回路，称作简单回路简单回路。显然：基本回路必为简单回路，反之，则不然。显然：基本回路必为简单回路，反之，则不然。v0v3v4v1v2e1e2e3e4e5e6e7e8路的表示方法：路的表示方法：(a)结点表示法：结点表示法：(b)边表示法：边表示法：例：给出有向图，求起始于，终止于例：给出有向图，求起始于，终止于4的路。的路。),(21kvvv),(21keee在下图中，ADEBCF；ADEBCEF这两条路，哪个是通路，哪个是迹？练习：练习：ABCDEF在下图中，求v1到v4长度分别为1，2，3的路分别有哪些？练习：1v2v3v

4、4v解：v1到v4长度分别为1和2的路：没有。v1到v4长度为3的路一条：v1 v2 v3 v4。n定理定理1：在一个在一个 n 阶图中，如果从结点阶图中，如果从结点u到结点到结点v存在存在一条路，则从从结点一条路，则从从结点u到结点到结点v必存在一条长度小于等必存在一条长度小于等于于 n-1条边的通路。条边的通路。定理定理2：在一个在一个 n 阶图中，若存在阶图中，若存在v到自身的简单回路，到自身的简单回路，则必存在则必存在v到自身长度小于等于到自身长度小于等于n的基本回路。的基本回路。1v2v3v4v 无向图的结点连通性无向图的结点连通性 定义：设图为无向图，且定义：设图为无向图，且 u

5、u ,vV,vV ，若从，若从u u到到v v存在任存在任何一条路径何一条路径 ，则称，则称u u到到v v是连通的。是连通的。有向图的结点可达性有向图的结点可达性 定义：设图为简单有向图，且定义：设图为简单有向图，且u u ,vVvV,若从若从u u到到v v存在任存在任何一条路径，则称何一条路径，则称u u到到v v是可达的。是可达的。图的连通性：图的连通性：（1）连通性与非连通性：连通性与非连通性：若无向图若无向图G是平凡图，或是平凡图，或G中任意两结点间都是连通的，中任意两结点间都是连通的，则称图则称图G是连通图，否则称是连通图，否则称G是是非连通图。是是非连通图。一个有向图，忽略边的

6、方向后得到的无向图若是连通一个有向图，忽略边的方向后得到的无向图若是连通的，则称该有向图为连通图，否则称非连通图。的，则称该有向图为连通图，否则称非连通图。（a）abcd（b）abcd 练习：已知关于人员练习：已知关于人员A,B,C,D,E的下述事实：的下述事实：A说英语；说英语；B说英语和西班牙语；说英语和西班牙语；C说英语，意大利语和俄语；说英语，意大利语和俄语；D说日语和西班牙语；说日语和西班牙语；E说法语，日语和俄语。说法语，日语和俄语。试问，上述五个人中是否任意两人都能交谈。试问，上述五个人中是否任意两人都能交谈。（如果必要，可由其余（如果必要，可由其余3人所组成的译员链帮忙）人所组

7、成的译员链帮忙）（2）连通分支连通分支 若无向图若无向图G的每个子图都是连通图，称为的每个子图都是连通图，称为G的连通分支。的连通分支。G的分支数记作的分支数记作p(G)。（3）强连通，单向连通，弱连通强连通，单向连通，弱连通 简单有向图简单有向图G：如果如果G的任何两结点间均是互相可达的，则称图的任何两结点间均是互相可达的，则称图G是是强连通强连通的。的。如果如果G的任何两结点间至少有一个结点到另一结点是可达的。则的任何两结点间至少有一个结点到另一结点是可达的。则称称G是是单向连通单向连通的。的。如果忽略边的方向，将它看成无向图后，图是连通的，则称该图如果忽略边的方向，将它看成无向图后，图是

8、连通的，则称该图为为弱连通弱连通的。的。若若G是强连通的，则是强连通的，则G是单向连通的。若是单向连通的。若G是单向连通的，则是单向连通的，则G是是弱连通的。弱连通的。反之，不成立。反之，不成立。(b)ABC(c)ABCABC(a)练习：下列各有向图是强连通图的是（）.定理定理：一个有向图是强连通的充要条件是：它包含：一个有向图是强连通的充要条件是：它包含一个回路，该回路至少包含每个结点一次。一个回路，该回路至少包含每个结点一次。ABCD定义：设，为一简单有向图，且定义：设，为一简单有向图，且是是的子图。的子图。具有强连通性质的极大子图具有强连通性质的极大子图称为强分图；称为强分图；具有单侧连

9、通性质的极大子图具有单侧连通性质的极大子图称为单侧图；称为单侧图；具有弱连通性质的极大子图具有弱连通性质的极大子图称为弱分图。称为弱分图。例：G的强分图为：1,2,3，4，5，6G的单侧图为：1,2,3,4,5，5,6G的弱分图为：1,2,3,4,5,6 定理：在任一简单有向图，中，有向定理：在任一简单有向图，中，有向 图的每一个结点位于且只位于一个强分图之中。图的每一个结点位于且只位于一个强分图之中。14235定义定义 设无向图设无向图G=是连通无向图是连通无向图,V1 V,若若G V1 不不连通或是平凡图连通或是平凡图,而对于而对于V1的任何一个非空真子集的任何一个非空真子集V2，G V2

10、 是连通的，则称是连通的，则称V1 是是G的点割集。的点割集。在下图中在下图中,v2,v4,v3 和和 v5 都是点割集都是点割集,v3和和v5都是割点。都是割点。若某一个结点构成一个点割集，则称该结点为割点。若某一个结点构成一个点割集，则称该结点为割点。练习：练习：设图设图G=的结点集为的结点集为V=v1,v2,v3,边集为边集为E=,则则G的割点是的割点是()A.v1 B.v2 C.v3 D.v2,v3 定义：定义：设设G为无向连通图且为非完全图为无向连通图且为非完全图,则称则称 (G)=min|V1|V1 为为G的点割集的点割集 为为G的点连通度的点连通度,简称连通度。简称连通度。(G)

11、简记为简记为 。完全图完全图Kn(n 1)的点连通度为的点连通度为n-1；规定非连通图和；规定非连通图和平凡图的点连通度为平凡图的点连通度为0；定义定义 设无向图设无向图G=是连通无向图是连通无向图,E1 E,若若G E1 不不连通，而对于连通，而对于E1的任何一个非空真子集的任何一个非空真子集E2，G E2 是连通的，是连通的，则称则称E1 是是G的边割集。的边割集。在下图中在下图中,e5,e6,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4 都是边割集都是边割集,其中其中e5和和e6是桥。是桥。若某一条边构成一个边割集，则称该条边为割边或桥。若某一条边构成一个边割集

12、，则称该条边为割边或桥。定义定义 设设G为无向连通图且为非平凡图为无向连通图且为非平凡图,则称则称(G)=min|E1|E1 为为G的边割集的边割集 为为G的边连通度。的边连通度。规定规定:非连通图和平凡图的边连通度为非连通图和平凡图的边连通度为(G)=0；完全；完全图图Kn(n 1)的边连通度的边连通度(Kn)=n-1.练习：下图的点连通度为 ，边连通度为_.练习：练习：分别求出分别求出n阶完全无向图阶完全无向图Kn的点连通度和边连通度。的点连通度和边连通度。解解：1)(nKn1)(nKN定理：定理：对于任何无向图对于任何无向图G,有有:(G)(G)(G)。例例 (1)给出一些无向简单图给出一些无向简单图,使得使得:=；无向完全图无向完全图Kn和零图和零图Nn都满足要求。都满足要求。(a)(b)(2)给出一些无向简单图给出一些无向简单图,使得使得:在两个在两个Kn(n 4)之间放置一个顶点之间放置一个顶点v,使使v与两个与两个Kn中任中任意两个不同的顶点相邻意两个不同的顶点相邻,所得简单图满足要求。所得简单图满足要求。(a)(b)