equitable_color

equitable_color(G, num_colors)

如果deg(G)<=r，则在O(r*n^2)时间内为G的节点提供相等的(r+1)-着色。 [1].

尝试使用r颜色为图形着色，其中节点的任何相邻节点都不能与节点本身具有相同的颜色，并且每种颜色的节点数最多相差1个。

参数

G网络X图表

该图的节点将被着色。

num_colors要使用的颜色数量

此数字必须至少比图形中的最大节点度大1。

返回

具有表示节点的键和表示的值的字典

相应的颜色。

加薪

NetworkXAlgorithmError

如果图的最大度 G 大于 num_colors 。

工具书类

1

Kierstead，H.A.、Kostochka，A.V.、Mydlarz，M.和Szemer_di，E.（2010年）。公平着色的快速算法。组合数学，30（2），217-224.

实例

>>> G = nx.cycle_graph(4)
>>> d = nx.coloring.equitable_color(G, num_colors=3)
>>> nx.algorithms.coloring.equitable_coloring.is_equitable(G, d)
True