グラフ彩色問題#
グラフ彩色問題とは、ある制約条件のもとでグラフの要素に色を割り当てる問題です。本チュートリアルでは、隣接する頂点が同じ色にならないように全ての頂点に色を割り当てる問題を通じて、グラフ彩色問題をどのように解くかを説明します。
頂点彩色問題とは#
以下では、隣接する頂点が同じ色にならないように全ての頂点に色を割り当てる頂点彩色問題を考えます。この頂点彩色問題は、下記の図のように解釈することで四色定理を適用することができ、最大でも4つの色で塗り分けれることがわかります。
もし3つの色で頂点が塗り分けられた場合、3-coloringであるといいます。3-coloringで塗り分け可能かどうかを判定する問題はNP完全な問題として有名です。
例#
例として、6つの頂点を持つ次の無向グラフを考えてみましょう。
このグラフは3-coloringです。なぜなら、以下のように3つの色で頂点を塗り分けることで、辺で隣接する頂点同士が異なる色にできるからです。
定式化#
上の例を一般化して数理モデルを定式化してみましょう。無向グラフ \(G=(V, E)\) を \(N\) 色で塗り分けるとします。決定変数 \(x_{v, n}\) は、頂点 \(v\) が色 \(n\) で着彩されている場合に1、そうでない場合に0を取るものとします。
制約: 各頂点は1色で塗らなければならない
以下の式は、各頂点 \(v\) を1色で塗らなければならないことを意味しています。
目的関数: 両端の頂点が同じ色である辺の個数を最小化する
ここで \(E\) はグラフ \(G\) に含まれる辺の集合で、\((uv)\) は頂点 \(u\) と 頂点 \(v\) を両端に持つ辺です。 この目的関数は少々複雑なので、以下の表を参照しながら理解を深めてみましょう。
\(x_{u,n}\) |
\(x_{v,n}\) |
\(x_{u,n}x_{v,n}\) |
|---|---|---|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
\(x_{u, n} u_{v, n}\)が1になるには、\(x_{u, n}\) と \(u_{v, n}\) がともに1である必要があります。 上で定義した通り、\(x_{v, n}\) が1になるのは頂点 \(v\) が色 \(n\) で塗られているときです。そのため、頂点 \(u\) と頂点 \(v\) が同じ色 \(n\) で塗られているときのみ \(x_{u, n} u_{v, n}\) が1になります。このことから、この目的関数は、両端の頂点が同じ色の辺があれば増加し、そのような辺がなければ0になることがわかります。つまり、この目的関数は、隣接する頂点が同じ色にならないようにどれだけ塗り分けられたかを示す指標となっています。
JijModelingによる定式化#
次に、JijModelingを使って上記の数理モデルを実装してみましょう。まずは、数理モデルに現れる変数およびパラメーターを定義します。
import jijmodeling as jm
problem = jm.Problem("Graph Coloring")
V = problem.Natural("V")
E = problem.Graph("E")
N = problem.Natural("N")
x = problem.BinaryVar("x", shape=(V, N))
ここでは V を頂点の数、E をグラフ \(G\) の辺集合、N を色の数として定義しており、\(x_{u,v}\) に相当する2次元のバイナリ変数として x を定義しています。
制約条件の実装#
制約条件として式(1)を実装すると以下のようになります。
problem += problem.Constraint("one-color", lambda v: jm.sum(N, lambda n: x[v, n]) == 1, domain=V)
目的関数の実装#
次に、目的関数として式(2)を実装すると以下のようになります。
problem += jm.sum(jm.product(N, E), lambda n, e: x[e[0], n] * x[e[1], n])
これで数理モデルの実装は完了です。正しく数理モデルが実装されているかをLaTeX表示を通して確認してみましょう。
problem
インスタンスデータの準備#
数理モデルが実装できたので、次はパラメーターに入力するインスタンスデータを準備します。ここでは、NetworkXを使って頂点が12個のグラフをランダム生成するものとします。
import networkx as nx
# set the number of vertices
inst_V = 12
# set the number of colors
inst_N = 4
# create a random graph
inst_G = nx.gnp_random_graph(inst_V, 0.4)
# get information of edges
inst_E = [list(edge) for edge in inst_G.edges]
instance_data = {"V": inst_V, "N": inst_N, "E": inst_E}
inst_V が頂点の個数、inst_N が色の数、inst_E が辺集合のインスタンスデータです。
JijZeptSolverで解く#
この問題をjijzept_solverを用いて解きましょう。
import jijzept_solver
instance = problem.eval(instance_data)
solution = jijzept_solver.solve(instance, solve_limit_sec=1.0)
解の可視化#
最後に、上記で得られた解を用いてグラフの塗り分けを行ってみましょう。以下のコードで塗り分けられたグラフを見ることができます。
import matplotlib.pyplot as plt
df = solution.decision_variables_df
indices = df[df["value"] == 1.0]["subscripts"].to_list()
node_colors = [-1] * len(indices)
colorlist = ["gold", "violet", "limegreen", "darkorange"]
for i, j in indices:
node_colors[i] = colorlist[j]
nx.draw_networkx(inst_G, node_color=node_colors, with_labels=True)
plt.show()
