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

1、2022-8-5计算机应用技术研究所计算机应用技术研究所1离散数学离散数学Discrete Mathematics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2022-8-5计算机应用技术研究所计算机应用技术研究所2第第1010章章 特殊图模型与算法特殊图模型与算法（上）（上）2022-8-52022-8-5二分图与匹配问题二分图与匹配问题2 23 3欧拉图与哈密顿图欧拉图与哈密顿图1 1&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所4欧拉图与哈密顿图欧拉图与哈密顿图2022-8-5计算机应用技术研究所计算机应用技术研究所5

2、&欧拉图与哈密顿图欧拉图与哈密顿图J欧拉图及其性质欧拉图及其性质4哈密顿图及其性质哈密顿图及其性质4中国邮路问题中国邮路问题ADBC&欧拉图的引入欧拉图的引入72022-8-5&欧拉图的引入欧拉图的引入哥尼斯堡七桥问题：哥尼斯堡小镇有一条贯穿全市的小河，河上有两个小岛，由七座桥将这两个小岛及其与河两岸进行互联，如图所示。问题是怎样才能不重复、不遗漏地走完七座桥，并回到出发点。&欧拉图的定义欧拉图的定义【定义】设 G=V,E 是任意给定的一个图模型，通过图G中所有边一次且仅一次的通路称为欧拉通路，通过图G中所有边一次且仅一的回路称为欧拉回路。如果图G中存在欧拉回路，则称之为欧拉图，如果G中存在欧

3、拉通路但不存在欧拉回路，则称之为半欧拉图。规定：平凡图为欧拉图。以上定义既适合无向图也适合有向图&欧拉图的特征欧拉图的特征&例例 题题【例】判断图中，哪些图是欧拉图，哪些图是半欧拉图?&欧拉通路的判定欧拉通路的判定【定理】设 G=V,E 是任意给定的一个无向图模型，则G=V,E 是欧拉图当且仅当 G=V,E 为连通图且所有结点度数均为偶数。【推论】设 G=V,E 是任意给定的一个无向图模型，则G=V,E 是半欧拉图当且仅当 G=V,E 为连通图且恰有2个奇度数结点。&例例 题题【例】对于如图所示的图模型，试判断哪些图能够一笔画成。&欧拉通路的判定欧拉通路的判定【定理】设 G=V,E 是任意给定

4、的一个有向图模型，则有：G=V,E 是欧拉图当且仅当 G=V,E 为连通图且所有结点的入度等等于出度；G=V,E 是半欧拉图，当且仅当G=V,E 连通且仅有一个结点的入度比出度大1，另外一个结点的出度比入度大1，其余结点的入度等于出度。2022-8-52022-8-5&总总 结结&七桥问题七桥问题2022-8-52022-8-5&弗洛莱算法弗洛莱算法 2022-8-52022-8-5&算法具体步骤算法具体步骤 2022-8-52022-8-5&算法关键算法关键 【例】对于图所示的无向图，用弗洛莱算法求出其的一条欧拉通路。&例例 题题 【解】图中每个结点的度数都是偶数，故存在欧拉回路。&例例 题

5、题&例例 题题&例例 题题&例例 题题&例例 题题&例例 题题 【例】对于图所示三个房间布局的平面设计，其中每个房间两两共墙相连，每面墙上有门通向室外，能否设计一个行走路径，使得某人从某房间里或室外开始出发，经过且只经过每个门一次？【解】将该平面设计图示抽象成一个图模型，每个房间及室外分别构成一个结点，每扇门对应一条边，则问题转化为该图是否存在一条欧拉道路。&例例 题题&例例 题题 【例例】求出下图的一条求出下图的一条EulerEuler回路。回路。v1v2v5v3v4v6v7v8v9&例例 题题 【解解】看每个顶点的度是否都是偶数。看每个顶点的度是否都是偶数。d(V1)=2 d(V1)=2，

