离散数学第7章图论2路与连通

1、1返回 结束第七章 图论-1引言引言7.1 图的基本概念图的基本概念7.2 路与连通7.3 图的矩阵表示图的矩阵表示2返回 结束7.2 路与连通 内容：内容：图的通路，回路，连通性。 重点：重点：1、通路，回路，简单通路，回路,初级通路，回路的定义2、图的连通性的概念3、短程线，距离的概念。3返回 结束7.2.1 路1、路路 (回路回路)中顶点和边的交替序列g0 1 1 2llv e v ee v ，其中1(,)iiievv(无向图)，或1,iiievv(有向图)，始点始点，0v终点终点，称为到lv0vlv的路路。当0lvv时， 为回路回路。1v2v3v4v5v1e2e3e4e5e6eg1 1

2、253443562v e v e v e v e v e v125344352v e v e v e v e v4返回 结束7.2.1 路2.简单通路、简单回路 边不同简单通路简单通路 ( (迹迹) )：路中所有的边都不同：路中所有的边都不同简单回路简单回路 ( (闭迹闭迹) )：回路中所有的边都不同：回路中所有的边都不同复杂通路复杂通路 ( (回路回路) )：路（回路）中有重复的边出现：路（回路）中有重复的边出现5返回 结束7.2.1 路3.初级通路、初级回路 初级（基本）通路，初级回路：点不同初级通路初级通路 ( (路径路径) )：路中所有的顶点互不相同：路中所有的顶点互不相同初级回路初级

3、回路 ( (圈圈) )：回路中所有的顶点互不相同：回路中所有的顶点互不相同初级通路 (回路)简单通路 (回路)，但反之不真。4、路，回路的长度中边的数目。6返回 结束7.2.1 路例例1、(1)例例1 1、(1)图(1)中，从的路有：到1v6v11 1 2 5 5 76v e v e v e v 21 1 22 3 3 442 5 5 76v e v e v e v e v e v e v 31 1 2 5 5 6442 5 5 76v e v e v e v e v e v e v 长度3长度6长度67返回 结束7.2.1 路例例1、(1)图(1)中，从的通路有：到1v6v11 1 2 5

4、5 76v e v e v e v 21 1 22 3 3 442 5 5 76v e v e v e v e v e v e v 31 1 2 5 5 6442 5 5 76v e v e v e v e v e v e v 初级通路简单通路复杂通路8返回 结束7.2.1 路例例1、(2)1244 3 3 22v e v e v e v 22 5 5 64 3 3 22v e v e v e v e v 3243243256325432vvvvvvveeeveeee 长度3长度4长度7图(2)中过)有：的回路 (从2v2v到2v9返回 结束7.2.1 路例例1、(2)1244 3 3 22v

5、 e v e v e v 22 5 5 64 3 3 22v e v e v e v e v 3244 3 3 22 5 5 64 3 3 22v e v e v e v e v e v e v e v 初级回路(圈)初级回路(圈)复杂回路图(2)中过)有：的回路 (从2v2v到2v10返回 结束7.2.1 路5、图中最短的回路如图： 无向图中，环构成的回路长为1 ，两平行边构成的回路长为2。 有向图中，环构成的回路长为1，两条方向相反的边构成的回路长为2。11返回 结束7.2.1 路6、性质定理：定理：阶图中，若从顶点nivjv到存在路()ijvv，则从ivjv到存在长度小于等于在一个的路。

6、1n推论：推论：阶图中，若从顶点nivjv到存在通路()ijvv，则从ivjv到存在长度小于等于在一个的初级通路。1n证明思路：多于证明思路：多于n-1条边的路中必有重复出现的结点，反条边的路中必有重复出现的结点，反复删去夹在两个重复结点之间的边之后，剩余的边数不会复删去夹在两个重复结点之间的边之后，剩余的边数不会超过超过n-1条边条边。 12返回 结束7.2.1 路6、性质定理：定理：阶图中，若niv到自身存在回路，则从到自身存在长度小于等于ivn的回路。在一个推论：推论：阶图中，若niv到自身存在一个简单回路，则从 到自身存在长度小于等于ivn的初级回路。在一个由以上定理可知，在阶图中，n

7、任何一条初级通路的长度任何一条初级回路的长度1nn13返回 结束7.2.2 图的连通性7.2.2 图的连通性1、连通，可达。无向图中，从 到存在路，称ivjv到ivjv是 连通的连通的( (双向双向) )。有向图中，从 到存在路，称ivjv可达可达ivjv(注意方向)。2、短程线，距离。短程线连通或可达的两点间长度最短的 路。距离短程线的长度，记,ijd v v( ,)ijd v v无向图有向图14返回 结束7.2.2 图的连通性2、短程线，距离若之间无路(或不可达)，规定,ijv v( ,),ijijd v vd v v 距离满足：,ijd v v(1)，时，等号成立。 ,0ijd v vi

8、jvv(2),ijjkikd v vd v vd v v若是无向图，还具有对称性，( ,)(,)ijjid v vd v v。15返回 结束7.2.2 图的连通性3、无向图的连通。为连通图为连通图是平凡图，或都是连通的。ggg中任两点为非连通图为非连通图g中至少有两点不连通。g例 1g3g2g1v2v3v4v4u1u2u3u 这里 是连通图， 是非连通图，仅有一个顶点的图 我们也把它看成是连通图。 1g2g3g16返回 结束7.2.2 图的连通性3、无向图的连通2g1v2v3v4v4u1u2u3u1v2v3v4v4u1u2u3u 连通图可以看成是只有一个连通分支的图，即 。( )1w g 结点

9、之间的连通性是结点集结点之间的连通性是结点集v上的等价关系，对应该等价关系，上的等价关系，对应该等价关系，必可将作出一个划分，把必可将作出一个划分，把v分成非空子集分成非空子集v1, v2, , vm,使得两个结使得两个结点点vj和和vk是连通的，当且仅当它们属于同一个是连通的，当且仅当它们属于同一个vi 。把子图把子图g(v1) , g(v2) , , g(vm)称为图称为图g的的连通分支连通分支（connected components）,图图g的连通分支数记为的连通分支数记为w(g) 。如上例中图。如上例中图 的连通分支个数就是的连通分支个数就是217返回 结束7.2.2 图的连通性4、

10、有向图的连通g中任一对顶点都互相可达 (双向)中任一对顶点至少一向可达略去 中有向边的方向后 得到的无向图连通连通强连通单向连通弱连通强连通单向连通弱连通强连通单向连通gg18返回 结束7.2.2 图的连通性例例2单向连通弱连通非连通图19返回 结束7.2.2 图的连通性5 图与顶点之间的若干关系图与顶点之间的若干关系 把度数为把度数为1的顶点称为的顶点称为（ pendant nodes）各顶点的度均相同的图称为各顶点的度均相同的图称为regular graph),各顶点度均为各顶点度均为k的正则图称为的正则图称为。结点结点v，即是把即是把v以及以及与与v关联的边都删除。关联的边都删除。：，即

