前へ / 戻る / 次へ

グラフ理論の目標

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

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

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

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

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

他分野との関係

　「もののつながり方」に関わる学問は全てグラフ理論と関係していると言っても過言ではありませんが、特に

• 「データ構造とアルゴリズム」ではデータ構造をグラフで表現してアルゴリズムを記述します。
• 「ネットワーク論」では、ネットワークをグラフで表現してその安定性や安全性を議論します。
• 電気回路の回路図、生物学の系統樹、化学分子の構造などもグラフとして表現されます。

前へ / 戻る / 次へ