6、d(V2)=4d(V2)=4，d(V3)=2d(V3)=2，d(V4)=4 d(V4)=4，d(V5)=4d(V5)=4，d(V6)=4d(V6)=4，d(V7)=2d(V7)=2，d(V8)=2d(V8)=2，d(V9)=4d(V9)=4。所以存在所以存在EulerEuler回路。回路。v1v2v5v3v4v6v7v8v9&例例 题题 可以任意一个顶点为起点，这里以可以任意一个顶点为起点，这里以v2v2为起点，依为起点，依序去掉相连的边序去掉相连的边v1v2v5v3v4v6v7v8v9&例例 题题 (1)先去掉(v2,v4)v1v2v5v3v4v6v7v8v91&例例 题题 (2)接着去掉(

7、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-8-52022

8、-8-5&例例 题题 2022-8-5计算机应用技术研究所计算机应用技术研究所38&欧拉图与哈密顿图欧拉图与哈密顿图4 欧拉图及其性质欧拉图及其性质J 哈密顿图及其性质哈密顿图及其性质4 中国邮路问题中国邮路问题&哈密顿图的引入哈密顿图的引入&哈密顿图的引入哈密顿图的引入&哈密顿图的定义哈密顿图的定义【定义】经过图中每个结点一次且仅一次的通路称为哈密顿通路。经过图中每个结点一次且仅一次的回路称为哈密顿回路。存在哈密顿回路的图称为哈密顿图；存在哈密顿通路的图称为半哈密顿图。规定：平凡图为哈密顿图。&哈密顿图哈密顿图&哈密顿路径的特点哈密顿路径的特点 哈密顿通路是经过图中所有结点的最短通路，即：经

9、过图中所有结点的基本通路。哈密顿回路是经过图中所有结点的最短回路，即：经过图中所有结点的基本回路。事实上，哈密顿通路就是图中所有结点的一个全排列。2022-8-52022-8-5&例例 题题 【例】下面各图是否哈密顿图？是否存在哈密顿通路？2022-8-52022-8-5&例例 题题&哈密顿图的必要条件哈密顿图的必要条件&哈密顿图的必要条件哈密顿图的必要条件&哈密顿图的推论哈密顿图的推论2022-8-52022-8-5&例例 题题 2022-8-52022-8-5 通常利用定理的逆否命题判断某图不是哈密通常利用定理的逆否命题判断某图不是哈密顿图。顿图。&必要但非充分必要但非充分2022-8-5

10、2022-8-5&例例 题题 2022-8-52022-8-5&例例 题题&哈密顿图的充分条件哈密顿图的充分条件&定理的证明定理的证明&定理的证明定理的证明&定理的证明定理的证明&奥尔定理奥尔定理&充分而非必要充分而非必要2022-8-52022-8-5&例例 题题 【例】由7个外交官举行一场重要会议，其中A只会讲英语，B会讲英语和汉语，C会讲英语、意大利语和俄语，D会讲日语和汉语，E会讲德语和意大利语，F会讲法语、日语和俄语，G会讲法语和德语。问如何安排座位，使得在没有翻译官的情况下，这7个人都能够和他身边的人交谈。【解】2022-8-52022-8-5&例例 题题 2022-8-52022

11、-8-5&例例 题题 2022-8-52022-8-5&例例 题题 2022-8-52022-8-5&例例 题题 2022-8-5计算机应用技术研究所计算机应用技术研究所64&欧拉图与哈密顿图欧拉图与哈密顿图4 欧拉图及其性质欧拉图及其性质4 哈密顿图及其性质哈密顿图及其性质J 中国邮路问题中国邮路问题2022-8-52022-8-5&中国邮路问题中国邮路问题2022-8-52022-8-5&数学模型数学模型2022-8-52022-8-5&问题分析问题分析2022-8-52022-8-5&构造算法构造算法2022-8-52022-8-5&构造算法构造算法2022-8-52022-8-5&例例

12、 题题 【例】图所示图模型表示某邮递员负责投递街道的结构图，其中每条边分别表示一条街道，每个结点表示街道的交叉路口，每条边的权值表示该边所对应街道长度，单位是公里。如何设计线路使得邮递员在经过每条街道至少一次的前期下总路程最短。2022-8-52022-8-5&例例 题题 【解】步骤1需向其添加平行边扩展为欧拉图。2022-8-52022-8-5&例例 题题 2022-8-52022-8-5&例例 题题 2022-8-52022-8-5&例例 题题 2022-8-52022-8-5&例例 题题 2022-8-52022-8-5欧拉图与哈密顿图欧拉图与哈密顿图1 1二分图与匹配问题二分图与匹配问

13、题2 2&本章学习内容本章学习内容2022-8-5计算机应用技术研究所计算机应用技术研究所77二分图与匹配问题二分图与匹配问题2022-8-5计算机应用技术研究所计算机应用技术研究所78&二分图与匹配问题二分图与匹配问题J二分图的概念与性质二分图的概念与性质4完备匹配与最大匹配完备匹配与最大匹配4最大匹配判定与构造最大匹配判定与构造2022-8-52022-8-5&二分图实例二分图实例【解】可将如图所示图模型的所有结点划分为应聘者和岗位这两个不同的集合，属于同一个集合的结点之间无边联结，图中所有边的两个端点均分属两个不同的集合。具有这种特征的图模型就是二分图。2022-8-52022-8-5&

14、二分图的定义二分图的定义2022-8-52022-8-5&二分图的概念二分图的概念2022-8-52022-8-5&完全二分图完全二分图2022-8-52022-8-5&例例 题题 【例】如图所示的图G和H是否为二分图。【解】图G是二分图。图H则不是二分图。2022-8-52022-8-5&例例 题题 2022-8-52022-8-5&二分图的判定二分图的判定 2022-8-52022-8-5&二分图的判定二分图的判定 2022-8-52022-8-5&二分图的判定二分图的判定 2022-8-52022-8-5&二分图的判定二分图的判定 2022-8-52022-8-5&例例 题题 【例】判定

15、如图所示图模型是否为二分图。2022-8-52022-8-5&例例 题题 【例】a,b,c,d,e,f分别为某次国际学术会议的六个成员，其中：a只会说德语、日语和俄语；b只会说汉语、法语和日语；c只会说俄语和西班牙语；d只会说汉语和西班牙语；e只会说英语和德语；f只会说英语和法语。会议时需要将该六人分为两组，是否会发生同一组内的任意两个成员不能互相直接交谈的情况？2022-8-5计算机应用技术研究所计算机应用技术研究所91&二分图与匹配问题二分图与匹配问题4 二分图的概念与性质二分图的概念与性质J 完备匹配与最大匹配完备匹配与最大匹配4 最大匹配判定与构造最大匹配判定与构造2022-8-520

16、22-8-5&匹配问题匹配问题 2022-8-52022-8-5&匹配问题匹配问题 2022-8-52022-8-5&匹配的概念匹配的概念 2022-8-52022-8-5&匹配的概念匹配的概念 2022-8-52022-8-5&例题例题 2022-8-52022-8-5&霍尔定理霍尔定理2022-8-52022-8-5&霍尔定理的思想霍尔定理的思想2022-8-52022-8-5&例题例题 2022-8-52022-8-5&t-t-条件判定条件判定 2022-8-52022-8-5&t t条件判定条件判定 2022-8-52022-8-5&例题例题 2022-8-52022-8-5&例题例题

17、 2022-8-5计算机应用技术研究所计算机应用技术研究所104&二分图与匹配问题二分图与匹配问题4二分图的概念与性质二分图的概念与性质4完备匹配与最大匹配完备匹配与最大匹配J最大匹配判定与构造最大匹配判定与构造2022-8-52022-8-5&可增广道可增广道 2022-8-52022-8-5&例题例题 2022-8-52022-8-5&可增广道可增广道 2022-8-52022-8-5&匈牙利算法匈牙利算法 1965 1965年，匈牙利的著名数学家年，匈牙利的著名数学家EdmondsEdmonds设计了一种求最大匹配的算设计了一种求最大匹配的算法，称为匈牙利法，称为匈牙利(Hungaria

18、n)(Hungarian)算法。算法。2022-8-52022-8-5&算法基本思想算法基本思想 2022-8-52022-8-5&算法描述算法描述 用匈牙利算法求下图的最大匹配：用匈牙利算法求下图的最大匹配：x1x2y1x3x4x5y2y3y4y5&例例 题题 （1 1）任给一个初始匹配；）任给一个初始匹配；（2 2）若）若X X已经饱和，结束；否则转（已经饱和，结束；否则转（3 3）；）；x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)（3 3）在）在X X中找一个非饱和点中找一个非饱和点x x2 2，V V1 1=x=x2 2，V V2 2=（4

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

