algorithm - 唯一最大匹配

Question

我正在尝试使用二分图来编写具有以下属性的程序:

1. 每边有N个顶点
2. 图是连通的

现在，我想在我的代码中添加一个条件，检查边的数量是否大于M，不允许用户进行更多事件(用简单的句子在那个条件下打印一些东西)其中 M 是最大边数，这样它仍然具有唯一最大匹配。

问题是我怎样才能找到M？

任何想法将不胜感激 谢谢

Answer 1

如果你的意思是找到最大 m 使得至少有一个具有 n 个顶点和 m 条边的图具有唯一的最大匹配，答案是 (n + 1) * n/2。

为了证明至少有一个图具有这个边数，考虑一个图有顶点 x₁, x₂, .., x _n 在一部分中，顶点 y₁, .. y_n 在另一部分中。在顶点 x_i 和 y_j iff (i <= j) 之间画一条边。

要显示不能再有边，请对顶点数使用归纳法。首先我们可以证明如果图中的每个顶点都连接到至少两个顶点，则该图至少有两个不同的最大匹配。 (考虑一个最大匹配，沿着一条路径从一个顶点开始，该顶点的边在匹配边和非匹配边之间交替，形成一个圆并反转所有边。)

所以我们知道有一个顶点的度数等于一。删除这个顶点和它的邻居并对剩余的图使用归纳法。

抱歉英语不好。