数学:算法:二分图匹配
二分图匹配
-
「二分图」:点分成两个集合,集合内部的点之间没有边相连
「匹配」:一个边集,其中任意两条边都没有公共顶点
由此可定义:匹配点、匹配边、未匹配点、非匹配边
「最大匹配」:使「匹配」中包含的边的数量尽可能多
显然「最大流算法」是可以的,并且速度不慢
「Hungarian Algorithm」匈牙利算法
「最大权值匹配」:使「匹配」中包含的边的总权值尽可能大
带花树
/var/www/DokuWikiStick/dokuwiki/data/pages/数学/算法/二分图匹配.txt · Last modified: 2024/12/25 16:09 by zhonghui