20、广；转（2 2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)V V1 1=V=V1 1xx5 5=x=x2 2,x,x5 5；V V2 2=V=V2 2 yy3 3 =y=y3 3 V V1 1=x=x2 2,V,V2 2=（4 4）若）若N(VN(V1 1)=V)=V2 2则停止，否则任选一点则停止，否则任选一点yN(VyN(V1 1)-V)-V2 2；x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)V V1 1=x=x2 2,x,x5 5；V V2 2=y=y3 3 N(VN(V1 1)=y)=y2

21、2,y y3 3,y y5 5 （5 5）若）若y y已饱和，已饱和，M M中必有中必有(y,z)(y,z)；作；作【V V1 1=V=V1 1 z z，V V2 2=V=V2 2 yy；转（转（4 4）】，否则，否则【求一条从求一条从x x0 0到到y y的可增广道路的可增广道路P P，对之进行增广；转（对之进行增广；转（2 2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)V V1 1=x=x2 2,x,x5 5；V V2 2=y=y3 3；V V1 1=V=V1 1xx3 3=x=x2 2,x,x5 5,x x3 3；V V2 2=V=V2

22、2 yy5 5 =y=y3 3,y,y5 5（4 4）若）若N(VN(V1 1)=V)=V2 2则停止，否则任选一点则停止，否则任选一点yN(VyN(V1 1)-V)-V2 2；x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)V V1 1=x=x2 2,x,x5 5,x x3 3；V V2 2=y=y3 3,y,y5 5；N(VN(V1 1)=y)=y2 2,y y3 3,y y5 5（5 5）若）若y y已饱和，已饱和，M M中必有中必有(y,z)(y,z)；作；作【V V1 1=V=V1 1 z z，V V2 2=V=V2 2 yy；转（转（4 4

