离散数学及其应用第10章-特殊图模型与算法(上)课件

1、2022/7/25计算机应用技术研究所1离散数学Discrete Mathematics 汪荣贵 教授合肥工业大学计算机与信息学院2022/7/25计算机应用技术研究所2第10章 特殊图模型与算法（上）2022/7/25二分图与匹配问题23欧拉图与哈密顿图1 本章学习内容2022/7/25计算机应用技术研究所4欧拉图与哈密顿图2022/7/25计算机应用技术研究所5欧拉图与哈密顿图欧拉图及其性质哈密顿图及其性质中国邮路问题ADBC 欧拉图的引入72022/7/25 欧拉图的引入哥尼斯堡七桥问题：哥尼斯堡小镇有一条贯穿全市的小河，河上有两个小岛，由七座桥将这两个小岛及其与河两岸进行互联，如图所示

2、。问题是怎样才能不重复、不遗漏地走完七座桥，并回到出发点。 欧拉图的定义【定义】设 G=V,E是任意给定的一个图模型，通过图G中所有边一次且仅一次的通路称为欧拉通路，通过图G中所有边一次且仅一的回路称为欧拉回路。如果图G中存在欧拉回路，则称之为欧拉图，如果G中存在欧拉通路但不存在欧拉回路，则称之为半欧拉图。 规定：平凡图为欧拉图。以上定义既适合无向图也适合有向图 欧拉图的特征 例 题【例】判断图中，哪些图是欧拉图，哪些图是半欧拉图? 欧拉通路的判定【定理】设 G=V,E是任意给定的一个无向图模型，则G=V,E是欧拉图当且仅当 G=V,E为连通图且所有结点度数均为偶数。【推论】设 G=V,E是任

3、意给定的一个无向图模型，则G=V,E是半欧拉图当且仅当 G=V,E为连通图且恰有2个奇度数结点。 例 题【例】对于如图所示的图模型 ，试判断哪些图能够一笔画成。 欧拉通路的判定【定理】设 G=V,E是任意给定的一个有向图模型，则有：G=V,E是欧拉图当且仅当 G=V,E为连通图且所有结点的入度等等于出度；G=V,E是半欧拉图，当且仅当G=V,E连通且仅有一个结点的入度比出度大1，另外一个结点的出度比入度大1，其余结点的入度等于出度。 对任意给定的无向连通图，只需通过对图中各结点度数的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图； 对任意给定的有向连通图，只需通过对图中各结点

4、出度与入度的计算，就可知它是否存在欧拉通路及欧拉回路，从而知道它是否为欧拉图。2022/7/25 总 结 七桥问题2022/7/25弗洛莱算法 2022/7/25算法具体步骤 2022/7/25 算法关键 【例】对于图所示的无向图，用弗洛莱算法求出其的一条欧拉通路。 例 题 【解】图中每个结点的度数都是偶数，故存在欧拉回路。 例 题 例 题 例 题 例 题 例 题 例 题 【例】对于图所示三个房间布局的平面设计，其中每个房间两两共墙相连，每面墙上有门通向室外，能否设计一个行走路径，使得某人从某房间里或室外开始出发，经过且只经过每个门一次？【解】将该平面设计图示抽象成一个图模型，每个房间及室外分

5、别构成一个结点，每扇门对应一条边，则问题转化为该图是否存在一条欧拉道路。 例 题 例 题 【例】求出下图的一条Euler回路。v1v2v5v3v4v6v7v8v9 例 题 【解】看每个顶点的度是否都是偶数。 d(V1)=2， d(V2)=4， d(V3)=2， d(V4)=4， d(V5)=4， d(V6)=4， d(V7)=2， d(V8)=2， d(V9)=4。 所以存在Euler回路。v1v2v5v3v4v6v7v8v9 例 题 可以任意一个顶点为起点，这里以v2为起点，依序去掉相连的边v1v2v5v3v4v6v7v8v9 例 题 (1)先去掉(v2,v4)v1v2v5v3v4v6v7v

