离散数学CH04_图论_路与连通性.ppt

离散数学Discrete Mathematics计算机与信息工程学院第4章 图 论内容提要图的基本概念4.1连通图4.34.4图的矩阵表示路和回路4.2内容提要欧拉图和哈密顿图4.5二部图及匹配4.74.8平面图树4.6n 定义4.2.1 设G=V,E是图，G中的结点与边的交替序列L：v0e1v1e2v2envn叫做v0到vn的路其中vi-1与vi是ei的端点，i=1,n v0和vn分别叫做路L的始点和终点 路L中边的条数叫做该路的长度4.2 路和回路n 例如， L1：v5e8v4e5v2e6v5e7v3 是从v5到v3的路，v5是始点，v3是终点，长度为4 L2：v1e1v2e3v3 是从v1到v3的路，v1是始点， v3是终点，长度为24.2 路和回路在简单图中没有平行边和环，路L:v0e1v1e2v2envn完全由它的结点序列v0v1v2 vn确定所以，在简单图中的路可以用结点序列表示n 定义4.2.2 设G=V,E是图，L是从 v0到vn的路 若v0=vn，则称L为回路 若L中所有边各异，则称L为简单路 若此时又有v0=vn，则称L为简单回路 若L中所有结点各异，则称L为基本路。

若此时又有v0=vn，则称L为基本回路 若L既是简单路，又是基本路，则称L为初级路 若此时又有v0=vn，则称L为初级回路,又称圈 4.2 路和回路4.2 路和回路在图中，L1是一条简单路L2是一条简单路、基本路、初级路 L1：v5e8v4e5v2e6v5e7v3L2：v1e1v2e3v3e1e2e3e4e5e6e7e8v1v2v3v4v5v1e2v3 e3v2 e3v3 e4v2 e6v5 e7v3v5e8v4 e5v2 e6v5 e7v3 e4v2v4e8v5 e6v2 e1v1 e2v3 v2e1v1 e2v3e7v5e6v2路简单路初级路圈（初级回路）定理4.2.1 在n阶图G中，若从结点vi到vj(vivj)存在一条路，则必存在长度小于等于n-1的路证明：设L：vie1v1e2v2ejvj是G中一条从结点vi到vj长度为L的路，路上有L+1个结点若Ln-1，则定理已证4.2 路和回路 否则，Ln-1，此时，L+1n，即路L上的结点数L+1大于图G中的结点数n，此路上必有相同结点设vk和vs相同于是，此路两次通过同一个结点vk(vs)，所以在L上存在vs到自身的回路Cks在L上删除Cks上的一切边和除vs以外的一切结点，得路L1：vie1v1ekvsejvj。

L1仍为从结点vi到vj的路，且长度至少比L减少1若路L1的长度小于等于n-1，则定理已证否则，重复上述过程由于G有n个结点，经过有限步后，必得到从vi到vj长度小于等于n-1的路4.2 路和回路n 推论:在n阶图G中，若从结点vi到vj(vivj)存在路，则必存在长度小于等于n-1的初级路由定理4.2.1的证明过程知，本推论成立n 类似的可证明下列定理和推论4.2 路和回路n 定理4.2.2 在n阶图G中，若存在结点vi到自身的回路，则必存在vi到自身长度小于等于n的回路推论 在n阶图G中，若存在结点vi到自身的简单回路，则必存在vi到自身长度小于等于n的初级回路 4.2 路和回路4.3.1无向连通图定义4.3.1 在无向图G中，如果结点u和结点v之间存在一条路，则称结点u和结点v连通记为uv规定，G中任意结点v和自身连通，即vv 在无向图中，如果结点u和结点v连通，即uv，那么，结点v和结点u连通，即vu所以，无向图结点间的连通是对称的4.3 连通图4.3.1无向连通图定义4.3.2 设G=V,E是无向图，在图G的结点集V上建立一个二元关系R： R=u,v | uVvVu和v连通 R叫做无向图G的结点集V上的连通关系。