23、）】，否则，否则【求一条从求一条从x x0 0到到y y的可增广道路的可增广道路P P，对之进，对之进行增广；转（行增广；转（2 2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x3,y5),(x5,y3)V V1 1=x=x2 2,x,x5 5,x x3 3；V V2 2=y=y3 3,y,y5 5；x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=M E(P)=(x1,y1),(x2,y3),(x3,y2),(x5,y5)（2 2）若）若X X已经饱和，结束；否则转（已经饱和，结束；否则转（3 3）；）；（3 3）在）在X X中找一个非

24、饱和点中找一个非饱和点x x0 0，V V1 1=x=x0 0，V V2 2=（4 4）若）若N(VN(V1 1)=V)=V2 2则停止，否则任选一点则停止，否则任选一点yN(VyN(V1 1)-V)-V2 2x1x2y1x3x4x5y2y3y4y5V V1 1=x=x4 4；V V2 2=M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)N(VN(V1 1)=y)=y3 3（5 5）若）若y y已饱和，已饱和，M M中必有中必有(y,z)(y,z)；作；作【V V1 1=V=V1 1 z z，V V2 2=V=V2 2 yy；转（转（4 4）】，否则，否则【求一条从求一条从x

25、 x0 0到到y y的可增广道路的可增广道路P P，对之进，对之进行增广；转（行增广；转（2 2）】x1x2y1x3x4x5y2y3y4y5V V1 1=x=x4 4；V V2 2=M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)V V1 1=V=V1 1xx2 2=x=x4 4,x,x2 2；V V2 2=V=V2 2yy3 3 =y=y3 3（4 4）若）若N(VN(V1 1)=V)=V2 2则停止，否则任选一点则停止，否则任选一点yN(VyN(V1 1)-V)-V2 2x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y

