[理学]图论简介.ppt

此算法不是好算法: 这是由于回路的数量是相当多且不易有哪些信誉好的足球投注网站. 在这之后, Edmonds和Johnson(1973)用边无关集的方法给出了一个好算法. 不再详述. 三、Hamilton问题 仅就Hamilton图的判定问题就没有找到较好的充分必要条件, 因此相应的好的算法也不存在. 下面罗列两个必要条件和几个充分条件: 定理6: 若G为Hamilton图, 则对V的任意非空子集S, 都有 ?(G–S) ? |S|. 定理5: 若G为Hamilton图, 则G是2-(度点)连通的. 定理7: G为简单图, 且|V| = n ?3, 若?(G) ? n/2, 则图G是Hamilton图. 定理8: G为简单图, 且|V| = n ?3, 若对任意不相邻两点u,v?V, 都有d(u)+d(v) ? n, 则图G是Hamilton图. 定理9: G为2-(度点)连通的简单图, 且|V| = n ?3, 若对任意点u, v?V, d(u, v)=2, 都有max{d(u), d(v)} ? n/2, 则图G是Hamilton图. 货郎担问题仅有枚举法是最优算法(已经证明). §5 匹配(边无关集) 定义: 设图G=(V, E), M?E, 若M中的所有边都不相邻, 则称M为G的一个匹配(或边无关集). 若v?V是M中某边的结点, 则称v为关于M的饱和点,否则称v为M的非饱和点. 若G中的每一个点都是M的饱和点, 则称M为G的完美匹配. 对于匹配M, 若G中没有匹配M?, 使得| M? | | M |, 则称M为G的最大匹配. 显然, 完美匹配一定是最大最大匹配. 反之不然. 设M为G的匹配, G中关于M的交错路, 是指其边在E–M 和M中交错出现的路. 可扩(增广)路是指其起点和终点都是M的非饱和点的关于M的交错路. 定理: G的匹配M是最大匹配当且仅当G中不含M的可扩路. 由此定理可知: 若要寻找图G的一最大匹配, 关键是寻找当前匹配M的可扩路. 若找到一条可扩路P, 则M?=E(P)?M为G的一个匹配且|M? | | M | +1. 当对某一个匹配M*, 若其没有可扩路, 即M*为G的一个最大匹配. 寻找匹配M的可扩路算法是解决最大匹配算法的要点. 对一般图来说, 寻找匹配有一些理论上的难度, 但这些理论问题已经研究解决. 我们仅就应用中最常见的情况——二部图的匹配问题描述一个好算法. 设二部图G=(X, Y; E), M为G的一个匹配, 由于可扩路的长度为奇数, 则G中若存在M的可扩路,则它的两个端点x, y必属于不同的结点集, 即x?X, y?Y. 寻找M的可扩路算法: 第0步: 令X(0)={ x?X | x是关于M的非饱和点}, 若X0=φ, 则终止, 即M为G的最大匹配. 否则, 取v0?X(0). 第1步: 对于vi ?X(k). 若 vi ?X(k)∩X时, 在V–X(k)中选与vi相邻的所有点(与其关联的边都是非M边). 若无边可选, 则对v0?X(0)的有哪些信誉好的足球投注网站终止. 若 vi ?X(k)∩Y 时, 当vi为非饱和点时, 则找到从v0到vi的可扩路P, 令M?=E(P)?M, 返回第0步; 当vi为饱和点时, 在V–X(k)中选与vi相邻于M的点vj. 第2步: 将新选的点vj 加入X(k),得X(k+1). 返回第1步. 这一算法是一种树状结构“生长”. 匈牙利树的特点为有奇数个点, 且仅有一个非饱和点. 在以上算法过程中对某一个 v0?X(0). 所产生的树有以下三种情况: (1)以v0为根的树还可以生长; (2)找到以v0为根的树中的一条可扩路; (3)既不可生长, 又没有可扩路——匈牙利树, 终止. 当进行到某一步无点可选时, 则当前匹配为最大. 以上生长过程是由X中的所有非饱和点为根生长出的树, 称为匈牙利树. v1 v2 v3 v4 v5 v6 u1 u2 u3 u4 u5 u6 考察图G=(X, Y, E), 其中X={u1, u2, u3, u4, u5, u6}, Y={v1, v2, v3, v4, v5, v6}. 并给出图G的一个匹配M={u2v4, u3v1, u4v3, u6v5} X(0)={u1, u5} 对于u1所关联的边有u1v1, u