maximal_extendability

maximal_extendability(G)

计算图的扩展性。

图的扩展性定义为使得 G 是 \(k\)-可扩展的最大 \(k\)。图 G 是 \(k\)-可扩展的当且仅当 G 具有完美匹配，并且每个由 \(k\) 条独立边组成的集合都可以扩展到 G 中的完美匹配。

Parameters:

GNetworkX 图

一个没有自环的完全连通二分图

Returns:

extendabilityint

Raises:

NetworkXError

如果图 G 是不连通的。 如果图 G 不是二分图。 如果图 G 不包含完美匹配。 如果图 G 的剩余图不是强连通的。

Notes

定义： 设 G 是一个具有完美匹配 M 和二分划分 (U,V) 的简单、连通、无向和二分图。 G 的剩余图，记为 \(G_M\)，是通过将 M 中的边从 V 指向 U，将不属于 M 的边从 U 指向 V 而得到的图。

引理 [1] ： 设 M 是 G 的完美匹配。 G 是 \(k\)-可扩展的当且仅当其剩余图 \(G_M\) 是强连通的，并且存在 \(k\) 条顶点不相交的有向路径连接 U 和 V 中的每个顶点。

假设输入图 G 是无向、简单、连通、二分且包含完美匹配 M，此函数构造 G 的剩余图 \(G_M\)，并返回 \(G_M\) 中每个顶点 U 和 V 之间的最大顶点不相交有向路径的最小值。结合定义和引理，该值表示图 G 的扩展性。

时间复杂度为 O(\(n^3\) \(m^2\))，其中 \(n\) 是顶点数，\(m\) 是边数。

References

[1]

“A polynomial algorithm for the extendability problem in bipartite graphs”, J. Lakhal, L. Litzler, Information Processing Letters, 1998.

[2]

“On n-extendible graphs”, M. D. Plummer, Discrete Mathematics, 31:201–210, 1980 https://doi.org/10.1016/0012-365X(80)90037-0