組合せとグラフの理論（塩田）2022年度 第5回
第１回でお話しした「ケーニヒスベルクの橋渡り」にちなんで、
出発点に戻る一筆描きができるグラフをオイラーグラフと呼びます。
一筆描きは単なる遊びに留まらず、
郵便配達の最短経路を求める最適化問題にも関わっています。
前半は、オイラーグラフの判定法や、一筆描きのアルゴリズムについて勉強します。
全ての辺を１回ずつ通って出発点に戻れるのがオイラーグラフであるのに対し、
すべての頂点を１回ずつ通って出発点に戻れるグラフをハミルトングラフと言います。
これは巡回セールスマン問題に関わっています。
後半はハミルトングラフのお話です。