k_edge_augmentation

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

查找k-edge-connect g的边集。

如果不去除k或更多的边，将边从增广添加到g，则不可能断开g。此函数使用最有效的可用函数（取决于k的值，如果问题是加权的或未加权的）来搜索k-edge连接g的可用边的最小权重子集。通常，找到k-edge增强是NP困难的，因此解决方案不会浪费到最小。此外，K边增广可能不存在。

参数

G网络X图表

无向图。

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，则在不可能的情况下引发错误。否则，生成的边形成部分增强，它k-边连接G的任何可能的部分，并最大限度地连接其余部分。

加薪

NetworkXUnfeasible

如果部分是假的，并且不存在k边增强。

NetworkXNotImplemented

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

ValueError：

如果k小于1

笔记

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

当k＝2时 avail 如果为“无”，则返回最佳解。否则，当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)]