Good Will Hunting Problem
マット・デイモンとロビン・ウィリアムズ主演の映画『グッド・ウィル・ハンティング/旅立ち』(Good Will Hunting)の中で、MITの廊下に掲示されたグラフ理論の問題を清掃をしていたマット・デイモンが解いてしまうシーンがあります。 中学生とかのときに初めてこの映画を見たときにはよっぽど難しい問題なんだろうな、と思ったのですが、最近見返してみると定義に従って素直に計算すれば解ける問題だということがわかったのでまとめておきます。
Quote
Given the graph \(G\), find
- The adjacency matrix, \(A\)
- The matrix giving the number of 3 step walks
- The generating function for walks from \(i\to j\)
- The generating function for walks from \(1\to3\)
