点の一筆書きを方程式にする
例題
こたえ
上から大文字のZのようにたどる
方程式の解にするべきは？
経路を求めたいということだから、点をつなぐ各線を経路に含むかどうかで表すとやりやすそうですね。
図のようにaからiまでの変数を用意して、経路に含まれるなら１、含まれないなら０が入ることにするよ。
つまり、例えば変数aの定義域は a ∈ [0,1] （0≦a≦1）を満たす整数ということになるよ。
方程式の条件
経路について
点の数は全部で7個。ということは、植木算よろしく経路に含まれる線の数は 7-1= 6 本となるわ。これを式にすると、こんな感じね。
a+b+c+d+e+f+g+h+i = 6
次数制約
出発点と終点につながる線のうち、経路として含まれる線はそれぞれ1本だけだよ。これを式にすると、
a+g = 1, c+i = 1
他の点は、例えばちょうど真ん中の点に注目すると、
この点には3本の線がつながっているけれど、経路をたどってこの点に「入ってくる線」と「出ていく線」があるよね。この点につながる線のうち、経路に含まれる線はちょうど2本ということが言えるわね。
d+e+f= 2
右下の点に注目すると h+i=2 となる
h+i=2 で、hもiも1以下だから、h = i = 1 ということがわかるね。これは、h と i に対応する線が、経路に含まれることを意味するわ。
部分閉路除去制約
でも、これだけでちゃんと理想的な解が得られるかしら？
こんな解が見つかっちゃうかもしれないわよ。
たしかに、道中の点には2本の線が含まれているし、全部の点を一度ずつ通っているけれど、ひとつながりになっていないわ！！
b,d,e のような部分閉路をうまく考えなければならないわね。
このループを作っている３つの点の「集合」を考えてみましょう。
この集合には出発点も終点も入っていないわ。
だから、集合の外から「入ってくる線」と、集合の外に「出ていく線」の2本が経路に含まれているはず。
a+c+f ≧ 2
もしかしたら一筆書きの経路が、もう一度この集合に入ってくるかもしれないから、等号にしないで「2以上」にしておくよ。
さあ式をまとめよう
以上をまとめると、こんな式になるわ！！
a+b+c+d+e+f+g+h+i = 6
a+g = 1, c+i = 1
a+b+d = 2, b+c+e = 2, d+e+f = 2,
g+f+h = 2, h + i = 2
a+c+f ≧ 2
これを、値が決まるところから求めていって、解が得られたら一筆書きができるってことになるわね！
逆にどれか条件を満たせないとなると、一筆書きができないことになるわ！
方程式は、一筆書きの判定にも使えるんだね！
ところでこれは……こんな風にも書けるのよ。
1a+1b+1c+1d+1e+1f+1g+1h+1i = 6
1a+0b+0c+0d+0e+0f+1g+0h+0i = 1
0a+0b+1c+0d+0e+0f+0g+0h+1i = 1
1a+1b+0c+1d+0e+0f+0g+0h+0i = 2
0a+1b+1c+0d+1e+0f+0g+0h+0i = 2
0a+0b+0c+1d+1e+1f+0g+0h+0i = 2
（省略）
a～i の各係数に、0か1がついているね！
しかも全部１次の多項式になっている。これってつまり（数Cとかで習う）行列で表せて、線形方程式にできるってこと。
A = [
1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1
1 1 0 1 0 0 0 0 0
0 1 1 0 1 0 0 0 0
0 0 0 1 1 1 0 0 0
]
および [a b c d e f g h i] の転置を x とすると
Ax = b と表すことができる（ただし b は [6 1 1 2 2 2] の転置）。
これは線形計画法を応用させた整数計画法で解くことができるときがあるよ。私はそこまで専門じゃないけれど、整数計画問題を解くソフトウェアがあるみたいだから、興味があるならまずは「線形計画法」について勉強してみるといいかもね（線形代数学を利用した大学数学です）。
終わりに
本日はここまで。例題を見ると簡単そうに見えるけれど、点の数が多いほど、線の数が多いほど制約は爆発的に増えていってすぐに難しくなっちゃうよ。
行列の話では、文系の皆さんを置いてけぼりにしてしまったけれど、今後は行列のことは話さないから大丈夫です！
次回、ハミルトンパスとハミルトン閉路の親和性について語りたい。
この記事が気に入ったらサポートをしてみませんか？