近似和启发式

优化问题的图性质和启发式函数的近似。

警告

近似子模块不在顶层导入 networkx .

这些函数可以通过 from networkx.algorithms import approximation .

连通性

节点连接的快速近似

all_pairs_node_connectivity (g) [, nbunch, cutoff] ) 计算所有节点对之间的节点连接。
local_node_connectivity \(G,源,目标[, ...] ) 计算源和目标之间的节点连接。
node_connectivity (g) [, s, t] ) 返回图或有向图G的节点连接的近似值。

K分量

K分量结构的快速逼近

k_components (g) [, min_density] ) 返回图G的近似k分量结构。

派系

用于计算大集团的函数。

max_clique (g) 找到最大的集团
clique_removal (g) 重复地从图表中删除组。
large_clique_size (g) 在图表中找出一个大集团的规模。

聚类

average_clustering (g) [, trials, 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) 返回最小基数边缘控制集。

独立集

独立集

独立集或稳定集是一个图中的一组顶点,其中没有两个是相邻的。也就是说,它是一组顶点i,因此对于i中的每两个顶点,都没有边连接这两个顶点。同样地,图中的每个边在i中最多有一个端点。独立集的大小是它包含的顶点数。

最大独立集是给定图G的最大独立集,其大小用α(g)表示。找到这样一个集合的问题称为最大独立集问题,是一个NP硬优化问题。因此,不太可能存在一种有效的算法来寻找图的最大独立集。

Wikipedia: Independent set

独立集算法基于以下论文:

\(O(|V|/(log|V|)^2)\) 最大集团/独立集团的APX。

Boppana,R.和Halld_rsson,M.M.(1992年)。通过排除子图近似最大独立集。位数字数学,32(2),180–196。Springer。doi:10.1007/bf01994876

maximum_independent_set (g) 返回一个近似的最大独立集。

匹配

图匹配

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

Wikipedia: Matching

min_maximal_matching (g) 返回G的最小最大匹配。

拉姆齐

拉姆齐数

ramsey_R2 (g) 近似计算拉姆齐数 R(2;s,t) 用于图形。

斯坦纳树

metric_closure (g) [, weight] ) 返回图的度量闭包。
steiner_tree \(G,终端节点[, weight] ) 返回图形的最小Steiner树的近似值。

树宽

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

无向图的树宽是与图相关联的数字。它可以定义为图的树分解中最大顶点集(包)的大小减去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.Bodlaender。”发现树的宽度”。乌得勒支大学信息与计算科学研究所。技术报告UU-CS-2005-018。网址:http://www.cs.uu.nl
[3]K.Wang、Z.Lu和J.Hicks 树宽 . http://web.eecs.utk.edu/~cphillip/cs594 Spring2015项目/treewidth.pdf
treewidth_min_degree (g) 返回使用最小程度启发式的树宽度分解。
treewidth_min_fill_in (g) 使用最小填充启发式返回树宽度分解。

顶点覆盖

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

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

min_weighted_vertex_cover (g) [, weight] ) 返回一个近似的最小加权顶点覆盖。