欢呼彩虹

文章
3
资源
0
加入时间
3年0月21天

图论 二分图匹配、最大匹配、完美匹配、匈牙利算法

能够解决的问题二分图匹配常常在指派问题的模型出现概念二分图的一个等价定义是:不含有「含奇数条边的环」的图。最大匹配:一个图所有匹配中,所含匹配边数最多的匹配,称为这个图的最大匹配。完美匹配:如果一个图的某个匹配中,所有的顶点都是匹配点,那么它就是一个完美匹配。(并非每个图都存在完美匹配)做法1、用匈牙利算法。匈牙利算法是二分图匹配的核心算法,除了二分图多重匹配外均可使用。2、用最...