6、8v91 例 题 (2) 接着去掉(v4,v3)v1v2v5v3v4v6v7v8v912 例 题 (3)接着去掉(v3,v2)v1v2v5v3v4v6v7v8v9123 例 题 依序去掉相连的边。v1v2v5v3v4v6v7v8v9123 例 题 v1v2v5v3v4v6v7v8v912345678这时，如果去掉(v6,v5)将导致图不连通 例 题 v1v2v5v3v4v6v7v8v91234567891011121314V2-v4-v3-v2-v1-v4-v5-v9-v6-v8-v9-v7-v6-v5-v2Euler回路：从上例可知， Euler回路不唯一。 例 题 2022/7/25 例

7、题 2022/7/25计算机应用技术研究所38 欧拉图与哈密顿图 欧拉图及其性质 哈密顿图及其性质 中国邮路问题 哈密顿图的引入 哈密顿图的引入 哈密顿图的定义【定义】经过图中每个结点一次且仅一次的通路称为哈密顿通路。经过图中每个结点一次且仅一次的回路称为哈密顿回路。存在哈密顿回路的图称为哈密顿图；存在哈密顿通路的图称为半哈密顿图。规定：平凡图为哈密顿图。 哈密顿图 哈密顿路径的特点 哈密顿通路是经过图中所有结点的最短通路，即：经过图中所有结点的基本通路。 哈密顿回路是经过图中所有结点的最短回路，即：经过图中所有结点的基本回路。 事实上，哈密顿通路就是图中所有结点的一个全排列。2022/7/2

8、5 例 题 【例】下面各图是否哈密顿图？是否存在哈密顿通路？2022/7/25 例 题 哈密顿图的必要条件哈密顿图的必要条件哈密顿图的推论2022/7/25 例 题 2022/7/25 通常利用定理的逆否命题判断某图不是哈密顿图。 必要但非充分2022/7/25 例 题 2022/7/25 例 题 哈密顿图的充分条件定理的证明定理的证明定理的证明奥尔定理 充分而非必要2022/7/25 例 题 【例】由7个外交官举行一场重要会议，其中A只会讲英语，B会讲英语和汉语，C会讲英语、意大利语和俄语，D会讲日语和汉语，E会讲德语和意大利语，F会讲法语、日语和俄语，G会讲法语和德语。问如何安排座位，使得

9、在没有翻译官的情况下，这7个人都能够和他身边的人交谈。【解】2022/7/25 例 题 2022/7/25 例 题 2022/7/25 例 题 2022/7/25 例 题 2022/7/25计算机应用技术研究所64 欧拉图与哈密顿图 欧拉图及其性质 哈密顿图及其性质 中国邮路问题2022/7/25 中国邮路问题2022/7/25 数学模型2022/7/25 问题分析2022/7/25 构造算法2022/7/25 构造算法2022/7/25 例 题 【例】图所示图模型表示某邮递员负责投递街道的结构图，其中每条边分别表示一条街道，每个结点表示街道的交叉路口，每条边的权值表示该边所对应街道长度，单位

10、是公里。如何设计线路使得邮递员在经过每条街道至少一次的前期下总路程最短。2022/7/25 例 题 【解】步骤1需向其添加平行边扩展为欧拉图。2022/7/25 例 题 2022/7/25 例 题 2022/7/25 例 题 2022/7/25 例 题 2022/7/25欧拉图与哈密顿图1二分图与匹配问题2 本章学习内容2022/7/25计算机应用技术研究所77二分图与匹配问题2022/7/25计算机应用技术研究所78 二分图与匹配问题二分图的概念与性质完备匹配与最大匹配最大匹配判定与构造2022/7/25 二分图实例【解】可将如图所示图模型的所有结点划分为应聘者和岗位这两个不同的集合，属于同

11、一个集合的结点之间无边联结，图中所有边的两个端点均分属两个不同的集合。具有这种特征的图模型就是二分图。2022/7/25 二分图的定义2022/7/25 二分图的概念2022/7/25 完全二分图2022/7/25 例 题 【例】如图所示的图G和H是否为二分图。【解】图G是二分图。图H则不是二分图。2022/7/25 例 题 2022/7/25 二分图的判定 2022/7/25 二分图的判定 2022/7/25 二分图的判定 2022/7/25 二分图的判定 2022/7/25 例 题 【例】判定如图所示图模型是否为二分图。2022/7/25 例 题 【例】a,b,c,d,e,f分别为某次国际

