最小边覆盖

最小边覆盖是对于给定图，具有最小可能边数的边覆盖。图的最小边覆盖的大小被称为图的边覆盖数，记为。

每个最小边覆盖都是一个极小边覆盖（即，不是任何其他边覆盖的真子集），但反之不一定成立。

只有没有孤立点的图才具有边覆盖（以及因此的最小边覆盖）。

图的最小边覆盖可以使用Wolfram 语言计算，使用FindEdgeCover[g]。目前没有 Wolfram 语言 函数来计算图的所有最小边覆盖。

如果图没有孤立点，则

其中 是匹配数， 是的顶点数（Gallai 1959，West 2000）。