k_edge_augmentation

k_edge_augmentation(G, k, avail=None, weight=None, partial=False)

找到使图 G 达到 k 边连通的边集。

向 G 添加来自增强的边后，除非移除 k 条或更多边，否则 G 将无法被断开。此函数使用最有效的可用函数（取决于 k 的值以及问题是否带权或无权）来搜索可用边的一个最小权子集，该子集能够使 G 达到 k 边连通。通常，寻找 k 边增强是 NP 难问题，因此不保证解是最小的。此外，k 边增强可能不存在。

参数:

GNetworkX 图

一个无向图。

k整数

所需的边连通性

avail字典或由 2 或 3 个元组组成的集合

可用于增强的可用边。

如果未指定，则 G 的补图中的所有边均可用。否则，每个项都是一条可用边（带有可选权重）。

在无权情况下，每个项都是一条边 (u, v)。

在带权情况下，每个项是一个 3 元组 (u, v, d) 或一个字典，其中项为 (u, v): d。第三项 d 可以是一个字典或一个实数。如果 d 是一个字典，则 d[weight] 对应于权重。

weight字符串

如果 avail 是由 3 元组组成的集合，且每个元组中的第三项是一个字典，则使用此键来查找权重。

partial布尔值

如果 partial 为 True 且不存在可行的 k 边增强，则会生成一个部分 k 边增强。将部分增强中的边添加到 G 中，可以最小化 k 边连通分量的数量，并最大化这些分量之间的边连通性。详细信息请参阅 partial_k_edge_augmentation()。

产生:

edge元组

添加到 G 后，将使 G 达到 k 边连通的边。如果 partial 为 False，并且无法做到这一点，则会引发错误。否则，生成的边会形成一个部分增强，它会使 G 中可能的部分达到 k 边连通，并最大化剩余部分之间的连通性。

引发:

NetworkXUnfeasible

如果 partial 为 False 且不存在 k 边增强。

NetworkXNotImplemented

如果输入图是有向图或多重图。

ValueError

如果 k 小于 1

说明

当 k=1 时，此函数返回最优解。

当 k=2 且 avail 为 None 时，此函数返回最优解。否则当 k=2 时，此函数返回最优解的 2 近似解。

对于 k>3，此问题是 NP 难问题，本函数使用随机算法

生成一个可行解，但不保证解的权重。

示例

>>> # Unweighted cases
>>> G = nx.path_graph((1, 2, 3, 4))
>>> G.add_node(5)
>>> sorted(nx.k_edge_augmentation(G, k=1))
[(1, 5)]
>>> sorted(nx.k_edge_augmentation(G, k=2))
[(1, 5), (5, 4)]
>>> sorted(nx.k_edge_augmentation(G, k=3))
[(1, 4), (1, 5), (2, 5), (3, 5), (4, 5)]
>>> complement = list(nx.k_edge_augmentation(G, k=5, partial=True))
>>> G.add_edges_from(complement)
>>> nx.edge_connectivity(G)
4

>>> # Weighted cases
>>> G = nx.path_graph((1, 2, 3, 4))
>>> G.add_node(5)
>>> # avail can be a tuple with a dict
>>> avail = [(1, 5, {"weight": 11}), (2, 5, {"weight": 10})]
>>> sorted(nx.k_edge_augmentation(G, k=1, avail=avail, weight="weight"))
[(2, 5)]
>>> # or avail can be a 3-tuple with a real number
>>> avail = [(1, 5, 11), (2, 5, 10), (4, 3, 1), (4, 5, 51)]
>>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail))
[(1, 5), (2, 5), (4, 5)]
>>> # or avail can be a dict
>>> avail = {(1, 5): 11, (2, 5): 10, (4, 3): 1, (4, 5): 51}
>>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail))
[(1, 5), (2, 5), (4, 5)]
>>> # If augmentation is infeasible, then a partial solution can be found
>>> avail = {(1, 5): 11}
>>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail, partial=True))
[(1, 5)]