このページでは、グラフの分割問題と呼ばれるNP困難な問題をイジングモデルで表現する方法について述べます。
問題の定式化 #
無向グラフ \(G = (V, E)\) が与えられます。 ここで \(G\) の頂点数 \(|V| = N\) は偶数であるとしましょう。 \(G\) の頂点集合の大きさの等しい分割 \(R\) と \(V - R\) （ \(|R| = |V-R| = \frac{N}{2}\) ）であって、 \(R\) と \(V-R\) の間を繋ぐ辺数が最も少なくなるようなものは何でしょうか？
なお、この問題の判定問題バージョンはNP完全な問題として知られています。 （無向グラフの頂点集合の大きさの等しい分割であって、それらの間を繋ぐ辺の数が \(k\) 本以下になるようなものが存在するでしょうか？という問題です。）
問題の具体例 #
以下の図の左のようなグラフ
\(G = (V, E)\)
を考えます。
\(|V|=8\)
であるので、
\(|R|=4\)
であるような集合
\(R\)
を決めた時の
\(R\)
と
\(V-R\)
の間を繋ぐ辺数の最小値を求めます。この問題の答えは以下の図の右側のような分割になり、最小値2を得ます。
イジングモデルへの変形 #
この問題を解くイジングモデルのエネルギー関数は以下のように構築されます。
まず、グラフの各頂点 \(v \in V\) についてイジングスピン変数 \(s_v = \pm 1\) を設定しましょう。 また、ある２つの正の定数 \(A > 0, B>0\) を取りましょう。 するとエネルギー関数は、 \[ H = H_A + H_B = A \left( \sum_{v \in V} s_v \right)^2 + B \sum_{(uv) \in E} \frac{1 - s_u s_v}{2} \] と記述されます。 ただし、以降の記述の簡便さのためにエネルギー関数の第1項と第2項をそれぞれ \(H_A, H_B\) と置いています。
エネルギー関数の最小化によりグラフの分割問題が解けるのは何故か #
先ほど定義したエネルギー関数を最小化することで、本当にグラフの分割問題が解けているのでしょうか？ これは次のようにして確かめることができます。
エネルギー関数が最小化されたとします。
このとき、 \(H_A\) はなるべく \(0\) に近くなっているでしょう。 理想的には \(0\) になっていることが期待されます。 この時、 \(s_v = +1\) である頂点の部分集合を \(R\) 、 \(s_v = -1\) である頂点の部分集合を \(V - R\) とすると \(R\) と \(V-R\) は大きさの等しい頂点集合の分割になっています。
また、この時 \(H_B\) もなるべく \(0\) に近くなっています。 \(H_B\) の和を構成する各項 \(\displaystyle \frac{1 - s_u s_v}{2}\) は、無向グラフ \(G\) の各辺について定義されていますが、 この値は以下のように変化します。
\[ \begin{aligned} \frac{1 - s_u s_v}{2} = \begin{cases} 0 & (s_u = s_v)\ 1 & (s_u \neq s_v) \end{cases} \end{aligned} \]\(s_u = s_v\) ということは頂点 \(u\) と \(v\) は同じ部分集合に入っているということですし、逆に \(s_u \neq s_v\) ということは、頂点 \(u\) と \(v\) は異なる部分集合に入っているということです。 すなわち、間に辺が存在する頂点どうしに対して、それらが異なる部分集合に属してしまうことに大きさ \(B\) のペナルティを課しているみなすことができます。 したがって、 \(H_B\) を \(0\) に近くなるよう最小化することは、 \(R\) と \(V-R\) の間の辺の数を最小化することに対応します。 こうして、エネルギー関数の最小化を行うことでグラフの分割問題が解けるのです。
おまけ #
-
エネルギー関数を最小化して得られた解は”縮退（degeneracy）”しています。 というのも、 \(s_i = +1\) である方を \(R\) ととっても良いし、逆に \(s_i=-1\) である方を \(R\) ととっても構いません。 つまり、二つの基底状態が一つの解を表してしまっています。 しかし、これは \(n\) 個のイジングスピン変数のうち一つを決め打つことで回避できるので大した問題ではありません。
-
\(B\) の値はペナルティの大きさですから、当然正の値として取る必要があります。ではどの程度大きく取ればよいのでしょうか？ 文献1によれば、以下のように \(A\) と \(B\) の値を取るとよいとのことです。 \[ \frac{A}{B} \ge \frac{\min (2 \Delta, N)}{8} \] ただし、 \(\Delta\) とは無向グラフ \(G\) の最大の次数とします。