引用本文: | 谢政.二部图的(g,f)匹配[J].国防科技大学学报,1991,13(3):73-78.[点击复制] |
Xie Zheng.(g,f)-Matchings of Bipartite Graphs[J].Journal of National University of Defense Technology,1991,13(3):73-78[点击复制] |
|
|
|
本文已被:浏览 5265次 下载 5072次 |
二部图的(g,f)匹配 |
谢政 |
(系统工程与应用数学系)
|
摘要: |
本文证明了二部图存在(g,f)匹配和 f 因子的充要条件以及有关的几个结果,并且给出了求二部图的最大(g,f)匹配、最小(g,f)匹配和最小权最大 f 匹配、最小权(g,f)匹配、最大权(g,f)匹配的算法。 |
关键词: 运筹学,图论,网络流,算法,二部图,(g,f)匹配,f 因子 |
DOI: |
投稿日期:1990-03-22 |
基金项目: |
|
(g,f)-Matchings of Bipartite Graphs |
Xie Zheng |
(Department of Applied Mathematics and System Engineering)
|
Abstract: |
In this paper,the sufficient and necessary condition of the existence theorems for (g,f)-matchings and f-factors of bipartite graphs and several related results are proved. We give the algorithms to solve the maximum (g,f)-matching,the minimum (g,f)-matching,the minimum weighted maximum f-matching,the minimum weighted (g,f)-matching and the maximum weighted (g,f)-matching of bipartite graphs. |
Keywords: operations research,graph theory,network flows,algorithms,bipatite graphs,(g,f)-matchings,f-factors. |
|
|
|
|
|