近似和启发式

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

警告

近似子模块不在顶层导入 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的最大独立集,其大小表示为 \(\alpha(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] )

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