min_maximal_matching

min_maximal_matching(G)

返回图 G 的最小极大匹配。也就是说，从图 G 的所有极大匹配中，返回最小的一个。

参数：

GNetworkX 图

无向图

返回值：

min_maximal_matching集合

返回一个边集合，其中任意两条边都没有共同的端点，并且集合中不存在的每条边都与集合中的某条边共享一个共同端点。在最坏情况下，基数（大小）将是 2*OPT。

注意

该算法计算最小极大基数匹配问题的近似解。解的大小不超过 2 * OPT。运行时长为 \(O(|E|)\)。

参考文献

[1]

Vazirani, Vijay Approximation Algorithms (2001)