用户名
给定一个两边图，它们的边X和Y大小相等，我们如何才能有效地找到必须添加的最小边数，以使图具有完美的匹配度？有没有比遍历所有2 ^（| X |）个子集并增加边直到满足Hall定理更好的解决方案？
谢谢。
编码器
如果我正确理解了该问题，则可以通过使用所谓的匈牙利方法或将模型化作为网络流量问题来有效地生成初始图的基数最大匹配。一旦找到最大基数匹配，则任一分区中必须有相等数量的不匹配节点，可以随意使用其他边进行匹配。
换句话说，如果M原始图中的基数最大匹配的基数|X|=|Y|保持不变，则至少M-|X|必须添加边缘以使图中包含完美匹配。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
我来说两句