networkx.algorithms.coloring.equitable_color

equitable_color(G, num_colors)[源代码]

如果deg(g)<=r,则为o(r*n^2)时间中g的节点提供公平的(r+1)着色。该算法在 1.

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

参数
  • GNetworkX图 )--此图的节点将被着色。

  • num_colors要使用的颜色数 )--此数字必须至少比图中节点的最大程度多一个。

返回

  • 一种字典,其中键表示节点,值表示

  • 相应的颜色。

实际案例

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

NetworkXAlgorithmError -- 如果图的最大度 G 大于 num_colors .

引用

1

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