1、2022-7-23计算机应用技术研究所计算机应用技术研究所11离散数学离散数学Discrete Mathematics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2022-7-23计算机应用技术研究所计算机应用技术研究所2第第1010章章 特殊图模型与算法特殊图模型与算法(下下)2022-7-232022-7-23&本章学习内容本章学习内容网络流图及其优化问题网络流图及其优化问题4 4平面图与着色问题平面图与着色问题3 35 5特殊图模型的应用特殊图模型的应用2022-7-23计算机应用技术研究所计算机应用技术研究所4平面图与着色问题平面图与着色问题2022-
2、7-23计算机应用技术研究所计算机应用技术研究所5&平面图与着色问题平面图与着色问题J 平面图的概念与性质平面图的概念与性质4 平面图的对偶图平面图的对偶图4 着色问题与算法着色问题与算法2022-7-232022-7-23&应用实例应用实例 2022-7-232022-7-23&交叉点与交叉边交叉点与交叉边2022-7-232022-7-23&可平面图可平面图 2022-7-232022-7-23&平面图的定义平面图的定义 2022-7-232022-7-23&非平面图非平面图 2022-7-232022-7-23&最大平面图最大平面图 2022-7-232022-7-23&面与边界思想面与
3、边界思想2022-7-232022-7-23&面与边界的定义面与边界的定义2022-7-232022-7-23&对面理解对面理解2022-7-232022-7-23&例例 题题2022-7-232022-7-23&一点说明一点说明2022-7-232022-7-23&次数与边的关系次数与边的关系2022-7-232022-7-23&欧拉公式欧拉公式2022-7-232022-7-23&欧拉公式欧拉公式2022-7-232022-7-23&欧拉公式欧拉公式2022-7-232022-7-23&定理定理2022-7-232022-7-23&定理定理2022-7-232022-7-23&非平面图的判
4、定非平面图的判定2022-7-232022-7-23&例例 题题2022-7-232022-7-23&定理定理2022-7-232022-7-23&例例 题题2022-7-232022-7-23&定义定义2022-7-232022-7-23&例例 题题2022-7-232022-7-23&定义定义2022-7-232022-7-23&库拉托夫斯基定理库拉托夫斯基定理2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例例 题题【例】证明图（a）所示的图G不是平面图。2022-7-23计算机应用技术研究所计算机应用技术研究所33&平面图与着色问题平面图与着色问题
5、4 平面图的概念与性质平面图的概念与性质J 平面图的对偶图平面图的对偶图4 着色问题与算法着色问题与算法2022-7-232022-7-23&对偶图的概念对偶图的概念2022-7-232022-7-23&例例 题题2022-7-232022-7-23&对偶图的性质对偶图的性质2022-7-232022-7-23&对偶图的定理对偶图的定理2022-7-23计算机应用技术研究所计算机应用技术研究所38&平面图与着色问题平面图与着色问题4平面图的概念与性质平面图的概念与性质4平面图的对偶图平面图的对偶图J着色问题与算法着色问题与算法2022-7-232022-7-23&四色猜想四色猜想2022-7-
6、232022-7-23&应用实例应用实例【解】可用一个无向图模型表示上述问题，图的每个结点分别代表一种食物，如果两种食物不能放在一起，则在这两种食物之间画一条无向边。2022-7-232022-7-23&应用实例应用实例可通过对该图的结进行着色的方法实现对上述问题的求解。具体地说，就是对图中每个结点分别涂上或者标注一种颜色，并满足相邻的结点之间具有不同的颜色，将相同颜色结点所代表的食物放在同一个隔间，则所需要的最少颜色数目显然就是所求的冰箱隔间数目。一种着色方案：2022-7-232022-7-23&结点着色结点着色2022-7-232022-7-23&例例 题题2022-7-232022-7
7、-23&例例 题题2022-7-232022-7-23&例例 题题2022-7-232022-7-23&点色数的性质点色数的性质2022-7-232022-7-23&布鲁克斯定理布鲁克斯定理2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例例 题题2022-7-232022-7-23&边着色边着色2022-7-232022-7-23&维津定理维津定理2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例例 题题2022-7-232022-7-23&例例 题题【解】（1）该问题
8、可用如图所示二分图G的边着色方法求解。一节课的时段对应边的一个着色组。由于G是二分图，故边色数是G的最大度35，即最少总课时时段为35节。故平均每天要安排7节课。（2）若每天安排8节课，则由G的总边数240知需要240/40=6间教室。2022-7-232022-7-23&平面图的面着色平面图的面着色2022-7-232022-7-23&面着色的定义面着色的定义2022-7-232022-7-23&面着色猜想面着色猜想2022-7-232022-7-23&面着色的性质面着色的性质面着色可以转化为点着色来完成面着色可以转化为点着色来完成【定理定理】地图地图G G是是k-k-面可色的，当且仅当它面
9、可色的，当且仅当它的对偶图的对偶图G G*是是k-k-可色图。可色图。【定理定理】若图若图G G是一个简单平面图，则该图是一个简单平面图，则该图中至少存在一个度数小于或等于中至少存在一个度数小于或等于5 5的结点。的结点。四色猜想：四色猜想：连通简单平面图的色数不超过4。2022-7-232022-7-23&结点着色算法结点着色算法对下图顶点进行着色。对下图顶点进行着色。v1v2v3v4v5v7v6&例例 题题（1 1）对）对i=1,2,n,i=1,2,n,作作C Ci i=c=c1 1,c,c2 2,c,ci i；v1v2v3v4v5v7v6C1=c1C2=c1,c2C3=c1,c2,c3C
10、4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7&例例 题题（2 2）标顶点）标顶点v vi i(i=1,2,n)(i=1,2,n)的颜色集的颜色集C Ci i的第一种颜色的第一种颜色c ck k；C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7v1v2v3v4v5v7v6c1&例例 题题（3 3）对顶点）对顶点v vi i的所有邻接点的所有邻接点v
11、vj j(ji)(ji)，作，作C Cj j=C=Cj j-c-ck k；v1v2v3v4v5v7v6c1C1=c1C2=c1,c2C3=c1,c2,c3C4=c1,c2,c3,c4C5=c1,c2,c3,c4,c5C6=c1,c2,c3,c4,c5,c6C7=c1,c2,c3,c4,c5,c6,c7C2=c2 C3=c2,c3 C7=c2,c3,c4,c5,c6,c7 C5=c2,c3,c4,c5 C6=c2,c3,c4,c5,c6 （4 4）转到（）转到（2 2），直到所有顶点都着色为止），直到所有顶点都着色为止（2 2）标顶点）标顶点v vi i(i=1,2,n)(i=1,2,n)的颜色
12、集的颜色集C Ci i的第一种颜色的第一种颜色c ck kv1v2v3v4v5v7v6c1C1=c1C2=c2C3=c2,c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（3 3）对顶点）对顶点v vi i的所有邻接点的所有邻接点v vj j(ji)(ji)，作，作C Cj j=C=Cj j-c-ck k；v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c2,c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2
13、C3=c3 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（4 4）转到（）转到（2 2），直到所有顶点都着色为止），直到所有顶点都着色为止（2 2）标顶点）标顶点v vi i(i=1,2,n)(i=1,2,n)的颜色集的颜色集C Ci i的第一种颜色的第一种颜色c ck kc3v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c3,c4C5=c2,c3,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,
14、c4,c5,c6,c7c2（3 3）对顶点）对顶点v vi i的所有邻接点的所有邻接点v vj j(ji)(ji)，作，作C Cj j=C=Cj j-c-ck k；c3C5=c2,c4,c5 C1=c1,c2,c4 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（4 4）转到（）转到（2 2），直到所有顶点都着色为止），直到所有顶点都着色为止（2 2）标顶点）标顶点v vi i(i=1,2,n)(i=1,2,n)的颜色集的颜色集C Ci i的第一种颜色的第一
15、种颜色c ck kc3c1v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（3 3）对顶点）对顶点v vi i的所有邻接点的所有邻接点v vj j(ji)(ji)，作，作C Cj j=C=Cj j-c-ck k；c3c1v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（4 4）转到（）转到（2 2），直到所有顶点都着色为止），
16、直到所有顶点都着色为止（2 2）标顶点）标顶点v vi i(i=1,2,n)(i=1,2,n)的颜色集的颜色集C Ci i的第一种颜色的第一种颜色c ck kc3c1c2v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c2,c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（3 3）对顶点）对顶点v vi i的所有邻接点的所有邻接点v vj j(ji)(ji)，作，作C Cj j=C=Cj j-c-ck k；c3c1c2C6=c3,c4,c5,c6 v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4
17、=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（4 4）转到（）转到（2 2），直到所有顶点都着色为止），直到所有顶点都着色为止（2 2）标顶点）标顶点v vi i(i=1,2,n)(i=1,2,n)的颜色集的颜色集C Ci i的第一种颜色的第一种颜色c ck kc3c1c2c3v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c3,c4,c5,c6,c7c2（3 3）对顶点）对顶点v vi i的所有邻接点的所有邻接点v vj j(j
18、i)(ji)，作，作C Cj j=C=Cj j-c-ck k；c3c1c2C7=c2,c4,c5,c6,c7 c3v1v2v3v4v5v7v6c1C1=c1C2=c2C3=c3C4=c1,c2,c4C5=c2,c4,c5C6=c3,c4,c5,c6C7=c2,c4,c5,c6,c7c2（4 4）转到（）转到（2 2），直到所有顶点都着色为止），直到所有顶点都着色为止（2 2）标顶点）标顶点v vi i(i=1,2,n)(i=1,2,n)的颜色集的颜色集C Ci i的第一种颜色的第一种颜色c ck kc3c1c2c3c2【例】用韦尔奇鲍威尔算法对图(a)所示连通无向图进行结点着色&例例 题题20
19、22-7-232022-7-23&本章学习内容本章学习内容平面图与着色问题平面图与着色问题3 3网络流图及其优化问题网络流图及其优化问题4 45 5特殊图模型的应用特殊图模型的应用2022-7-23计算机应用技术研究所计算机应用技术研究所78网络流图及其优化网络流图及其优化问题问题2022-7-23计算机应用技术研究所计算机应用技术研究所79&网络流图及其优化问题网络流图及其优化问题J流网络与切割流网络与切割4最大流求解算法最大流求解算法2022-7-232022-7-23&流网络与切割流网络与切割2022-7-232022-7-23&可行流可行流2022-7-232022-7-23&例题例题
20、2022-7-232022-7-23&几个概念几个概念2022-7-232022-7-23&最大流问题最大流问题2022-7-232022-7-23&残留网络残留网络2022-7-232022-7-23&例题例题2022-7-232022-7-23&增广路径增广路径2022-7-232022-7-23&切割切割2022-7-232022-7-23&例题例题2022-7-232022-7-23&最大流最小割定理最大流最小割定理2022-7-23计算机应用技术研究所计算机应用技术研究所91&网络流图及其优化问题网络流图及其优化问题4流网络与切割流网络与切割J最大流求解算法最大流求解算法2022-7
21、-232022-7-23&Ford-FulkersonFord-Fulkerson算法算法Ford-Fulkerson算法是一种迭代算法，基本思路如下：首先，对所有结点u,vV令f(u,v)=0。然后，通过迭代的方式不断在残留网络中寻找一个增广路径来增加流值，直到残留网络中不包括增广路径为止。2022-7-232022-7-23&Ford-FulkersonFord-Fulkerson算法算法2022-7-232022-7-23&算法基本过程算法基本过程1）对网络G=V,E 初始化，使f(e)=0，eE；2）给源点s标号(-，)，其它结点均未标号；3）依次选一个未标号的结点，根据其方向进行标号
22、，若当前标号的结点为汇点t，转步骤4），否则转步骤6）；4）选择一条标号过的增流路径进行增流；5）转步骤2）；6）这时得到的f就是最大可行流。2022-7-232022-7-23&例题例题【例】对于如图所示为初始网络G，其中边上的数字表示对应边的容量，下面介绍通过Ford-Fulkerson算法寻找其的最大可行流的具体实现过程2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题2）给源点s标号(-,)，其它结点均未标号。2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例
23、题2022-7-232022-7-23&例题例题6）类似地，按照步骤3再次进行标号。2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题8）同理，再对源点s标号(-，)，其他结点均未标号。2022-7-232022-7-23&例题例题9）按步骤3，再次进行标号。2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题【解】2022-7-2
24、32022-7-23&本章学习内容本章学习内容平面图与着色问题平面图与着色问题3 34 4网络流图及其优化问题网络流图及其优化问题特殊图模型的应用特殊图模型的应用5 52022-7-23计算机应用技术研究所计算机应用技术研究所112特殊图模型的应用特殊图模型的应用2022-7-23计算机应用技术研究所计算机应用技术研究所113&特殊图模型的应用特殊图模型的应用J鼓轮设计问题鼓轮设计问题4最优路线问题最优路线问题4稳定婚配问题稳定婚配问题2022-7-232022-7-23&三位轮鼓三位轮鼓 2022-7-232022-7-23&三位轮鼓三位轮鼓 2022-7-232022-7-23&8 8位布
25、鲁英序列位布鲁英序列2022-7-232022-7-23&四位轮鼓四位轮鼓 2022-7-232022-7-23&四位轮鼓四位轮鼓2022-7-232022-7-23&四位轮鼓四位轮鼓2022-7-232022-7-23&四位轮鼓四位轮鼓 2022-7-23计算机应用技术研究所计算机应用技术研究所121&特殊图模型的应用特殊图模型的应用4鼓轮设计问题鼓轮设计问题J最优路线问题最优路线问题4稳定婚配问题稳定婚配问题2022-7-232022-7-23&最优路线问题最优路线问题如果想在较短的时间内旅游较多的景点，则需要确定一个合理的路线，尽量缩短旅游的路程，使总路程最短。该问题可用哈密顿图模型求解
26、。寻找旅游各个景点近似最佳旅行线路问题就转化为：在给定的加权无向图中，寻找从给定的结点出发，行遍所有结点仅一次再回到该指定的结点，使得总权数最小，即总路程最短。可以运用图论中的最邻近插入法来寻找近似最佳旅游线路和路程。2022-7-232022-7-23&算法步骤算法步骤2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题2022-7-232022-7-23&例题例题在上表所示回路中选取长度最短的两个回路1326751或1675231，其长度均为75。将结点4分别插入上面的两个最短回路，得到如表所示的回路及其长度。在表所示的回路中，选取长度最短的旅程12
27、345761，其长度为125，则该回路就是所求的近似最佳旅游线路2022-7-232022-7-23&货郎担问题货郎担问题遍历多个景点的最短旅游路线问题，其实就是从具有n个结点的无向带权完全图中寻找一条哈密顿回路的问题。如果景点个数较多的时候，比如说几十个或者上百个，则上述算法就非常复杂甚至不可行。这其实是图论中的一个著名问题，通常称之为货郎担问题。因为该问题也可以描述为：某地区共有n个村庄，某售货员从他所在的某个村庄出发，前往其它n-1个村庄一次且恰好一次，最后返回到他所在的村庄，求一条满足上述要求且总路程最短的回路。读者可参阅相关的资料进一步深入学习。2022-7-23计算机应用技术研究所
28、计算机应用技术研究所128&特殊图模型的应用特殊图模型的应用4鼓轮设计问题鼓轮设计问题4最优路线问题最优路线问题J稳定婚配问题稳定婚配问题2022-7-232022-7-23&稳定婚配问题稳定婚配问题2022-7-232022-7-23&稳定婚配问题稳定婚配问题2022-7-232022-7-23&稳定婚配算法稳定婚配算法2022-7-232022-7-23&具体计算过程具体计算过程2022-7-232022-7-23&具体计算过程具体计算过程2）现有自由男士B，C。B当前最佳人选b女士求婚，由于b不是自由的，她把B与当前配偶A做比较，由于A的优先级较高，故拒绝B的求婚，如表所示2022-7-
29、232022-7-23&具体计算过程具体计算过程3）现有自由男士B，C。B向当前最佳人选c女士求婚，由于c是自由的，故c接受。如表所示2022-7-232022-7-23&具体计算过程具体计算过程4）现有自由男士C。C向其当前最佳人选c女士求婚，由于c不是自由的，她把C和当前配偶B做比较，由于B的优先级较高，故拒绝C的求婚。如表所示2022-7-232022-7-23&具体计算过程具体计算过程5）现有自由男士C。C向其当前最佳人选b女士求婚，由于b不是自由的，她把C和当前配偶A做比较，由于C的优先级较高，故C替换掉A。如表所示2022-7-232022-7-23&具体计算过程具体计算过程6）现在有自由男士A。A其当前最佳人选a女士求婚，由于a是自由的，所以a接受了。如表所示2022-7-232022-7-23&证明证明2022-7-232022-7-23计算机应用技术研究所计算机应用技术研究所139139
