补图方法在二部图最大匹配中的应用  

The application of the method of complement graph in maximal matching for bipartite graph

作　　者：毛华[1] 史田敏[1] 李斌[1] 

机构地区：[1]河北大学数学与计算机学院,保定071002

出　　处：《黑龙江大学自然科学学报》2012年第3期289-293,共5页Journal of Natural Science of Heilongjiang University

基　　金：保定市科学技术研究项目(11ZG005)

摘　　要：图论中的匹配理论无论是在图论本身还是生产实践中都有着重要的作用,特别是在计算机和网络研究等领域中应用更为广泛和深入。利用补图的思想,关于二部图的最大匹配问题,给出一种新的研究方法,并通过实例说明此方法的实用性和有效性。为解决二部图最大匹配问题开辟了新途径。No matter in the study of graph theory or the real practice, the matching theory in graph theory plays an important role. Especially, in the fields of computer science and web knowledge, the applications are wider and deeper. Applying the knowledge of complement graph, a new research method on the maximal matching for bipartite graph is presented. Additionally, by a concrete instance, it expresses the utility and effectivity of this method. The idea in this method provides a new way for dealing with maximal matching of bipartite graph.

关 键 词：补图 二部图 最大匹配 图论 

分 类 号：O23[理学—运筹学与控制论]