maximal_extendability

maximal_extendability(G)

计算图的可扩展性。

图的可扩展性定义为图 G 是 \(k\)-可扩展的最大值 \(k\)。当且仅当 G 存在完美匹配，并且任何 \(k\) 条独立边的集合都可以扩展成 G 中的完美匹配时，图 G 是 \(k\)-可扩展的。

参数：

GNetworkX 图

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

返回值：

extendabilityint

抛出：

NetworkXError

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

备注

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

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

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

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

参考文献

[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