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边增广。

Parameters:

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边连通分量的数量，并最大化这些分量之间的边连通度。详细信息请参阅:func:partial_k_edge_augmentation 。

Yields:

edge元组

一旦添加到G中，将使G成为k边连通的边。如果partial为False且无法实现，则会引发错误。否则，生成的边形成一个部分增广，尽可能地k边连通G的任何部分，并最大限度地连接剩余部分。

Raises:

NetworkXUnfeasible

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

NetworkXNotImplemented

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

ValueError:

如果k小于1

Notes

当k=1时，返回一个最优解。

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

对于k>3，此问题是NP难的，使用随机算法生成一个可行解，但不保证解的权重。

Examples

>>> # 无权重情况
>>> 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

>>> # 加权情况
>>> G = nx.path_graph((1, 2, 3, 4))
>>> G.add_node(5)
>>> # avail可以是一个包含字典的元组
>>> avail = [(1, 5, {"weight": 11}), (2, 5, {"weight": 10})]
>>> sorted(nx.k_edge_augmentation(G, k=1, avail=avail, weight="weight"))
[(2, 5)]
>>> # 或者avail可以是一个包含实数的3元组
>>> 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)]
>>> # 或者avail可以是一个字典
>>> 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)]
>>> # 如果增广不可行，则可以找到一个部分解
>>> avail = {(1, 5): 11}
>>> sorted(nx.k_edge_augmentation(G, k=2, avail=avail, partial=True))
[(1, 5)]