二分图匹配算法及其应用【开题报告】

开题报告

数学与应用数学 二分图匹配算法及其应用

一、综述本课题国内外研究动态, 说明选题的依据和意义

图的匹配理论简单的说就是使得图G中每两个点之间都有联系. 匹配理论是图论中的一个重要内容, 它在运筹学、系统工程中都有着广泛的应用, 近几十年来, 随着组合数学的迅速发展, 匹配理论成为许多重要理论的基础和源泉. 二分图的最大匹配算法是匹配理论研究的热点之一. KM算法是求最大权匹配的经典算法, 它是在匈牙利算法的进一步提高, 它是解决数学中一类存在性问题的基本工具, 广泛应用于社会、经济、科技、自然等各个领域中. 本文主要研究KM算法的具体原理, 步骤, 以及它一些实际问题中的应用.

图的匹配问题起源于1935年霍尔的“婚姻问题”. KM算法是Kuhn和Munkras分别于1955年和1957年独立提出来的, 他们在研究图论中最大权匹配问题时很巧妙运用KM算法去解决问题.

定义1 图G有三部分所组成

(1) 非空集合V(G), 称为G的结点集, 其成员称为结点或顶点. (2) 集合E(G), 称为G的边集, 其成员称为边.

(3) 函数?G:E(G)?(V(G),V(G)), 称为边和顶点的关联映射. 这里

(V(G),V(G))称为V(G)的偶对集, 其成员偶对形如(u,v), u,v为结点, 它们未必不

同. 当?G(e)?(u,v)时, 称边e关联端点u,v. 当(u,v)用作序偶时

(V(G),V(G))?V(G)?V(G),

e称为有向边, e以u为起点, 以v为终点, 图G称为有向图; 当(u,v)用作无序偶对

时, (u,v)?(v,u), 称e为无向边(或边), 图G称为无向图(或图).

定义2 无向图G??V,E,??称为二分图, 如果有非空集合X,Y使

X?Y?V,XIY?? ,

且对每一e?E, ?(e)?(x,y), x?X,y?Y. 此时常用?V,E,??表示二分图G. 若对X中任一x及Y中的任一y恰有一边e?E, 使?(e)?(x,y), 则称G为完全二分图. 当X?m, Y?n时, 完全二分图G记为Km,n.

定义3 图G的顶点v1到顶点vl的拟路径是指如下顶点与边的序列:

v1,e1v2,e2,v3,?,vl?1,el?1,vl

其中v1,v2,v3,?,vl?1,vl为G的顶点, e1,e2,?,el?1为G的边, 且ei(i?1,2,?,l?1)以

vi及vi?1为端点(对有向图G, ei以vi为起点, 以vi?1为终点). 当ei(i?1,2,?,l?1)各

不相同时, 该拟路径称为路径.

定义4 若M是二分图G?(V,E)的一个匹配. 设从图G中的一个顶点到另一个顶点存在一条路径, 这条路是由属于M的边和不属于M的边P交替出现组成的, 则称这条路为增广路(或称交互树或交错树). 如果增广路的首尾两个顶点不属于M, 则称这条路为可增广路.

定义5 设G??V,E,??为二分图, 当给G赋予映射f:V?W或g:E?W,

W为任意集合、常用实数集及其子集, 此时G为赋权图, 常用?V,E,?,f?或

?V,E,?,g?或?V,E,?,f,g?表示之. f(v)称为结点v的权, g(e)称为e的权.

定义6 设G??X,E,Y?为二分图, M?E. 称M为G的一个匹配, 如果M中任何两条边都没有公共端点. G的所有匹配中边数最多的匹配称为最大匹配, 其边数称为匹配数. 如果X(Y)中任一顶点均为匹配M中边的端点, 那么称M为X(Y)—完全匹配. 若M既是X—完全匹配又是Y—完全匹配, 则称M为G的完全匹配.

定义7 设二分图G??X,E,Y?, 其中X=Y=匹配数, E中每条边(Xi,Yj)有权Wi,j?0, 若能找到一个匹配M(M=匹配数), 满足所有匹配的边权和最大(或最小), 则称M为G的一个最大(或最小)权匹配.

定义8 称图中顶点u到v是可达的, 如果u?v, 或者有一条u到v的路径. 如果G的任何两个顶点都是互相可达的, 称无向图G是连通的. 如果G?是G的子图,

G?是连通的, 并且不存在G的真子图G??, 使G??是连通的, 且G??以G?为真子图, 则

图G?称为图G的连通分支.

定理1(霍尔定理) 设图G??X,E,Y?. G有X—完全匹配的充分必要条件是: 对每一S?X, 其中N(S)为S的邻域, 即N(S)?vi?S?N(v), 则有

iN(S)?S.

定理2(Tutte定理) 一个图G有完全匹配当且仅当对图G的任意顶点子集S有图G?S的奇分支数不大于S中的顶点数, 其中G?S表示从图G中删去顶点集S及其关联的边所得的图, 图的奇分支是指奇数个顶点的连通分支.

定理3 若由二分图中所有满足Xi?Yj?Wi,j的边(i,j)构成的子图(称做相等子图)有完全匹配, 那么这个完全匹配就是二分图的最大权匹配.

刘桂真[1]对二分图最大权匹配开讨论, 介绍了二分图最大权匹配并将匹配问题从“婚姻问题”推广到工作分派问题.

耿素云[2]通过对二分图的匹配及带权图的应用进行了讨论也将其运用到实际中, 并以此解决了最短路径问题、关键路径问题以及中国邮递员问题.

杨胜超、张瑞军[3]将在介绍毕业论文选题系统的系统用例、功能模块、和流程图的基础上, 针对学生选题不均衡这一突出问题, 引出了二分图最大权匹配的经典算法—KM算法, 该算法能够根据学生的题目预选、自命题、未定题等多种情况, 完成题目与学生的智能匹配, 使最终题目的整体满意度最高, 从而提高学生毕业论文选题质量. 该系统在武汉科技大学管理学院04级毕业论文选题中实施.

谢政、程浩光[4]利用赋双权的二分图中求关于第一个权最大的限制下、第二个权最小的完美匹配的网络模型，给出了这一模型的有效性，并用此算法解决了企业的优化组合分工中的挖潜问题.

彭宇新, Ngo Chong-Wah, 肖建国[5]利用尝试将二分图的最大权匹配用于镜头检索. 把两个镜头的相似度度量建模为一个带权的二分图: 镜头中的每一帧看成二分图的一个结点, 两个镜头之间任意帧的相似值作为边的权值. 在一一对应的前提下, 利用最大权匹配的KM算法求出该二分图的最大权, 以此作为两个镜头的相似度. 考虑到检索的速度的问题, 提出了两个改进算法.

对于二分图最大权匹配的算法有不少, 如: 顶点标记法等. 但KM算法是求解二分图最大权匹配的经典算法. 本文主要研究用KM算法解决二分图最大权匹配的步骤过程及二分图