最大カット問題

ノードとそれらを任意に繋ぐエッジがある。

https://scrapbox.io/files/667d4caa7df06c001d7b8bfa.png

ここで、エッジを切断する。

https://scrapbox.io/files/667d4d24a77e7f001d0072e6.png

この切断の重みが最大となる切り方を求める。

これは、「エッジ(i,j)を切断するかしないか」(ノードiとノードjを別のグループにするか)のエネルギーを計算することに等しい

/icons/hr.icon

定式化

コストハミルトニアンは以下のように定義される

$ v_i= \begin{cases} 1 \\ -1 \end{cases}

$ H_c=-\frac{1}{2}\sum_{(i,j)\in E} w_{i,j} (1-v_i v_j)

$ v_iと$ v_jが同じグループなら切断しないので、コストは0 ($ w_{i,j}\cdot0=0)

$ v_iと$ v_jが違うグループなら切断するので、コストは$ w_{i,j} ($ w_{i,j} \cdot \frac{1}{2}\cdot2 = w_{i,j})

/icons/hr.icon

疑問点

本当にルールに従って切断できてるの？コストハミルトニアンだけだと、違法な切り方してない？

→違法な切り方をすると、2つのグループに分割するという前提が崩れる。例えば三角形をin,out,inで切ったら、ノードの種類が3つになってしまう。今回のモデルは$ \pm1の二値をとる設計なので、3グループ以上の別れ方をしない。