前へ / 戻る / 次へ

グラフ理論の目標

　「７つの橋渡り」や「地図の塗り分け」のように、「もののつながり方」に関係する問題を

• グラフとして表現し、
• グラフ理論の定理やグラフ・アルゴリズムを用いて解く

ことがグラフ理論の大きな目標のひとつです。

本講義の内容

　この授業では次のような問題を扱ってゆきます。

• 一筆描き
• 彩色問題 ... 地図の塗り分け、スケジュール調整、レジスタの割り付け等に応用される
• 探索 ... データ構造の基本的なアルゴリズム
• 最短路問題 ... カーナビや 高速道路のルート検索 で必須のアルゴリズム
• 巡回セールスマン問題 ... 全ての顧客を訪問する最短コースを求める問題
• 郵便配達員問題 ... 全ての道路を通る最短コースを求める問題
• 平面性の問題 ... 電子回路設計に応用される
• 連結度 ... ネットワークの安全性に関わる問題
• ネットワーク・フロー ... ネットワークの通信容量等を測る問題
• マッチング ... 相性のいいペアを沢山作る問題 （入退院サポートシステムへの応用例）etc.

前へ / 戻る / 次へ