文件名称：最大权匹配-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:29
集训队论文集
5.2 最大权匹配 5.2.1 问题描述 所谓最大权匹配是指让图 G 的每条边 viv j 带上一个权值 wi, j，然后现在我们的目标是 求一个边权和最大的匹配 M。最大匹配相当于边权均为 1的最大权匹配。 5.2.2 算法介绍 我们不妨在每对点之间都连上权值为 0的边，当 n是奇数时我们再新增一个点，并让 它向所有点连边。因此原图的每一个带权匹配都会对应新图的至少一个带权完美匹配，并 且新图的一个带权完美匹配对应了原图的一个带权匹配。 现在我们转化为求新图G′的带权完美匹配。我们新增一个变量 y。设 Ã′(G′)i, j = Ã(G′)i, j× ywi, j。这样我们相当于要求 det Ã′(G′)中，y的最高次数（这个值除以 2就是最大权匹配）。 我们先把所有的 xi, j 赋上一个随机的值。然后设所有边的权值和不超过 W，那么我们 可以将 0到 W 中的每个值代入 y，算一遍行列式，并用这 (W + 1)个结果插值得到一个关 于 y的多项式。那么这个多项式的最高项次数就是我们要求的东西。 这个算法的时间复杂度为 O(Wnω + W2)，在 W 和 n均较小的时候有一定的价值。 6 总结 至此，我们已经能够在O(nω)的复杂度内求出一般图最大匹配的大小，并且在O(n3)的 复杂度内构造出一组匹配方案。 本文所介绍的算法仍旧有着巨大的潜力等待我们去探究，并且本文所介绍的应用还较 为基础。因此我希望本文能够起到抛砖引玉的作用，希望有读者能够拓展本文中的算法， 将这一算法发扬光大，得到更加有趣的应用。 致谢 • 感谢中国计算机学会提供学习和交流的平台； • 感谢宋新波老师，卓明聪老师多年以来的关心和指导； • 感谢国家集训队教练张瑞喆和余林韵的指导； • 感谢周子鑫同学与我分享这个算法； • 感谢高闻远同学、武弘勋同学为本文审稿； 25