12、学术会议的六个成员，其中：a只会说德语、日语和俄语；b只会说汉语、法语和日语；c只会说俄语和西班牙语；d只会说汉语和西班牙语；e只会说英语和德语；f只会说英语和法语。会议时需要将该六人分为两组，是否会发生同一组内的任意两个成员不能互相直接交谈的情况？2022/7/25计算机应用技术研究所91 二分图与匹配问题 二分图的概念与性质 完备匹配与最大匹配 最大匹配判定与构造2022/7/25 匹配问题 2022/7/25 匹配问题 2022/7/25 匹配的概念 2022/7/25 匹配的概念 2022/7/25 例题 2022/7/25 霍尔定理2022/7/25 霍尔定理的思想2022/7/25

13、 例题 2022/7/25 t-条件判定 2022/7/25 t条件判定 2022/7/25 例题 2022/7/25 例题 2022/7/25计算机应用技术研究所104二分图与匹配问题二分图的概念与性质完备匹配与最大匹配最大匹配判定与构造2022/7/25 可增广道 2022/7/25 例题 2022/7/25 可增广道 2022/7/25 匈牙利算法 1965年，匈牙利的著名数学家Edmonds设计了一种求最大匹配的算法，称为匈牙利(Hungarian)算法。2022/7/25 算法基本思想 2022/7/25 算法描述 用匈牙利算法求下图的最大匹配：x1x2y1x3x4x5y2y3y4y

14、5 例 题 （1）任给一个初始匹配；（2）若X已经饱和，结束；否则转（3）；x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)（3）在X中找一个非饱和点x2，V1=x2，V2=（4）若N(V1)=V2则停止，否则任选一点yN(V1)-V2x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)V1=x2,V2=N(V1)=y2, y3 （5）若y已饱和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】x1x2y1x3x4

15、x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)V1=V1x5=x2,x5；V2=V2 y3 =y3V1=x2,V2=（4）若N(V1)=V2则停止，否则任选一点yN(V1)-V2；x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)V1=x2,x5；V2=y3N(V1)=y2, y3 , y5 （5）若y已饱和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5

16、),(x5,y3)V1=x2,x5；V2=y3；V1=V1x3=x2,x5, x3；V2=V2 y5 =y3 ,y5（4）若N(V1)=V2则停止，否则任选一点yN(V1)-V2；x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x5,y3)V1=x2,x5, x3；V2 =y3 ,y5；N(V1)=y2, y3 , y5（5）若y已饱和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x3,y5),(x

17、5,y3)V1=x2,x5, x3；V2 =y3 ,y5；x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=M E(P)=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)（2）若X已经饱和，结束；否则转（3）；（3）在X中找一个非饱和点x0，V1=x0，V2=（4）若N(V1)=V2则停止，否则任选一点yN(V1)-V2x1x2y1x3x4x5y2y3y4y5V1=x4；V2 =M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)N(V1)=y3（5）若y已饱和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V

18、2 y； 转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】x1x2y1x3x4x5y2y3y4y5V1=x4；V2 =M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)V1=V1x2=x4,x2；V2=V2y3 =y3（4）若N(V1)=V2则停止，否则任选一点yN(V1)-V2x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)V1=x4,x2,；V2 =y3 N(V1)=y2, y3（5）若y已饱和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 转（4）】，否则

19、【求一条从x0到y的可增广道路P，对之进行增广；转（2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)V1=x4,x2,；V2 =y3 V1=V1x3=x4,x2 ,x3；V2=V2y2 =y3,y2（4）若N(V1)=V2则停止，否则任选一点yN(V1)-V2x1x2y1x3x4x5y2y3y4y5M=(x1,y1 ),(x2,y3),(x3,y2),( x5,y5)V1=x4,x2 ,x3；V2=y3,y2N(V1)=y2, y3 , y5（5）若y已饱和， M中必有(y,z) ；作【 V1 =V1 z ， V2 =V2 y； 转（4）】，否则【求一条从x0到y的可增广道路P，对之进行增广；转（2）】x1x2y1x3x4