グラフ理論との関連

ウィキペディア小見出し辞書

グラフ理論との関連

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/09 03:10 UTC 版)

「一筆書き」の記事における「グラフ理論との関連」の解説

1736年、レオンハルト・オイラーは、この問題を以下のグラフに置き換えて考えた。 → このグラフが一筆書き可能であれば、ケーニヒスベルクの橋を全て1度ずつ通って戻ってくるルートが存在することになる。 そして、オイラーは、このグラフが一筆書きできないことを証明し、ケーニヒスベルクの問題を否定的に解決した。