組合せとグラフの理論（塩田）第8回 (6) デモ動画、今日のまとめと宿題
デモ動画
mp4 が再生可能なブラウザでご覧ください。
今日のまとめ
- 最短路問題にはダイクストラ法という決定版の高速なアルゴリズムがあります。
- 郵便配達員問題は、グラフがオイラーグラフ・半オイラーグラフのときは高速に解けますが、
奇数次数の頂点が多くなる程解きにくくなります。
- 最小連結子問題にもクラスカル法という高速なアルゴリズムがあります。
- 巡回セールスマン問題には残念ながら高速なアルゴリズムはなく、「ましな解」で満足するのが普通です。
宿題
- 授業時間に紙媒体で配布しますが、pdf もここから download できます。
- 提出方法：スキャンしたり写メを撮ったり、pdf を編集したりして、pdf ファイル・画像ファイル等を送信してください。
- 宛先は shiota＠is.kochi-u.ac.jp（＠は小文字）
- 件名は、組合せとグラフの理論第8回の宿題 [自分の学籍番号]
- 上手く送れない人はメールで連絡してください。
- 提出期限：6月14日(金) 10:30am