因为R是自反的、对称的、传递的，所以R是V上的等价关系无向图G的结点集V上的连通关系是等价关系4.3 连通图4.3.1无向连通图定义4.3.3 若无向图G中的任何两个结点都是连通的，则称G为连通图规定，平凡图是连通图4.3 连通图4.3.1无向连通图定义4.3.3 设G=V,E是图 V1V且V1，E1是G中两个端点都在V1中的边组成的集合，图G1=V1,E1叫做G的由V1导出的子图，记为GV1 E2E且E2 ，V2是由E2中的边所关联的结点组成的集合，图G2=V2,E2叫做G的由E2导出的子图，记为GE24.3 连通图4.3 连通图n 定义4.3.4 设G=V,E是无向图， R是V上的连通关系，V/R=ViVi是R的等价类，i=1,k 是V关于R的商集，GVi是Vi导出的子图，称GVi( i=1, k)为G的连通分支G的连通分支数记为W(G)4.3 连通图非连通图三个连通分支非连通图两个连通分支例4.3 连通图n 定义4.3.4 每一个连通分支中任何两个结点是连通的，而位于不同连通分支中的任何两个结点是不连通的即每一个连通分支都是原图的最大的连通子图 显然，G是连通图，当且仅当W(G) =1。

4.3 连通图【例】 求证：若图中只有两个奇度数顶点，则二顶点必连通 证明: 用反证法来证明 设二顶点不连通，则它们必分属两个不同的连通分支，而对于每个连通分支，作为G的子图只有一个奇度数顶点，余者均为偶度数顶点，与握手定理推论矛盾，因此，若图中只有两个奇度数顶点，则二顶点必连通4.3 连通图 【例】在一次国际会议中，由七人组成的小组a,b,c,d,e,f,g中，a会英语、阿拉伯语；b会英语、西班牙语；c会汉语、俄语；d会日语、西班牙语；e会德语、汉语和法语；f会日语、俄语；g会英语、法语和德语问：他们中间任何二人是否均可对话（必要时可通过别人翻译）？4.3 连通图n 定义4.3.5 设无向图G=(V,E,)是连通图，若有点集V1V，使图G删除了V1的所有结点后，所得到的子图是不连通的，而删除了V1的任何真子集后，所得到的子图仍是连通的，则称V1是G的一个点割集若某个结点构成一个点割集，则称该结点为割点4.3 连通图4.3 连通图n 如何判断一个图中的割点（关节点）？4.3 连通图例 试验证下列结点集合是否为点割集4.3 连通图例 试验证下列结点集合是否为点割集4.3 连通图n 定义4.3.6 设无向图G=(V,E,)不是完全图， 定义k(G)=min|V1| V1是G的点割集为G的点连通度（或连通度）。

显然，k(G)是为了产生一个不连通图需要删除的点的最少数目4.3 连通图n 定义4.3.7 设无向图G=(V,E,)是连通图，若有边集E1E，使图G删除了E1的所有边后，所得到的子图是不连通的，而删除了E1的任何真子集后，所得到的子图仍是连通的，则称E1是G的一个边割集若某个边构成一个边割集，则称该结点为割边或桥4.3 连通图例 试验证下列边集合是否为割集4.3 连通图例 试验证下列边集合是否为割集4.3 连通图n 定义4.3.8 设无向图G=(V,E,)不是完全图， 定义(G)=min|E1| E1是G的边割集为G的边连通度 显然， (G)是为了产生一个不连通图需要删除的边的最少数目4.3 连通图n 下面是由惠特尼(H.Whitney)于1932年得到的关于结点连通度、边连通度和最小度的不等式联系的定理：n 定理4.3.1： 对任一无向图G=(V,E,)， k(G)(G)(G)4.3 连通图n 证明： 如果G是不连通的，由点连通度和边连通度的定义有k(G)=(G)=0， 所以 k(G)(G) (G)4.3 连通图n 如果G是连通图 先证明(G) (G) 如果G是平凡图，(G)=0(G)，即(G) (G)，如果G是非平凡图，设n=(G)=mindeg(v)|vV，则存在G的一个结点v，它关联了n条边，而其它结点关联的边数大于等于n，将v关联的这n条边删除，G成为不连通的。