11、是把该边删，即是把该边删除。除。 见见p-282页的图页的图7-2.2和图和图7-2.3。20返回 结束7.2.3 图的连通度定义定义7-2.4 图图g =是连通图是连通图,若有结点集若有结点集v1 v,使图使图 g中中v1v1连通连通图图,则称则称v1是是g的一个的一个点割集点割集(cut-set of nodes) 。k(g)=min|v1| 是是g的点割集的点割集 称为图称为图g的的点连通度点连通度(node-connectivity) 。v5v1v2v4v5v1v4点割集点割集v1=v221返回 结束7.2.3 图的连通度定义定义7-2.5 图图g =是连通图是连通图,若有边集若有边集

12、e1 e，使图使图 g中中e1e1连连通图，则称通图，则称e1是是g的一个边割集的一个边割集(cut-set of edges) 。若若某一条边就构成一个边割集，则称该边为割边或桥。某一条边就构成一个边割集，则称该边为割边或桥。 割边割边e使图使图g满足满足w(g-e)w(g) 。连通度连通度(edge-connectivity) (g)定义定义：非平凡图的：非平凡图的边连通度为边连通度为 (g)=min |e1| | e1是是g的边割集的边割集 边连通度边连通度 (g)是为了产生一个不连通图需要删去的边是为了产生一个不连通图需要删去的边的最少数目。对平凡图的最少数目。对平凡图g可以定义可以定

13、义 (g)=0，一个不连通一个不连通图也有图也有 (g)=022返回 结束7.2.4 二分图v例：人员分配问题，某公司分配 个工人做 件工作。代表人的一组顶点用 表示，代表工作的一组顶点 用表示 。 与 相邻当且仅当工人 能做工作 ，从而 之间(y 之间)无边。所得图称为二分图 。nmnxxxx,2112,myy yyxjyixixjy 一、一、 二分图定义二分图定义 定义定义1： 的二分划 ，即使 的每条边的两个端点一个在 中，另一个在 中。则称 是二分图或偶图， 称为 的二分划，记为 。vyxyxgvyx,),(gyx ,g);,(eyxg xyyx ,g23返回 结束7.2.4 二分图我

14、们可以验证下面三条成立yx和)(gvxyxgygg (1) 是的一个划分； (2) 和； (3)和均为空图。由以上三条可知，为二分图。24返回 结束7.2.4 二分图123 ,xv v v123, ,yu u u1v2v3v1u2u3u图 是二分图当且仅当存在顶点集合的二分划 ，使 为空图； 当且仅当 不含长为奇数的回路； 当且仅当 的所有非平凡子图是二分图。 gyx ,ygxggg例： 1v2v3v1u2u3u 的一个回路为若 ，则 类似有所以而 ，故 是偶数。g34,ux uy1ux212,llux uykuy122u ueuy121kcu uu uk利用第二个等价刻画即可。25返回 结束7.2.4 二分图定理定理7.2.1 非平凡图 是二分图当且仅当 中不含长为奇数的回路。gg证明证明必要性是明显的。充分性充分性：不妨设g中每一对顶点之间有路连接（否则只需考虑g的每个每一对顶点之间有路连接的极大子图）。任取g的一个顶点u，由g的假设，对g的每个顶点v，在g中存在u-v路。现利用u对g的顶点进行分类。设v1v|vv(g),g中存在一条长度为偶数的u-v路v2v|vv(g),g中存在一条长度为奇数的u-v路显然uv