離散数学入門#6: オイラーグラフと郵便配達員問題

早稲田大学の全学部の3〜4年生を対象とする全学オープン科目「離散数学入門」（担当教員：早水 桃子）の授業動画です．文理を問わず，誰でもグラフ理論やグラフアルゴリズムの初歩を学ぶことができます．グラフ理論の定理やグラフに関するアルゴリズムを正しく理解して，現実の諸問題を解決するための応用力を身につけましょう． --------------------------------------------------------------------------------------- 全ての辺をちょうど1回ずつ通過して一筆書きで巡回できるグラフをオイラーグラフといい，その一筆書きの巡回経路に相当する回路をオイラー回路といいます．実社会では例えば道路清掃車や除雪車が全ての街路を無駄なく通過する巡回経路を設計したいとき，与えられたグラフがオイラーグラフかどうかを判定する問題や，具体的なオイラー回路を求める問題が現れます．ここではオイラー自身によって示されたオイラーグラフの特徴づけの定理を証明し，さらにオイラー回路を求める方法としてフラーリのアルゴリズムを解説します．また，フラーリのアルゴリズムの応用例として，準オイラーグラフにおける郵便配達員問題（重複して通過する部分の重みが最小で済む巡回経路を求める問題）の解き方も紹介します． 0:00 オープニング 1:15 ２種類の周遊性：辺に対する周遊性と頂点に対する周遊性 6:38 復習：小道（トレイル）と回路（サーキット） 8:38 定義：オイラー回路，オイラーグラフ，オイラー小道，準オイラーグラフ 10:08 オイラーグラフの特徴づけとその証明 ☆証明の中で使われている「最小次数が2以上のグラフには閉路が存在する」の証明は下記 https://youtu.be/6D7BoKrq7hA?t=683 17:55 オイラーグラフの特徴づけ（有向グラフ版） 18:20 準オイラーグラフの特徴づけ 18:58 オイラー回路を求める方法：フラーリのアルゴリズム 22:12 準オイラーグラフの郵便配達員問題（フラーリのアルゴリズムの応用例） ▷ 再生リスト：「離散数学入門」の動画一覧 https://youtube.com/playlist?list=PLCo60G1m_ibpJgfB4WcGwWybC6sfyawoL --------------------------------------------------------------------------------------- ▷ 2021年度 授業シラバス https://www.wsl.waseda.jp/syllabus/JAA104.php?pKey=2602023030012021260202303026&pLng=jp ▷ Twitter（早稲田大学 早水桃子研究室） https://twitter.com/hayamizu_lab ▷ 質問箱 https://peing.net/ja/hayamizu_lab --------------------------------------------------------------------------------------- ▷ 教科書 『例題で学ぶグラフ理論』（安藤 清, 土屋 守正, 松井 泰子 共著）森北出版 https://www.amazon.co.jp/dp/4627052812/ref=cm_sw_r_tw_dp_XY1C405DW1N0ZHG0NF7H ▷ 参考書やアプリなど ・『グラフ理論入門：基本とアルゴリズム』（宮崎 修一 著） 森北出版 https://www.amazon.co.jp/dp/4627852819/ref=cm_sw_r_tw_dp_E85NNF8V37QWSNZ7CC0H ・『グラフ理論入門』（R.J. ウィルソン 著, 西関 隆夫, 西関 裕子 共訳）近代科学社 https://www.amazon.co.jp/dp/4764902966/ref=cm_sw_r_tw_dp_CZH6YAY86MBG5FTHYK2B ・『アルゴリズム図鑑 絵で見てわかる26のアルゴリズム』（石田 保輝, 宮崎 修一 共著）森北出版（iOS/Android 無料アプリ版だと色々なアルゴリズムをアニメーションで学べます．） https://www.amazon.co.jp/dp/4798149772/ref=cm_sw_r_tw_dp_WQP59HC2MYF78CRCG6E5 --------------------------------------------------------------------------------------- 【モデレーターより】 早水研究室の動画を見てくださり誠に有難うございます。当チャンネルの動画は早稲田大学の学生や教員が視聴するものですので、YouTubeのポリシーに反するコメントや教育上の観点から不適切と思われるコメントは、モデレーターの判断で削除する場合がございます。受講生や他の教員に読まれることを想定した上でのコメント投稿をお願い申し上げます。 編集アシスタント：SK