百足

隣接 2 つ

定数割当 (全て true)

https://scrapbox.io/files/66518d24ac4057001c0707e7.png

隣り合う外側の辺変数を true にできる。しかもそれを無限に繋げられる

定数割当

trivial な例なので他の事例について考える時によく省略する

全て false

https://scrapbox.io/files/665191607e0011001c2f848c.png

外側の辺変数を全て false にできる

この際内側の辺変数が必ず交互に true-false になる

頂点節が4以上の偶数個の場合のみ環にできる

隣が同じ

https://scrapbox.io/files/6652c1f2302a5d001c0bc6c8.png

true - false

https://scrapbox.io/files/665189e775e2f3001ca89e46.png

隣同士の外側の辺変数を true-false にすると、false の隣の外側の辺変数が false になる

隣が違う

https://scrapbox.io/files/6652c3a4e23932001d3a89e6.png

1 つ飛ばして 3 つ

true - X - true

https://scrapbox.io/files/66518a8f9a00cb001c6a9095.png

1つ飛ばして外側の辺変数2つを true にすると、その間の外側の辺変数も true になる

つまり、外側の辺変数を true-false-true と交互にはできない

false - X - false

https://scrapbox.io/files/6652c6db46e753001c371340.png

下2つが OR の関係にある

真ん中の上＝左下 AND 右下

true - X - false

https://scrapbox.io/files/6652c8056b94b2001d4ba9ed.png

https://scrapbox.io/files/66534182b8fa41001d80d403.png

2 つ飛ばして 4 つ

true - X - Y - true

https://scrapbox.io/files/66518b1378ae43001d7a7fbf.png

2つ飛ばして外側の辺変数2つを true にすると、その間の外側の辺変数は同じ値になる

T-F-F-T / T-T-T-T

false - X - Y - false

https://scrapbox.io/files/6652ca5d6b94b2001d4bb432.png

ほぼ any

何の特徴もない

真ん中が true の時は左下右下は true

これ以外の 2 つ組は 1-in-3 sat のルールを守る以外は全組み合わせがある

3 つ飛ばして 5 つ

true - X - Y - Z - true

https://scrapbox.io/files/66518cace08d10001dbd0561.png

3つ飛ばして外側の辺変数 2 つを true にすると、3 つのときのルールで考えれば説明がつくのみが SAT になる

3色

https://scrapbox.io/files/6652db1454b97d001c0ec16f.png

実線が (青, 緑) = (0, 0), (0, 1), (1, 0) のみ (1, 1) は無い

波線が (青, 緑) = (1, 1), (1, 0), (0, 1) のみ (0, 0) は無い