摘要
本文给出了一个多部图的商匹配问题的定义,提出了求解多部图商匹配问题的一个算法。该算法使用圈与割集中偶图的交相结合的方法,利用求二部图的最大匹配算法,求解多部图的最大商匹配问题。
This paper defines the quotient matching problems of multi-partite graphs, and puts forward an algorithm that solves the maximum quotient matching problem of the multi-partite graphs. This algorithm uses the bipartite graph joining in circle and cut of multi-partite graphs, and utilizes one of the maximum matching problem algorithm of bipartite graphs to find a maximum quotient matching of multi-partite graphs.
出处
《计算机工程与科学》
CSCD
北大核心
2009年第9期36-38,70,共4页
Computer Engineering & Science
基金
海南省自然科学基金资助项目(80636)
海南省教育厅资助项目(Hjkj200705)
关键词
多部图
匹配问题
商匹配
multi-partite graphs
matching problems
quotient matching
