主题
Search

最大独立边集

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

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

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

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

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

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

参见

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

使用 Wolfram|Alpha 探索

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. "最大独立边集。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/MaximumIndependentEdgeSet.html

学科分类