max_weight_clique

max_weight_clique(G, weight='weight')

找到图 G 中的最大权重团。

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

Parameters:

GNetworkX 图

无向图

weight字符串或 None, 可选 (默认=’weight’)

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

Returns:

clique列表

最大权重团的节点

weight整数

最大权重团的权重

Notes

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

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

References

[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).