max_weight_clique

max_weight_clique(G, weight='weight')

在图 G 中查找最大权重团。

图中的团是节点的一个集合，其中任意两个不同的节点都相邻。团的权重是其所有节点的权重之和。图 G 的最大权重团是 G 中的一个团 C，使得 G 中没有其他团的权重大于 C 的权重。

参数:

GNetworkX 图

无向图

weight字符串或 None，可选 (默认值='weight')

用作权重的节点属性，存储整数值。如果为 None，则每个节点的权重为 1。

返回值:

clique列表

最大权重团的节点列表

weight整数

最大权重团的权重

说明

该实现是递归的，因此如果 G 包含一个节点数量接近递归深度限制的团，可能会遇到递归深度问题。

在每个搜索节点，算法会贪婪地构建图一部分的加权独立集覆盖，以便找到一个小的节点集来进行分支。该算法与 Tavares 等人 [1] 的算法非常相似，区别在于 NetworkX 版本不使用位集。这种解决最大权重团（以及最大权重独立集，这是同一个问题但在补图上）的算法风格已有数十年的历史。参见 Warren 和 Hicks [2] 的算法 B 以及该论文中的参考文献。

参考文献

[1]

Tavares, W.A., Neto, M.B.C., Rodrigues, C.D., Michelon, P.: Um algoritmo de branch and bound para o problema da clique máxima ponderada. Proceedings of XLVII SBPO 1 (2015).

[2]

Warren, Jeffrey S, Hicks, Illya V.: Combinatorial Branch-and-Bound for the Maximum Weight Independent Set Problem. Technical Report, Texas A&M University (2016).