min_maximal_matching

min_maximal_matching(G)

返回图 G 的最小极大匹配。即，在图 G 的所有极大匹配中，返回最小的匹配。

Parameters:

GNetworkX 图

无向图

Returns:

min_maximal_matching集合

返回一组边，其中任意两条边不共享公共端点，并且集合外的每条边都与集合内的某些边共享公共端点。在最坏情况下，基数将为 2 * OPT。

Notes

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

References

[1]

Vazirani, Vijay 近似算法 (2001)