26、5)V V1 1=x=x4 4,x,x2 2,；V V2 2=y=y3 3 N(VN(V1 1)=y)=y2 2,y y3 3（5 5）若）若y y已饱和，已饱和，M M中必有中必有(y,z)(y,z)；作；作【V V1 1=V=V1 1 z z，V V2 2=V=V2 2 yy；转（转（4 4）】，否则，否则【求一条从求一条从x x0 0到到y y的可增广道路的可增广道路P P，对之进，对之进行增广；转（行增广；转（2 2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)V V1 1=x=x4 4,x,x2 2,；V V2 2=y=

27、y3 3 V V1 1=V=V1 1xx3 3=x=x4 4,x,x2 2,x,x3 3；V V2 2=V=V2 2yy2 2 =y=y3 3,y,y2 2（4 4）若）若N(VN(V1 1)=V)=V2 2则停止，否则任选一点则停止，否则任选一点yN(VyN(V1 1)-V)-V2 2x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)V V1 1=x=x4 4,x,x2 2,x,x3 3；V V2 2=y=y3 3,y,y2 2 N(VN(V1 1)=y)=y2 2,y y3 3,y y5 5（5 5）若）若y y已饱和，已饱和，M M

28、中必有中必有(y,z)(y,z)；作；作【V V1 1=V=V1 1 z z，V V2 2=V=V2 2 yy；转（转（4 4）】，否则，否则【求一条从求一条从x x0 0到到y y的可增广道路的可增广道路P P，对之进，对之进行增广；转（行增广；转（2 2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)V V1 1=x=x4 4,x,x2 2,x,x3 3；V V2 2=y=y3 3,y,y2 2 V V1 1=V=V1 1xx5 5=x=x4 4,x,x2 2,x,x3 3,x x5 5；V V2 2=V=V2 2yy5 5 =

29、y=y3 3,y,y2 2,y,y5 5（4 4）若）若N(VN(V1 1)=V)=V2 2则停止，否则任选一点则停止，否则任选一点yN(VyN(V1 1)-V)-V2 2x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)V V1 1=x=x4 4,x,x2 2,x,x3 3,x x5 5；V V2 2=y=y3 3,y,y2 2,y,y5 5 N(VN(V1 1)=y)=y2 2,y y3 3,y y5 5,y y4 4 （5 5）若）若y y已饱和，已饱和，M M中必有中必有(y,z)(y,z)；作；作【V V1 1=V=V1 1 z

30、 z，V V2 2=V=V2 2 yy；转（转（4 4）】，否则，否则【求一条从求一条从x x0 0到到y y的可增广道路的可增广道路P P，对之进行增广；转（对之进行增广；转（2 2）】x1x2y1x3x4x5y2y3y4y5M=(x1,y1),(x2,y3),(x3,y2),(x5,y5)V V1 1=x=x4 4,x,x2 2,x,x3 3,x x5 5；V V2 2=y=y3 3,y,y2 2,y,y5 5 x1x2y1x3x4x5y2y3y4y5x1x2y1x3x4x5y2y3y4y5M=M E(P)=(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)（2 2）若）若X X已经饱和，结束；否则转（已经饱和，结束；否则转（3 3）；）；x1x2y1x3x4x5y2y3y4y5 这时，这时，M=(x1,y1),(x2,y2),(x3,y5),(x4,y3),(x5,y4)就是所求的最大匹配。就是所求的最大匹配。2022-8-52022-8-5&例题例题 2022-8-52022-8-5计算机应用技术研究所计算机应用技术研究所129129