《(第19讲)图论》由会员分享，可在线阅读，更多相关《(第19讲)图论（31页珍藏版）》请在金锄头文库上搜索。
1、Discrete Mathematics 18.2 图的连通性 一、路径与回路 定义 给定图G=，设v0, v1,v2,vn V， e1,e2,en E， 其中ei 关联与vi-1 和vi (i=1,2,n)，则 G中点和边的交替序列(v0e1v1e2envn)称为从顶点v0到 vn的路径。 v0和vn分别称为此路径的起点和终点，称路径中边的数目称为路径的长度。当v0 = vn时，此路径称为回路。Discrete Mathematics 2v 若路径中的所有边互不相同，则称为简单路径。若回路中的所有边互不相同，称此回路为简单回路。 v若路径的所有顶点互不相同(从而所有边互不相 同)，则称此路径
2、为基本路径。若回路中，除v0 = vn外，其余顶点各不相同，所有边也各不相同，则称此回路为基本回路。v有边重复出现的路径称为复杂路径，有边重复出 现的回路称为复杂回路。Discrete Mathematics 3v 根据以上定义可知：1) 基本路径(回路)是简单路径(回路)，但反之不 成立。2) 一般说来，路径、回路是图的子图。Discrete Mathematics 4(1)为v0到v4的长为4的基本路径。(3)为v0到v8的长为8的简单路径。(5)是v0到v5（= v0 ）的长为5的基本回路。(7)为v0到v8（= v0 ）长为8的简单回路。 Discrete Mathematics 5在
3、有向图的路径或回路中，注意边的方向的一致性 。 基本路径简单路径基本回路简单回路Discrete Mathematics 6解答：在无向图中，环和两条平行边构成的回 路分别为长度为1和2的基本回路。在有向图中，环和两条方向相反边构成的回路 分别为长度为1和2的基本回路。 思考：在无向图中，环或两条平行边构成 什么回路？长度是多少？在有向图中，环 或两条方向相反边构成什么回路？长度又 是多少？ 。 Discrete Mathematics 7二、路径与回路的性质 定理 在一个具有n个顶点的简单图中，如果从顶 点v1到v2存在路径，则从v1到v2存在一条长度小于 等于n-1的基本路径。Discre
4、te Mathematics 8证明：假设从v1到v2存在一条路径:(v1,vi,v2 ).如果其中有相同的顶点vk，如(v1,vi, vk, vk, v2 )，它仍然是从v1到v2的路径。如此反复下去直到(v1,vi,v2 )中没有重复的点为止。此时，所得到的就是一条基本路径，基本路径的长度 的长度比所经过顶点数少1，图中共n个顶点，故基本 路径的长度应该小于等于n-1.则删去从vk到vk的这些边， (v1,vi, vk, v2 )，Discrete Mathematics 9定理 在一个有n个顶点的简单图中，如果存在 一条vi到自身的简单回路，则从vi到自身存在一 条长度小于等于n的基本回
5、路。Discrete Mathematics 10试用有向图描述出以下问题的解法：“过河问题”例 河岸上有狼、羊和白菜，摆渡人要將它们送 到河对岸去。由于船容量小，每次只能载一样东 西，但狼和羊，羊和白菜都不能在无人看管的情 況下留在一起，否则狼会吃了羊，羊会吃光白菜 ，问如何安全地把它们都运过河去？Discrete Mathematics 11分析：人(M)、狼(L)、羊(Y)、菜(C)4种的任意组合共有 16种，其中狼羊菜、羊菜、狼羊三种不允许出现， 所以人、人狼、人菜这三种对应的情形也不会出现 。v剩下的10种情形为：人狼羊菜、人狼羊、人狼菜 、人羊菜、人羊、狼菜、菜、羊、狼、空。v将这
6、10种情形看成点，例如初始状态可记为 ，人和羊过河后的状态可记为，若从状态S1可变到状态S2，则从顶 点S1画一条有向弧到顶点S2。Discrete Mathematics 12v如从初始状态S1：S3：S5： S7：v这样就得到一个有向图，根据题意，只要找出图中所 有从S1到S10的路径就是问题的解。 S2： S4： S6： S10 Discrete Mathematics 13定义 在图G=中，从顶点vi到vj最短路径的长 度叫从vi到vj的距离，记为d(vi,vj)。若从vi到vj不存在路径，则d(vi,vj)=。注意：在有向图中，d(vi,vj)不一定等于d(vj,vi)，但 一般地满
7、足以下性质:(1) d(vi,vj)0;(2) d(vi,vi)=0;(3) d(vi,vj)+d(vj,vk)d(vi,vk)。(三角不等式)Discrete Mathematics 14三、图的连通性 定义 在一给定图G=中，u,v V。若存在u 到v的路径，则称u到v是连通的或称u到v是可达 的。规定：任何顶点与自身是连通的。定义 在一无向定图G中。若G中的任何两个顶点 都是连通的，则称G是连通图，否则称G 是非连 通图。显然，在无向图G中，顶点间的连通关系是等价 关系，因为它具有：自反性；对称性；传 递性。Discrete Mathematics 15则从该等价关系形成V的一个划分，相
8、应的等价 类为V1，Vm，则等价类的类内各点均是连 通的，类间各点都不连通。我们把G的子图G(V1),G(Vm)称为G的连通分 图，并用p(G)来表示G的连通分图的个数。显然，G是连通的 p(G)=1。V1=v1,v2,v3,v4 V2=v5,v6,v7 V3=v8 V4=v9p(G)=4Discrete Mathematics 16定义 在有向图G=中，如果略去G中各边 的方向后所得无向图是连通的，则称G是弱连通图；若G中任意两个顶点间至少一个可达另一个，则 称G是单向连通图；若G中任何一对顶点都可互相到达，则称G是强连通图。Discrete Mathematics 17(1)为强连通图，(
9、2)单向连通图，(3)是弱连通图。有向图中各种连通性之间的关系：一个有向图G是强连通的，它一定是单向连通的；同样，单向连通图也一定是弱连通图。但反 之都不成立。Discrete Mathematics 18有向图连通性的判别方法：判别法1：若一个有向图的底图是连通的，则G是弱连通图。判别法2：若 一个有向图G中存在经过每个顶点 至少一次的回路，则G是强连通图。判别法3：若一个有向图G中存在经过每个顶点至 少一次的路径，则G是单向连通图。 Discrete Mathematics 19定义 在有向图G中，存在一个点的子集 V1V，如果V1导出的子图G是强连通的(单向连 通的、弱连通的)，而对于
10、uVV1，则V1 u导出的子图G不是强连通的(单向连通的、弱 连通的) 。称V1导出的子图G是强分图(单向分图 、弱分图)。 Discrete Mathematics 20图1中，v4,v5，v1，v2导出的子图是强分图；图2中，v1,v2,v3,v5导出的子图是单向分图； 请问：图3中，v1,v2,v5导出的子图是强分图吗？连通性在计算机中的应用：检验“死锁”。Discrete Mathematics 21四、点割集、边割集、连通度 v对于无向连通图来说，常由删除G中的一些顶点或边来破坏其连通性。v在图G=中，删除顶点v是将v及与v相关联 的边都删除。如：V1 V，从G中删除V1是将V1及与
11、V1相关联的边均删除，剩下的子图记为G- V1 。v删除边是将仅将边删除，如E1 E，从G中将E1 删除是仅将边集E1删除，剩下的子图记做G- E1 。Discrete Mathematics 22定义 设在一无向定图G中，若存在顶点集V1 V， 使G删除V1后所得子图G- V1 的连通分支数 p(G -V1 )p(G)，而删除任何V2 V1 ，都有 p(G - V2 )=p(G) ，则称V1为G的一个点割集。只有一个顶点的点割集，则称该点为割点。Discrete Mathematics 23例如，对上图，有p(G)=1，V1=v1,v2，pG-V1=3 对V1的任何子集，如果少删除一点，其连
12、通分支仍 然是1，所以，V1是G的一个点割集。Discrete Mathematics 24例2，同理，在图G1中，v1,v3、v4、v6也是G1的点 割集，而且， v4、v6是割点。而v5,v6不是点割集。Discrete Mathematics 25定义 设在一无向定图G中，若存在边集E1 E，使 得G- E1 的连通分图数 p(G- E1 )p(G)，而删除任 何E2 E1 ，都有 p(G- E2 )=p(G) ，则称E1为G的一个边割集。如边割集中只有一条边，则称该边为割边或桥。Discrete Mathematics 26例如，在下面图G中， e1,e2,e1,e3,e2,e3,e4
13、 e5,e6,e5,e7,e6,e7,e8,e9,e10都是边割集 。其中e4,e10是桥。Discrete Mathematics 27定义 设G为无向连通图，定义0(G)=minv1v1是G的点割集，或使G-V1为平凡图 ，则称0(G)是G的点连通度。由定义可知：若G是平凡图，则v1=，于是0(G)=00(Kn)=n-1若图存在割点，则0(G)=1规定非连通图的连通度0(G)=0Discrete Mathematics 28定义 设G为无向连通图，定义1(G)=minE1E1是G的边割集，则称1(G)为G的边连通度。由此可得，(1)若G是平凡图，则E1=，1(G)=0 (2)若G存在割边，
14、则1(G)= 1 (3)规定非连通图的边连通图1(G)= 0Discrete Mathematics 定理8.23设G是任一(n,m)无向简单图 ,是其连通分图个数,则证 先证n-m。对m作归纳。m=0时,G是零图,=n,命题成立。设m-1时成立,现证明m时也成立。我们从G上删去 一条边得G,G有两种可能:(i)有n个顶点,个分图,m-1条边,根据归纳假设n-m-1,显然在G中成立n-m。(ii) 有n个顶点,+1个分图,m-1条边,根据归纳假设n-(+1)m-1,显然在G中成立n-m。Discrete Mathematics 定理8.24设G无向简单连通图, 则有 (G)(G)(G) 其中， (G) 为G的最小度。 定理8.25设E无向简单连通图G的割 集，则, w(G-E)=2 。 定理8.26无向简单连通图G有一割点v， 当且仅当存在两个顶点u，w，使得u到w的 任何路径都经过v。Discrete Mathematics 定理8.27无向简单连通图G没有割点当且 仅当任意两点u，w同在一条基本路径上。 定理8.28无向简单连通图G=没有割 点当且仅当任意点u和任意边（ w ,v ）同在 一条基本路径上。 定理8.29无向简单连通图G=没有割 点当且仅当任何两边（ u ,v ）,（ w ,x ）同 在一条基本路径上。
