近似和启发式#

图性质的近似和优化的启发式方法。

警告

这些函数不会导入到的顶层 networkx

可以使用以下命令访问这些功能 networkx.approximation.function_name

可以使用以下工具导入它们 from networkx.algorithms import approximation 或 from networkx.algorithms.approximation import function_name

连通性#

节点连接的快速近似

all_pairs_node_connectivity(G[, nbunch, cutoff])

计算所有节点对之间的节点连接。

local_node_connectivity(G, source, target[, ...])

计算源和目标之间的节点连接。

node_connectivity(G[, s, t])

返回图或有向图G的节点连接的近似值。

K分量#

K分量结构的快速逼近

k_components(G[, min_density])

返回图G的近似k分量结构。

派系#

用于计算大型团和最大独立集的函数。

maximum_independent_set(G)

返回一个近似的最大独立集。

max_clique(G)

找到最大的集团

clique_removal(G)

重复地从图表中删除组。

large_clique_size(G)

在图表中找出一个大集团的规模。

聚类#

average_clustering(G[, trials, seed])

估计G的平均聚类系数。

距离测量#

距离度量近似于度量。

diameter(G[, seed])

返回图G的直径的下界。

支配集#

用于查找节点和边缘控制集的函数。

A dominating set 对于无向图 G 顶点集 V 边集 E 是子集 D 属于 V 使每个顶点不在 D 与至少一个成员相邻 D . 安 edge dominating set 是子集 F 属于 E 使每一个边缘不在 F 在中至少有一个边缘的终结点 F .

min_weighted_dominating_set(G[, weight])

返回一个近似最小权重节点控制集的控制集。

min_edge_dominating_set(G)

返回最小基数边缘控制集。

匹配#

给定图g=（v，e），匹配的m in g是一组成对的非相邻边，也就是说，没有两个边共享一个公共顶点。

Wikipedia: Matching

min_maximal_matching(G)

返回G的最小最大匹配。

拉姆齐#

拉姆齐数

ramsey_R2(G)

计算最大团和最大独立集 G .

斯坦纳树#

metric_closure(G[, weight])

返回图的度量闭包。

steiner_tree(G, terminal_nodes[, weight])

返回图形的最小Steiner树的近似值。

旅行推销员#

旅行商问题(TSP)#

实现了求解和逼近TSP问题的近似算法。

实施的算法类别：

  • Christofides(提供了TSP的3/2近似)

  • 贪婪

  • 模拟退火法

  • 阈值接受(TA)

  • Asadour非对称旅行商算法

旅行商问题试图在给定推销员必须访问的所有点之间的权重(距离)的情况下，找出路线，以便：

  • 推销员旅行的总距离(成本)是最小的。

  • 推销员又回到了起点。

  • 请注意，对于完整的图表，推销员访问每个点一次。

该函数 travelling_salesman_problem 通过寻找所有对的最短路径来允许不完全图，从而有效地将问题转化为完全图问题。它调用该问题的一个近似方法，然后使用以前找到的最短路径将结果转换回原始图形。

TSP问题是组合优化中的NP-Hard问题，在运筹学和理论计算机科学中具有重要意义。

http://en.wikipedia.org/wiki/Travelling_salesman_problem

christofides(G[, weight, tree])

旅行商问题的一种近似解

traveling_salesman_problem(G[, weight, ...])

在中查找最短路径 G 正在连接指定的节点

greedy_tsp(G[, weight, source])

从以下位置开始返回低成本周期 source 以及它的成本。

simulated_annealing_tsp(G, init_cycle[, ...])

返回旅行商问题的近似解。

threshold_accepting_tsp(G, init_cycle[, ...])

返回旅行商问题的近似解。

asadpour_atsp(G[, weight, seed, source])

返回旅行商问题的近似解。

树宽#

用于计算树宽分解的函数。

无向图的树宽是与图相关联的数字。它可以定义为图的树分解中最大顶点集（包）的大小减去1。

Wikipedia: Treewidth

树宽和树分解的概念已经获得了它们的吸引力，部分原因是当输入图的树宽被常数限制时，许多在任意图上难以解决的图和网络问题(例如，NP-Hard)变得有效地可解(例如，使用线性时间算法 [1] [2] 。

计算树分解有两种不同的功能： treewidth_min_degree() 和 treewidth_min_fill_in() .

1

Hans L.Bodlaender和Arie M.C.A.Koster。2010。树宽度计算，即上界”。计算机。208，3（2010年3月），259-275.http://dx.doi.org/10.1016/j.ic.2009.03.008

2

汉斯·L·博德兰德。”发现树维特”。乌得勒支大学信息与计算科学研究所。技术报告UU-CS-2005-018。http://www.cs.uu.nl

3

王建国，吕振中，J.希克斯 树宽 。Https://web.archive.org/web/20210507025929/http://web.eecs.utk.edu/~cphill25/cs594_spring2015_projects/treewidth.pdf

treewidth_min_degree(G)

返回使用最小程度启发式的树宽度分解。

treewidth_min_fill_in(G)

使用最小填充启发式返回树宽度分解。

顶点覆盖#

用于计算近似最小重量顶点覆盖的函数。

A vertex cover 是节点的子集，这样图中的每个边都与该子集中的至少一个节点关联。

min_weighted_vertex_cover(G[, weight])

返回一个近似的最小加权顶点覆盖。

最大切割#

randomized_partitioning(G[, seed, p, weight])

计算图节点及其割值的随机分区。

one_exchange(G[, initial_cut, seed, weight])

计算图节点的划分和相应的割值。