1、图论模型1.图论基本概念图论基本概念2.最短路径算法最短路径算法3.最小生成树算法最小生成树算法4.遍历性问题遍历性问题5.二分图与匹配二分图与匹配26.网络流问题网络流问题7.关键路径问题关键路径问题8.系统监控模型系统监控模型9.着色模型着色模型1 1、图论的基本概念、图论的基本概念问题问题1(1(哥尼斯堡七桥哥尼斯堡七桥问题问题):): 能否从任一陆地出发通过每座桥恰好一次而能否从任一陆地出发通过每座桥恰好一次而回到出发点？回到出发点？34欧拉指出：欧拉指出： 如果每块陆地所连接的桥都是偶数座，则从任一如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地
2、陆地出发，必能通过每座桥恰好一次而回到出发地. .5问题问题2(2(哈密顿环球旅行哈密顿环球旅行问题问题):): 十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，个城市，能否从某个城市出发在十二面体上依次经过每个能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？城市恰好一次最后回到出发点？欧拉问题是欧拉问题是“边遍历边遍历”，哈密尔顿问题是，哈密尔顿问题是“点遍历点遍历”6问题问题3(3(四色问题四色问题):): 对任何一张地图进行着色，两个共同边界的国家染不同的颜对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了色，
3、则只需要四种颜色就够了. .问题问题4(4(关键路径问题关键路径问题):): 一项工程任务一项工程任务, ,大到建造一座大坝大到建造一座大坝, ,一座体育中心一座体育中心, ,小至组装小至组装一台机床一台机床, ,一架电视机一架电视机, , 都要包括许多工序都要包括许多工序. .这些工序相互约束这些工序相互约束, ,只有在某些工序完成之后只有在某些工序完成之后, , 一个工序才能开始一个工序才能开始. . 即它们之间存在即它们之间存在完成的先后次序关系完成的先后次序关系, ,一般认为这些关系是预知的一般认为这些关系是预知的, , 而且也能够而且也能够预计完成每个工序所需要的时间预计完成每个工序
4、所需要的时间. . 这时工程领导人员迫切希望了解最少需要多少时间才能够完这时工程领导人员迫切希望了解最少需要多少时间才能够完成整个工程项目成整个工程项目, , 影响工程进度的要害工序是哪几个？影响工程进度的要害工序是哪几个？ 图的定义 图论中的图论中的“图图”并不是通常意义下的几何图形或物体的形并不是通常意义下的几何图形或物体的形状图状图, , 而是以一种抽象的形式来表达一些确定的事物之间的联而是以一种抽象的形式来表达一些确定的事物之间的联系的一个数学系统系的一个数学系统. . 定义定义1 一个有序二元组一个有序二元组(V, E ) 称为一个称为一个图图, 记为记为G = (V, E ), 其
5、中其中 V称为称为G的顶点集的顶点集, V , 其元素称为其元素称为顶点顶点或或结点结点, 简称简称点点; E称为称为G的边集的边集, 其元素称为其元素称为边边, 它联结它联结V 中的两个点中的两个点, 如如果这两个点是无序的果这两个点是无序的, 则称该边为则称该边为无向边无向边, 否则否则, 称为称为有向边有向边. 如果如果V = v1, v2, , vn是有限非空点集是有限非空点集, 则称则称G为为有限图有限图或或n阶图阶图. 8 如果如果E的每一条边都是无向边的每一条边都是无向边, 则称则称G为为无向图无向图( (如图如图1)1); 如如果果E的每一条边都是有向边的每一条边都是有向边,
6、则称则称G为为有向图有向图( (如图如图2)2); 否则否则, 称称G为为混合图混合图. 图图1 1 图图2 2并且常记并且常记: : V = v1, v2, , vn, |V | = n ;E = e1, e2, , em(ek=vivj ) , |E | = m.称点称点vi , vj为边为边vivj的的端点端点. 在有向图中在有向图中, 称点称点vi , vj分别为边分别为边vivj的的始点始点和和终点终点. 该图称为该图称为(n,m)图图9 对于一个图对于一个图G = (V, E ), 人们常用图形来表示它人们常用图形来表示它, 称称其为其为图解图解. 凡是有向边凡是有向边, 在图解上
7、都用箭头标明其方向在图解上都用箭头标明其方向. 例如例如, 设设V = v1 , v2 , v3 , v4, E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 则则G = (V, E ) 是一个有是一个有4个顶点和个顶点和6条边的图条边的图, G的图解如下图所示的图解如下图所示. 10 一个图会有许多外形不同的图解一个图会有许多外形不同的图解, , 下面两个图表示同一个图下面两个图表示同一个图G = (V, E )的图解的图解. .这两个图互为这两个图互为同构图同构图, ,今后将不计较这种外形今后将不计较这种外形上的差别上的差别, ,而用一个容易理解的、
8、确定的图解去表示一个图而用一个容易理解的、确定的图解去表示一个图. . 11 有边联结的两个点称为有边联结的两个点称为相邻的点相邻的点, 有一个公共端点的边称为有一个公共端点的边称为相相邻边邻边. 边和它的端点称为边和它的端点称为互相关联互相关联. 常用常用d(v)表示图表示图G中与顶点中与顶点v关联关联的边的数目的边的数目, d(v)称为顶点称为顶点v的的度数度数. 对于有向图对于有向图,还有还有出度出度和和入度入度之之分分. 用用N(v)表示图表示图G中所有与顶点中所有与顶点v相邻的顶点的集合相邻的顶点的集合. d(v1)= d(v3)= d(v4)=4, d(v2)=2dout(v1)=
9、 dout (v3)= dout (v4)=2, dout(v2)=1din(v1)= din(v3)= din(v4)=2, din(v2)=112握手定理握手定理：无向图中，所有结点的度数之和等于2m。右图：推论1：无向图中必有偶数个度数为奇数的结点。推论2：有向图中所有结点的出度之和等于入度之和。d(v1)= d(v3)= d(v4)=4, d(v2)=2mvdnii2)(1147*2)(1niivd我们今后只讨论有限简单图： (1) (1) 顶点个数是有限的顶点个数是有限的; (2) (2) 任意一条边有且只有两个不同的点与它相互关联任意一条边有且只有两个不同的点与它相互关联; (3)
10、 (3) 若是无向图若是无向图, , 则任意两个顶点最多只有一条边与之相则任意两个顶点最多只有一条边与之相联结联结; (4) (4) 若是有向图若是有向图, , 则任意两个顶点最多只有两条边与之相则任意两个顶点最多只有两条边与之相联结联结. . 当两个顶点有两条边与之相联结时，这两条边的方向当两个顶点有两条边与之相联结时，这两条边的方向相反相反. . 如果某个有限图不满足如果某个有限图不满足(2)(3)(4),(2)(3)(4),可在某条边上增设顶点可在某条边上增设顶点使之满足使之满足. .14 定义定义2 若将图若将图G的每一条边的每一条边e都对应一个实数都对应一个实数F (e), 则称则称
11、F (e)为该边的为该边的权权, 并称图并称图G为为赋权图赋权图(网络网络), 记为记为G = (V, E , F ). 定义定义3 任意两点均有通路的图称为任意两点均有通路的图称为连通图连通图. 定义定义4 连通而无圈的图称为连通而无圈的图称为树树, 常用常用T表示树表示树. 常用的图给定图G= 和 G = 是两个图，如果有 V V 和 E E,则称图G是图 G 的子图。若V =V 称图G是图 G 的生成子图；若将图G的每一条边e都对应一个实数F(e)，则称F(e)为该边的权，并称图G为赋权图(网络), 记为G = 。任意两点均有通路的图称为连通图。连通而无圈的图称为树，常用T=表示树。 若
12、图G是图 G 的生成子图，且G又是一棵树，则称G是图G 的生成树。例 Ramsey问题问题：任何6个人的聚会，其中总会有3个互相认识或3人互相不认识。图论模型：用红、蓝两种颜色对6个顶点的完全图K6的边进行任意着色，则不论如何着色必然都存在一个红色的K3或一个蓝色的K3 。对应关系：每个人即为一个结点；人与人之间的关系即为一条边例 Ramsey问题图论证明：用红、蓝两种颜色对K6的边进行着色，K6的任意一个顶点均有5条边与之相连接，这5条边必有3条边的颜色是相同的，不妨设为蓝色（如图）与这3条边相关联的另外3个节点之间的3条边，若都为红色，则形成红色的K3；若另外3个节点之间的3条边有一条为蓝
13、色，则与上面的蓝色边形成蓝色的K3；因此必然存在一个红色的K3或一个蓝色的K3 。例 Ramsey问题Ramsey数：R（3,3）=6；R（3,4）=9；。18例 过河问题问题：一摆渡人欲将一只狼、一头羊、一篮菜从河西渡过河到河东。由于船小，一次只能带一物过河，并且狼与羊，羊与菜不能独处，给出渡河方法。这里显然不能用一个节点表示一个物体。一个物体可能在河东，也可能在河西，也可能在船上，状态表示不清楚。另外，问题也可以分成几个小问题，如：问题是否能解？有几种不同的解法？最快的解决方案是什么？例 过河问题解：解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1，否则取0)，
14、共有24 =16 种状态。在河东岸的状态类似记作。由题设，状态(0,1,1,0)，(0,0,1,1)，(0,1,1,1)是不允许的；其对应状态：(1,0,0,1)， (1,1,0,0)，(1,0,0,0)也是不允许的。以可允许的以可允许的10个状态向量作为个状态向量作为顶点顶点，将可能互相转移的状，将可能互相转移的状态用态用边边连接起来构成一个图。连接起来构成一个图。利用图论的相关知识即可回答原问题。例 过河问题(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0)(0,0,0,0) (0,0,0,1) (0,0,1,0) (0,1,0,0) (0,
15、1,0,1)(0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0)(1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1)河西河西=(人人,狼狼,羊羊,菜菜) 河东河东=(人人,狼狼,羊羊,菜菜) 将10个顶点分别记为A1, A2, , A10 , 从图中易得到两条路：A1 A6 A3 A7 A2 A8 A5 A10;A1 A6 A3 A9 A4 A8 A5 A10.问题的转换： 过河问题是否能解？即：图中A1到A10是否连通？ 有几种不同的解法？即： A1到A10之间有多少条不同的路径？ 最快的解决方案是什
16、么？即： A1到A10最短路径有哪些？图的矩阵表示图的矩阵表示 邻接矩阵：邻接矩阵：邻接矩阵表示了点与点之间的邻接关邻接矩阵表示了点与点之间的邻接关系系. .一个一个n阶图阶图G的邻接矩阵的邻接矩阵A = (aij )nn , 其中其中 ., 0;, 1EvEvaijijij0101100101001010A2223无向图无向图G的邻接矩阵的邻接矩阵A是一个对称矩阵是一个对称矩阵. . 0101101101011110A 权矩阵权矩阵 一个一个n阶赋权图阶赋权图G = (V, E, F)的权矩阵的权矩阵A = (aij ) nn , 其中其中 .,;0),(EvjiEvvvFaijijjiij
17、有限简单图基本有限简单图基本上可用权矩阵来上可用权矩阵来表示表示. .2405420370860A无向图无向图G的权矩阵的权矩阵A是一个对称矩阵是一个对称矩阵. . 02420737064360A25 关联矩阵：关联矩阵：一个有一个有m条边的条边的n阶有向图阶有向图G的关联的关联矩阵矩阵A = (aij )nm , 其中其中 若若vi是是ej的始点的始点;若若vi是是ej的终点的终点;若若vi与与ej不关联不关联. ., 0, 1, 1ija 有向图的关联矩阵每列的元素中有且仅有一个有向图的关联矩阵每列的元素中有且仅有一个1,1,有且仅有且仅有一个有一个 - - 1. 1. 110110001
18、1011000000111011001A26 一个有一个有m条边的条边的n阶无向图阶无向图G的关联矩阵的关联矩阵A = (aij )nm , 其中其中 若若vi与与ej关联关联;若若vi与与ej不关联不关联. ., 0, 1ija 无向图的关联矩阵每列的元素中有且仅有两个无向图的关联矩阵每列的元素中有且仅有两个1. 1. 110100101010011001000111A2 2、最短路径算法 定义定义1 设设P(u, v) 是赋权图是赋权图G = (V, E , F) 中从点中从点u到到v的路径的路径, 用用E(P) 表示路径表示路径P(u, v)中全部边的集合中全部边的集合, 记记)()()
19、(PEeeFPF则称则称F (P)为路径为路径P(u, v) 的的权权或或长度长度( (距离距离) ). 定义定义2 若若P0 (u, v) 是是G 中连接中连接u, v的路径的路径, 且对任意在且对任意在G 中连中连接接u, v的路径的路径P (u, v)都有都有F (P0)F(P), 则称则称P0 (u, v) 是是G 中连接中连接u, v的的最短路最短路. 重要性质：重要性质： 若若v0 v1 vm 是是图图G中从中从v0到到vm的最短路的最短路, 则则 1km, v0v1 vk 必为必为G中从中从v0到到vk的最短路的最短路. 即：最短路是一条路，且最短路的任一段也是最短路即：最短路是
20、一条路，且最短路的任一段也是最短路. 求非负赋权图求非负赋权图G中某一点到其它各点最短路，一般用中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法算法. . 这两种算法均适用于有向非负赋权图这两种算法均适用于有向非负赋权图. . 下面分别介绍两种算法的基本过程下面分别介绍两种算法的基本过程. .Dijkstra算法指标（a为起点） 设T为V的子集，P=V-T且aT，对所有tT，设 l(t)表示从a到t的所有通路中距离最短的一条的长度，且这条路径中不包含T中其他的结点，则称l(t)为t
21、关于集合P的指标，若不存在这样的路径，这记l(t)= 注：l(t)不一定是从a到t的最短路径，因为最短路径中可能包含T中其他的节点。定理1 若t是T中关于P由最小指标的结点，则l(t)是a和t之间的最短距离。定理2 设 T为V的子集，P=V-T，设 (1)对P中的任一点p,存在一条从a到p的最短路径,这条路径仅有P中的点构成, (2)对于每一点t,它关于P的指标为l(t),令x为最小指标所在的点, 即: (3)令P=P Ux,T=T-x,l(t)表示T中结点t关于P的指标,则 29),()(),(min)( txwxltltlTttlxl),(min)(Dijkstra算法（求a点到其他点的最
22、短路径）1、初始化，、初始化，P=a，T=V-a，对每个结点，对每个结点t计算指标计算指标 l(t)=w(a,t) 2、设、设x为为T中关于中关于P有最小指标的点有最小指标的点, 即即:l(x)=min(l(t) (tT), 3、若、若T=,则算法结束则算法结束; 否则否则,令令P=P Ux,T=T-x 按照公式按照公式l(t)=minl(t),l(x)+w(x,t), 计算计算T中每一个结点中每一个结点t关于关于P的指标的指标. 4、P代替代替P,T代替代替T,重复步骤重复步骤2,3 （ 其中：其中：w(x,y)为图的权矩阵）为图的权矩阵） 30改进Dijkstra算法（求a点到其他点的最短
23、路径）1、初始化，、初始化，P=a，T=V-a，对每个结点，对每个结点t计算指标计算指标 l(t)=w(a,t) ,pro(t)=a;2、设、设x为为T中关于中关于P有最小指标的点有最小指标的点, 即即:l(x)=min(l(t) (tT);3、若、若T=,则算法结束则算法结束; 否则否则,令令P=P Ux,T=T-x 按照公式按照公式l(t)=minl(t),l(x)+w(x,t), 计算计算T中每一个结点中每一个结点t关于关于P的指标的指标. 若若 l(x)+w(x,t) l(t), pro(t)=x;4、P代替代替P,T代替代替T,重复步骤重复步骤2,3 （ 其中：其中：w(x,y)为图
24、的权矩阵）为图的权矩阵） 31例 求下图中A A点到其他点的最短路. .32Floyd算法（求任意两点的最短路径） 设设A = (aij )nn为赋权图为赋权图G = (V, E, F)的权矩阵的权矩阵, dij表表示从示从vi到到vj点的距离点的距离, rij表示从表示从vi到到vj点的最短路中前一个点的最短路中前一个点的编号点的编号. 赋初值赋初值. 对所有对所有i, j, dij = aij, rij = j. k = 1. 转向转向. 更新更新dij , rij . 对所有对所有i, j, 若若dik + dk jdij , 则令则令dij = dik + dkj , rij = k,
25、 转向转向; 终止判断终止判断. 若若k = n终止终止; 否则令否则令k = k + 1, 转向转向. 最短路线可由最短路线可由rij得到得到. 例 求下图中任意两点间的最短路. .3403030350201502051504510500A028338235803065508525035205540150352053015035452510450D533333143333113111133230142212142220R例 设备更新问题 某企业每年年初某企业每年年初, ,都要作出决定都要作出决定, ,如果继续使用旧设备如果继续使用旧设备, ,要付要付维修费；若购买一台新设备维修费；若购买一台
26、新设备, ,要付购买费要付购买费. .试制定一个试制定一个5 5年更新计年更新计划划, ,使总支出最少使总支出最少. . 已知设备在每年年初的购买费分别为已知设备在每年年初的购买费分别为11,11, 12,12,13. 11,11, 12,12,13. 使使用不同时间设备所需的维修费分别为用不同时间设备所需的维修费分别为5,6,8,11,18.5,6,8,11,18. 解解 设设bi 表示设备在第表示设备在第i 年年初的购买费年年初的购买费, ,ci 表示设备使用表示设备使用i 年年后的维修费后的维修费, , V= v1, v2, , v6,点点vi表示第表示第i 年年初购进一台新设备年年初购
27、进一台新设备, ,虚设一个虚设一个点点v6表示第表示第5 5年年底年年底. . E = vivj | 1ij6,每条每条边边vivj表一台设备，从第表一台设备，从第i年年初购买使年年初购买使用到第用到第j年年初报废年年初报废.ijkkijicbvvF1)(36 这样上述设备更新问题就变为：在有向赋权图这样上述设备更新问题就变为：在有向赋权图G = (V, E, F )(图解如下图解如下) )中求中求v1到到v6的最短路问题的最短路问题. 37 由实际问题可知由实际问题可知, ,设备使用三年后应当更新设备使用三年后应当更新, ,因此删因此删除该图中除该图中v1到到v5 , ,v1到到v6 , ,
28、v2到到v6的连线；又设备使用一年的连线；又设备使用一年后就更新则不划算后就更新则不划算, ,因此再删除该图中因此再删除该图中v1v2 , ,v2v3 , ,v3v4 , ,v4v5 , ,v5v6 五条连线后得到五条连线后得到从上图中容易得到从上图中容易得到v1到到v6只有两条路：只有两条路：v1v3v6和和v1v4v6. . 而这两条路都是而这两条路都是v1到到v6的最短路的最短路. .3 3、最小生成树 由树的定义不难知道由树的定义不难知道, 任意一个连通的任意一个连通的(n,m)图图G适当去掉适当去掉m - - n +1条边后条边后, 都可以变成树都可以变成树, 这棵树称为图这棵树称为
29、图G的的生成树生成树. 设设T是图是图G的一棵生成树的一棵生成树, 用用F(T)表示树表示树T中所有边的权数之和中所有边的权数之和, F(T)称为称为树树T的权的权. 一个连通图一个连通图G的生成树一般不止一棵的生成树一般不止一棵, 图图G的所有生成树中权的所有生成树中权数最小的生成树称为图数最小的生成树称为图G的的最小生成树最小生成树-Minimum-cost Spanning Tree (MST). 求最小生成树问题有很广泛的实际应用求最小生成树问题有很广泛的实际应用. 例如例如, 把把n个乡镇用个乡镇用高压电缆连接起来建立一个电网高压电缆连接起来建立一个电网, 使所用的电缆长度之和最短使
30、所用的电缆长度之和最短, 即即费用最小费用最小, 就是一个求最小生成树问题就是一个求最小生成树问题. KruskalKruskal算法39 从未选入树中的边中选取权重最小的且不构成回路从未选入树中的边中选取权重最小的且不构成回路的边加入到树中的边加入到树中. .（判断回路比较麻烦）（判断回路比较麻烦）算法过程：算法过程：1.将各边按权值从小到大进行排序将各边按权值从小到大进行排序2.找出权值最小且找出权值最小且不与已加入最小生成树集合的边构成回路不与已加入最小生成树集合的边构成回路的的边。若符合条件，则加入最小生成树的集合中。不符合条件则边。若符合条件，则加入最小生成树的集合中。不符合条件则继
31、续遍历图，寻找下一个最小权值的边。继续遍历图，寻找下一个最小权值的边。3.递归重复步骤递归重复步骤1，直到找出，直到找出n-1条边为止，得到最小生成树。条边为止，得到最小生成树。时间复杂度时间复杂度只和边有关，可以证明其时间复杂度为只和边有关，可以证明其时间复杂度为O(mlogm)求最小生成树40?2?4?4?2?1?3?7?2?8?6?7?3?B?C?A?F?D?G?E?2?2?1?3?6?3?E?G?D?F?A?C?BPrimPrim算法41 把结点分成两个集合，已加入树中的把结点分成两个集合，已加入树中的( (P P) )和未加入树中的和未加入树中的( (Q Q) )，然后每次选择一个点
32、在然后每次选择一个点在P P中一个点在中一个点在Q Q中的权重最小的边，加入树中的权重最小的边，加入树中，并把相应点加入中，并把相应点加入P P中。中。类似地类似地, ,可定义连通图可定义连通图G 的最大生成树的最大生成树. .算法过程：算法过程：1：初始化：任取一个节点：初始化：任取一个节点u加入生成树加入生成树,P=u0, Q=V-u0, 生成树的边集生成树的边集TE=。2：在所有：在所有uP,vQ的边的边(u,v) （称为可选边集称为可选边集）中，找一条权重最小的）中，找一条权重最小的边边(u1,v1)，将此边加进集合，将此边加进集合TE中，并将中，并将v加入加入P中。同时对与中。同时对
33、与v关联的边，若关联的边，若另一个端点已经在另一个端点已经在P中，则从可选边集中删除，否则加入可选边集。中，则从可选边集中删除，否则加入可选边集。3：如果：如果P=V，则算法结束；否则重复步骤，则算法结束；否则重复步骤2。 我们可以算出当我们可以算出当U=V时，步骤时，步骤2共执行了共执行了n1次，次，TE中也增加了中也增加了n1条条边，这边，这n1条边就是需要求出的最小生成树的边。条边就是需要求出的最小生成树的边。例 选址问题 现准备现准备在在 n 个个居民点居民点v1, v2, , vn中设置一银行中设置一银行. .问问设在哪个点设在哪个点, ,可使最大服务距离最小可使最大服务距离最小?
34、? 若设置两个银行若设置两个银行, ,问设在哪两个点问设在哪两个点? ? 模型假设模型假设 假设各假设各个个居民点都有条件设置银行居民点都有条件设置银行, ,并并有路相连有路相连, ,且路长已知且路长已知. . 模型建立与求解模型建立与求解 用用Floyd算法求出任意两算法求出任意两个个居民居民点点vi , vj 之间的最短距离之间的最短距离, ,并用并用dij 表示表示. . 设置一个银行设置一个银行, ,银行设银行设在在 vi 点点的最大服务距离为的最大服务距离为.,.,2 , 1,max1niddijnji43求求k, ,使使.min1inikdd 即若设置一个银行即若设置一个银行, ,
35、则银行设在则银行设在 vk 点点, ,可使最大服务距离最小可使最大服务距离最小. . 设置两个银行设置两个银行, ,假设银行设假设银行设在在vs , vt 点点使最大服务距离最小使最大服务距离最小. .记记.,minmax),(1jkiknkddjid则则s, ,t 满足：满足：).,(min),(1jidtsdnji进一步进一步, ,若设置多个银行呢？若设置多个银行呢？4 4、遍历性问题一、欧拉图G=(V,E)为一连通无向图经过G中每条边至少一次的回路称为巡回；经过G中每条边正好一次的巡回称为欧拉巡回；存在欧拉巡回的图称为欧拉图。二、中国邮递员问题（CPPchinese?postman?pr
36、oblem）?一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？这一问题是我国管梅谷教授1962年首先提出，国际上称之为中国邮递员问题。?44解法： 若本身就是欧拉图，则直接可以找到一条欧拉巡回就是若本身就是欧拉图，则直接可以找到一条欧拉巡回就是本问题的解。本问题的解。 若不是欧拉图，必定有偶数个奇度数结点，在这些奇度若不是欧拉图，必定有偶数个奇度数结点，在这些奇度数点之间添加一些边，使之变成欧拉图，再找出一个欧数点之间添加一些边，使之变成欧拉图，再找出一个欧拉巡回。拉巡回。具体解法：Fleury算法+Edmond
37、s最小对集算法45三、哈密尔顿图G=(V,E)为一连通无向图经过G中每点一次且正好一次的路径称为哈密尔顿路径；经过G中每点一次且正好一次的回路称为哈密尔顿回路；存在哈密尔顿回路的图称为哈密尔顿图。四、旅行商问题（TSPTraveling?Salesman?Problem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线？ 即：从驻地出发，经过每个城市恰好一次，最后返回驻地（最小哈密尔顿回路）对于n个节点的旅行商问题，n个节点的任意一个全排列都是问题的一个可能解（假设任意两个点之间都有边）。G个节点的全排列有(n-1)!个，因此间题归结为在(n-1)!个回路中选取最小回路
38、。 TSP问题的解法属于NPNP完全问题，一般只研究其近似解法46最邻近算法(1) 选取任意一个点作为起始点,找出与该点相关联的权重最小的边,形成一条初始路径.(2) 找出与最新加入到路径中的点相关联的权重最小的边加入到路径中,且要求不再路径中产生回路.(3) 重复(2)直到所有的结点都加入到路径中.(4) 将起点和最后加入的结点之间的边加入到路径中,形成Hamilton回路.其他数值算法： 人工神经元方法， 遗传算法等等475 5、二分图与匹配 定义定义1 1 设设X, ,Y 都是非空有限集都是非空有限集, ,且且XY = , , E xy| |xX, ,yY, , 称称G =(X, Y,
39、E)为为二部图二部图. . 二部图可认为是有限简单无向图二部图可认为是有限简单无向图. . 如果如果X中的每个点都与中的每个点都与Y中的每个点邻接中的每个点邻接, ,则称则称G =(X, Y, E)为为完备二部图完备二部图. . 若若F：ER + +, ,则称则称G =(X, Y, E, F )为为二部赋权图二部赋权图. . 二部赋权图的权矩阵一般记作二部赋权图的权矩阵一般记作A=(aij )|X|Y | , ,其中其中aij = F (xi yj ). .49 定义定义2 2 设设G =(X, Y, E)为二部图为二部图, ,且且M E. .若若M中任意两条边中任意两条边在在G中均不邻接中均
40、不邻接, ,则称则称M是是二部图二部图G的一个的一个匹配匹配. . 定义定义3 3 设设M是二部图是二部图G的一个匹配的一个匹配, ,如果如果G的每一个点都是的每一个点都是M中边的顶中边的顶点点, ,则称则称M是二部图是二部图G的的完美匹配完美匹配； 如果如果G中没有另外的匹配中没有另外的匹配M0 , ,使使| |M0| | |M|,|,则称则称M是二部图是二部图G的的最大匹配最大匹配. . 在二部赋权图在二部赋权图G =(X, Y, E, F )中中, ,权数最大的最大匹配权数最大的最大匹配M称为称为二部赋权图二部赋权图G的的最佳匹配最佳匹配. . 显然显然, ,每个完美匹配都是最大匹配每个
41、完美匹配都是最大匹配, ,反之不一定成立反之不一定成立. .工作安排问题之一 50 给给n个工作人员个工作人员x1, x2, , xn安排安排n项工作项工作y1, y2, , yn. . n个工作人员中每个人能胜任一项或几项工作个工作人员中每个人能胜任一项或几项工作, 但并但并不是所有不是所有工作人员都能从事任何一项工作工作人员都能从事任何一项工作. 比如比如x1能做能做y1, y2工作工作, x2能能做做y2, y3, y4工作等工作等. 这样便提出一个问题这样便提出一个问题, 对所有的工作人员能不能都分配对所有的工作人员能不能都分配一件他所能胜任的工作？一件他所能胜任的工作？ 我们构造一个
42、二部图我们构造一个二部图G = ( X, Y, E ), 这里这里X = x1, x2, , xn,Y = y1, y2, , yn, 并且当且仅当工作人员并且当且仅当工作人员xi胜任工作胜任工作yj时时, xi与与yj才相邻才相邻. 于是于是, 问题转化为求二部图的一个完美匹配问题转化为求二部图的一个完美匹配. 因为因为 |X|=|Y|, 所以完美匹配即为最大匹配所以完美匹配即为最大匹配. 51 求二部图G = ( X, Y, E )的最大匹配算法( (匈牙利算法, ,交替链算法) )迭代步骤: 从从G的任意匹配的任意匹配M开始开始. . 将将X中中M的所有的所有非饱和点非饱和点都给以标号都
43、给以标号0 0和标记和标记* *, , 转向转向. . M的非饱和点即非的非饱和点即非M的某条边的顶点的某条边的顶点. . 若若X中所有有标号的点都已去掉了标记中所有有标号的点都已去掉了标记* *, , 则则M是是G的最大的最大匹配匹配. . 否则任取否则任取X中一个既有标号又有标记中一个既有标号又有标记* *的点的点xi , , 去掉去掉xi的标的标记记* *, , 转向转向. . 找出在找出在G中所有与中所有与xi邻接的点邻接的点yj , , 若所有这样的若所有这样的yj都已有标都已有标号号, , 则转向则转向, , 否则转向否则转向. .52 对与对与xi邻接且尚未给标号的邻接且尚未给标
44、号的yj都给定标号都给定标号i. . 若所有的若所有的 yj 都是都是M的的饱和点饱和点, ,则转向则转向, ,否则逆向返回否则逆向返回. . 即由即由其中其中M的任一个非饱和点的任一个非饱和点 yj 的标号的标号i 找到找到xi , ,再由再由 xi 的标号的标号k 找到找到 yk , , ,最后由最后由 yt 的标号的标号s找到标号为找到标号为0 0的的xs时结束时结束, ,获得获得M- -增广路增广路xs yt xi yj , , 记记P = xs yt , , xi yj ,重新记重新记M为为M P, ,转向转向. . 不必理会不必理会M- -增广路增广路的定义的定义. . M P =
45、 MP MP, , 是对称差是对称差. . 将将yj在在M中与之邻接的点中与之邻接的点xk , ,给以标号给以标号 j 和标记和标记* *, , 转向转向. .例 求下图所示二部图G的最大匹配53解解 取初始匹配取初始匹配M0 = x2 y2 , x3 y3 , x5 y5 ( (上图粗线所示上图粗线所示). ). 给给X中中M0的两个非饱和点的两个非饱和点x1, ,x4都给以标号都给以标号0 0和标记和标记* * ( (如如下图所示下图所示). ). 去掉去掉x1的标记的标记*, 将与将与x1邻接的两个点邻接的两个点y2, y3都给以标号都给以标号1.1. 因因为为y2, y3都是都是M0的
46、两个饱和点的两个饱和点, ,所以将它们在所以将它们在M0中邻接的两个点中邻接的两个点x2, x3都给以相应的标号和标记都给以相应的标号和标记* (如下图所示如下图所示). 54 去掉去掉x2的标记的标记*, 将与将与x2邻接且尚未给标号的三个点邻接且尚未给标号的三个点y1, y4, y5都给以标号都给以标号2 (如下图所示如下图所示). 因为因为y1是是M0的非饱和点的非饱和点, 所以顺着标号逆向返回依次得到所以顺着标号逆向返回依次得到x2, y2, 直到直到x1为为0为止为止. .于是得到于是得到M0的增广路的增广路x1 y2x2 y1, 记记P = x1 y2 , y2x2 , x2 y1
47、. 取取M1 = M0P = x1 y2 , x2 y1 , x3 y3 , x5 y5, 则则M1是比是比M多一边的匹配多一边的匹配(如下图所示如下图所示). 再给再给X中中M1的非饱和点的非饱和点x4给以标号给以标号0和标记和标记*, 然后去掉然后去掉x4的的标记标记*, 将与将与x4邻接的两个点邻接的两个点y2, y3都给以标号都给以标号4. 因为因为y2, y3都是都是M1的两个饱和点的两个饱和点, , 所以将它们在所以将它们在M1中邻接的两中邻接的两个点个点x1, x3都给以相应的标号和标记都给以相应的标号和标记* (如下图所示如下图所示). 去掉去掉x1的标记的标记*, 因为与因为
48、与x1邻接的两个点邻接的两个点y2, y3都有标号都有标号4, 所所以去掉以去掉x3的标记的标记*. 而与而与x3邻接的两个点邻接的两个点y2, y3也都有标号也都有标号4, 此时此时X中所有有标号中所有有标号的点都已去掉了标记的点都已去掉了标记*(如下图所示如下图所示), 因此因此M1是是G的最大匹配的最大匹配. G不存在饱和不存在饱和X的每个点的匹配的每个点的匹配, 当然也不存在完美匹配当然也不存在完美匹配.工作安排问题之二 56 给给n个工作人员个工作人员x1, x2, , xn安排安排n项工作项工作y1, y2, , yn. . 如如果每个工作人员工作效率不同果每个工作人员工作效率不同
49、, 要求工作分配的同时考虑总效要求工作分配的同时考虑总效率最高率最高. 我们构造一个二部赋权图我们构造一个二部赋权图G = ( X, Y, E , F ), 这里这里X = x1, x2, , xn,Y = y1, y2, , yn, F(xi yj )为工作人员为工作人员xi胜任工作胜任工作yj时的工作效率时的工作效率. 则问题转化为：求二部赋权图则问题转化为：求二部赋权图G的最佳匹配的最佳匹配. 在求在求G 的最佳匹配时的最佳匹配时, 总可以假设总可以假设G为完备二部赋权图为完备二部赋权图. .若若xi与与yj不相邻不相邻, 可令可令F(xi yj )=0. 同样地同样地, 还可虚设点还可
50、虚设点x或或y, ,使使|X|=|Y|. .如此就将如此就将G 转化为完备二部赋权图转化为完备二部赋权图, ,而且不会影响结果而且不会影响结果. 定义定义 设设G =( (X, Y, E, F) )为完备的二部赋权图为完备的二部赋权图, , 若若L：X Y R + + 满足：满足： xX, yY, L(x) + L(y)F(xy), ,则称则称L为为G的一个的一个可行点标记可行点标记, ,记相应的生成子图为记相应的生成子图为GL =( (X, Y, EL , F),),这里这里EL = xyE| |L(x) + L (y) = F (xy). 求完备二部赋权图求完备二部赋权图G = (X, Y
