ケーニッヒスベルクの橋
グラフ理論
の有名な問題
ノードとそれを結ぶ辺があるとする
ノードは何度も訪れて良いが、辺は1度のみ通れる
つまり
一筆書き
問題
4つの地区と7つの橋からなる
ケーニッヒスベルクの橋
を一筆書きの順路で辿れるかどうか?という問題
一筆書きが可能である条件(判定方法)
始点と終点が同じ場合
始点・終点から伸びる辺が奇数個、かつそれ以外の辺が偶数個ある
始点と終点が異なる場合
各ノードから伸びる辺がそれぞれ偶数個ずつある
参考
https://suwaru.tokyo/%E3%80%90グラフ理論%E3%80%91ケーニヒスベルクの橋を解説%EF%BC%81%E3%80%90/
https://math.cs.kitami-it.ac.jp/~fuchino/chubu/lecture-07-06-13.pdf