組合せとグラフの理論（塩田）第8回 (6) デモ動画、今日のまとめと宿題
デモ動画
mp4 が再生可能なブラウザでご覧ください。
今日のまとめ
- 最短路問題にはダイクストラ法という決定版の高速なアルゴリズムがあります。
- 郵便配達員問題は、グラフがオイラーグラフ・半オイラーグラフのときは高速に解けますが、
奇数次数の頂点が多くなる程解きにくくなります。
- 最小連結子問題にもクラスカル法という高速なアルゴリズムがあります。
- 巡回セールスマン問題には残念ながら高速なアルゴリズムはなく、「ましな解」で満足するのが普通です。
宿題
- ここから download してください。
- 提出期限：6月17日(金)
- 提出方法：スキャンするか写メを撮るなどして、pdf ファイル・画像ファイル等を shiota＠is.kochi-u.ac.jp 宛に送信してください（＠は小文字）。
- 件名に「組合せとグラフの理論第8回の宿題」と書いておいて頂けると有難いです。
- 宿題を複数回分まとめて提出されると見落とす危険があります。１回分ずつ送信してください。