离2-图论2012.ppt

* 例 有4个教师和5个班级，教学要求矩阵P和一张课表如下，现只有3个教室，要求优化课表。 * * * * 上课 * * * * * * * * 并？ * * * 货郎担问题 这个问题可化归为如下的图论问题。 设G＝V,E,W，为一个n阶完全带权图Kn，各边的权非负，且有的边的权可能为∞。求G中一条最短的哈密顿回路，这就是货郎担问题的数学模型。 * 例 例 下图为4阶完全带权图K4。求出它的不同的哈密顿回路，并指出最短的哈密顿回路。 * 带权图的说明 n阶完全带权图中共存在(n-1)!/2种不同的哈密顿回路，经过比较，可找出最短哈密顿回路。 n＝4时， 有3种不同哈密顿回路。n＝5时， 有12种，n＝6时， 有60种，n＝7时， 有360种，…，n＝10时，有5×9!=1 814 400种，…。 * TSP相关算法 最邻近法 以v1为起点，形成初始路径P1＝v1. 若已访问了k个顶点，形成路径pk=v1v2…vk,下一步访问Pk之外离vk最近的顶点。 当访问完G中所有顶点后，回到v1得H回路。 * TSP问题 例14.12 abdeca (48,最坏情况） aedbca(41)baedcb (36，最好情况） a b c d e 9 5 16 9 5 5 8 12 7 8 * TSP相关算法 例： 00 * TSP相关算法 最小生成树法 求G的一棵最小生成树T。 将T中各边均添加一条权值相同的平行边，得图G* 求G*中以某点v出发的欧拉回路E。 从v出发沿E访问G*中各顶点，其原则是：在未访问完所有顶点之前，一旦出现重复的顶点就跳过它走到下一个顶点（抄近路法），直到访问完所有顶点为止，得H回路。作为近似解 * TSP相关算法 从b出发：E回:bcbaeadab 得H圈：bcaedb(41)E回： baeadabcb 得H圈：baedcb(36最优) a b c d e 9 5 16 9 5 5 8 12 7 8 * TSP相关算法 定理14.16 设G中各边权值满足三角不等式，d0是最短H回路，d是由最小生成树法求出的回路，则d 2d0。 * TSP相关算法 最小权匹配法 求G的一棵最小生成树T。 设T中奇度点集合为V’,求出G[V’]的最小完美匹配M，令G*＝T∪M 求G*中以某点v出发的欧拉回路E。 从v出发沿E访问G*中各顶点，其原则是：在未访问完所有顶点之前，一旦出现重复的顶点就跳过它走到下一个顶点（抄近路法），直到访问完所有顶点为止，得H回路。作为近似解 * TSP相关算法 T中奇度点集V’={a,c,d,e}，最小权匹配M={cd,ae}。 a b c d e 9 5 16 9 5 5 8 12 7 8 a b c d e 9 5 9 5 5 从a出发：E回:aeadcba 得H圈:aedcba(36最优)b出发E回： baeadcb 得H圈：baedcb(36最优) * TSP相关算法 定理14.17 设G中各边权值满足三角不等式，d0是最短H回路，d是由最小生成树法求出的回路，则d 1.5d0。 * 便宜算法 便宜算法 设顶点为1,2,…,n 令S={2,3,…,n};w(1,1)=0;k=1;T=(1,1) 令w(j,t)=min{w(i,k)|i∈S,k∈T}对T中边(t,t1),(t,t2),若 w(j,t1)-w(t,t1)≤ w(j,t2)-w(t,t2)则将j插入到t,t1之间，否则插入到t,t2之间S=S-j，若S=?,结束。 对所有i∈S,令w(i,k)=min(w(i,k),w(i,j)) 转b * 便宜算法 定理 设G中各边权值满足三角不等式，d0是最短H回路，d是由便宜算法求出的回路，则d 2d0。 * 中国邮递员问题 一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局。如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程。 * 学号： 姓名： 实验内容： 实验环境：VC++ 实验过程与结果： xxx问题简介 算法框图 运行结果 分析与总结 完整源程序(交电子档）：0408304xx-xxx 图论与代数实验报告 * 推论 非空二部图有饱和所有最大度点的最大匹配。 推论 任意二部图G的边集可以划分成?(G)个边不交的匹配。 * 相异代表系（SDR）：S≠?，? =（A1,…Am）是S的非空子集组成的簇。将(a1,…am)称为?的一个相异代表系，其中ai?Ai,且两两不同。 将?看成是二部图，{1,2,…m}和S看成二部图的两个顶点集，则相异代表系就是?的一个匹配。 * Hall定理：? =（A1,…Am）是S的非空子集组成的簇, 则?存在SDR iff 对每个正整数k(1≤k≤