从而这n条边或这n条边中的几条边组成一个边割集，即存在一个边割集的基数小于等于n，所以 min|E 1| | E 1是G的边割集n=mindeg(v) | vV ，即 (G) (G) 再证k(G)(G) 设(G)=1，G有一条割边，此边的任一端点是割点，k(G)=1所以k(G)(G)成立4.3 连通图n 设(G)2，则可删除某(G)条边，使G成为不连通的，而删除其中的(G)1条边，它仍然是连通的且有一个桥，设该桥为e=(u,v)对这(G)1条边选取一个不同于u，也不同于v的端点，把这些端点删除，则必至少删除了这(G)1条边若这样产生的图是不连通的，则k(G)(G)1(G)若这样产生的图是连通的，则e=(u,v)仍是桥此时再删除u或v，就必产生了一个不连通图，故k(G)(G) 由和得k(G)(G) (G) 4.3 连通图(G) = 2K(G) = 2(G) = 2例请求出下图的(G), K(G), (G)4.3 连通图(G) = 1 (G) = 2 (G) = 4画出一个的无向简单连通图4.3 连通图n 定理4.3.2 一个连通无向图G中的结点v是割点存在两个结点u和w，使得联结u和w的每条路都经过v。

n 定理4.3.3 一个连通无向图G中的边e是割边,则存在两个结点u和w，使得联结u与w的每条路都经过e4.3 连通图n 4.3.2 有向图的连通性n 定义4.3.9 在有向图G中，结点u到结点v存在一条路，则称结点u到结点v可达记为uv如果u到v可达且v到u也可达，称结点u和结点v相互可达记为uv 规定，G中任何结点v自己到自己可达，即vv4.3 连通图n 4.3.2 有向图的连通性n 定义4.3.10 在简单有向图G中，对于任意两个结点u和v， 如果结点u到结点v可达或结点v到结点u可达，则称G为单向(侧)连通的 如果结点u和结点v互相可达，则称G为强连通的 如果略去方向得到的无向图是连通的，则称G为弱连通的4.3 连通图强连通图单向连通图连通图例4.3 连通图n 下面给出简单有向图的一个应用资源分配图 在多道程序的计算机系统中，可以同时执行多个程序实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、CPU、主存贮器和编译程序等操作系统对这些资源负责分配给各个程序当一个程序要求使用某种资源，它要发出请求，操作系统必须保证这一请求得到满足4.3 连通图n 对资源的请求可能发生冲突。

如程序A控制着资源r1，请求资源r2；但程序B控制着资源r2，请求资源r1这种情况称为处于死锁状态然而冲突的请求必须解决，资源分配图有助发现和纠正死锁n 假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足在请求的时间里，被请求的资源是不能利用的，程序控制着可利用的资源，但对不可利用的资源则必须等待4.3 连通图n 令Pt=p1，p2，pm表示计算机系统在时间t的程序集合，QtPt是运行的程序集合，或者说在时刻t至少分配一部分所请求的资源的程序集合Rt=r1，r2，rn是系统在时刻t的资源集合资源分配图Gt=是有向图，它表示了时间t系统中资源分配状态把每个资源ri看作图中一个结点，其中i=1，2，n表示有向边，E当且仅当程序pkQt已分配到资源ri且等待资源rj4.3 连通图n 例如，令Rt=r1,r2,r3,r4，Qt=p1,p2,p3,p4资源分配状态是： p1占用资源r4且请求资源r1； p2占用资源r1且请求资源r2和r3； p3占用资源r2且请求资源r3； p4占用资源r3且请求资源r1和r44.3 连通图n 于是，可得到资源分配图Gt=，如图所示n 能够证明，在时刻t计算机系统处于死锁状态资源分配图Gt中包含强分图。

于是，对于该图，Gt是强连通的，即处于死锁状态4.3 连通图p1占用资源r4且请求资源r1；p2占用资源r1且请求资源r2和r3；p3占用资源r2且请求资源r3；p4占用资源r3且请求资源r1和r4v 路 回路 简单路 基本路 初级路 圈v 连通图 连通分支v 点割集 割点 割集 割边（桥。