3CNFをグラフGに変換して、最小の頂点被覆を求める
参考
上の2つの参考では、数式でごちゃごちゃ書いていて、一見難しそうに見えるが、図で順番通りに見るとめちゃくちゃ簡単mrsekut.icon
例として以下の3CNFを考える
$ \phi=(x_1\lor x_1\lor x_2)\land(\overline{x_1}\lor\overline{x_2}\lor\overline{x_2})\land(\overline{x_1}\lor x_2\lor x_2)
これは2つの変数$ x_1,x_2と、
(これを$ m=2とする)
3つの節$ (),(),()を
(これを$ l=3とする)
持った論理式だと言える
この$ \phiをグラフ$ Gに変換していく
まずは、変数$ x_1, x_2の方
変数のtrueとfalseを並べて描いて、同じ変数同士を辺で繋ぐ
https://gyazo.com/ada36b258d07880dd0807202b3c65d44
これらを「変数ガジェット」と呼ぶ
次に$ \phiの節を変換
各節ごとに三角形みたいにして描く
https://gyazo.com/5f00e9fa6cdc35e9dad1d7b9313f99f5
今描いた、図の下側のやつを「節ガジェット」と呼ぶ
上と下で同じもの同士を繋ぐ
https://gyazo.com/c6e1313bc2c1c2a41c7c3d71e43e4ef5
終わり！
このグラフ$ Gは、
節点が$ 2m+3l=13個で
$ k=m+2l=8個が、このグラフ$ Gの、最小の頂点被覆のサイズになる
では、どこを頂点被覆にするか
まず、今回の$ \phiは$ x_1=0,x_2=1のときのみ充足するので、これに付いて考える
↑これは自分で求めないといけない
というか、本来は求まっている前提でこのノート全ての話は進んでいる
まず、変数ガジェットで真のリテラルになるやつを頂点被覆に選ぶ
ここでは、$ \overline{x_1},x_2=1になるので、これらを塗りつぶす
https://gyazo.com/56bdedfd6264a6bfa99cd674a130da55
変数ガジェットで頂点被覆に含まれるのは変数の個数分だけってことだねmrsekut.icon
次に、$ \phi=(x_1\lor x_1\lor x_2)\land(\overline{x_1}\lor\overline{x_2}\lor\overline{x_2})\land(\overline{x_1}\lor x_2\lor x_2) の節ごとに見る
節の中で真のリテラルになるやつを選ぶ
一つずつ見ていこう
$ (x_1\lor x_1\lor x_2)では、$ 0\lor0\lor1のときに真
$ (\overline{x_1}\lor\overline{x_2}\lor\overline{x_2}) では、$ 1\lor0\lor0のときに真
$ (\overline{x_1}\lor x_2\lor x_2)では、$ 1\lor1\lor1のときに真
それぞれに$ x_1=0,x_2=1を代入しただけ。
この時、真になっているやつを1つ選んだ後、それ以外のものを2つ選んで塗りつぶす
$ (x_1\lor x_1\lor x_2)では、$ x_1,x_1のみ
$ (\overline{x_1}\lor\overline{x_2}\lor\overline{x_2}) では、$ \overline{x_2},\overline{x_2}のみ
$ (\overline{x_1}\lor x_2\lor x_2)では、全て真なので、どれでも良いから2つ選べばいい
今回は適当に$ \overline{x_1},x_2を選んでみよう
$ x_2,x_2でも問題はないmrsekut.icon
https://gyazo.com/b3486da9608163d78242116c28c06107
この8点が$ Gの最小の頂点被覆である
変数ガジェットも、
節ガジェットも、
変数ガジェットと節ガジェットの間の辺も、
全て被覆されている