主题
Search

最大独立边集

图 图 G 的独立边集（也称为匹配）是边的子集，使得子集中没有两条边在 G 中共享一个顶点。最大独立边集是给定图的所有独立边集中包含边数最多的独立边集。

可以使用 Wolfram 语言 计算图的最大独立边集，使用命令：FindIndependentEdgeSet[g]。

最大独立边集的大小被称为匹配数或边独立数。

最大独立边集不等同于极大独立边集，极大独立边集仅仅是无法扩展到更大独立边集的独立边集。每个最大独立边集也是一个极大独立边集，但反之则不然。

给定图图的边覆盖，不在覆盖中的所有边定义了一个独立集（Skiena 1990, p. 218）。Gallai (1959) 证明了最小边覆盖的大小加上最大独立边集的大小等于图的顶点数。

花算法可以用于在一般图中找到最大独立边集，而更简单的匈牙利最大匹配算法可以用于二分图。

参见

花算法, 边覆盖, 匈牙利最大匹配算法, 独立数, 独立边集, 匹配数, 极大独立边集, 最大独立集问题, 最大独立顶点集, 完美匹配

使用 探索

WolframAlpha

更多尝试

参考文献

Brualdi, R. A. Introductory Combinatorics, 4th ed. New York: Elsevier, 1997.Cook, W. J.; Cunningham, W. H.; Pulleyblank, W. R.; and Schrijver, A. Combinatorial Optimization. New York: Wiley, 1998.Hopcroft, J. and Karp, R. "二分图中最大匹配的 n^(5/2) 算法。" SIAM J. Comput. 2, 225-231, 1975.Pemmaraju, S. and Skiena, S. "最大独立集。" §7.5.3 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, p. 318, 2003.Skiena, S. "最大独立集。" §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.Zwick, U. "关于二分图和非二分图中最大匹配的讲义。" http://www.cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf. 2009.

请引用为

Weisstein, Eric W. "最大独立边集。" 来自 Web 资源。 https://mathworld.net.cn/MaximumIndependentEdgeSet.html

学科分类