前へ / 戻る / 次へ

グラフ理論の目標

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

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

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

本講義の内容

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

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

おまけ：サイコロパズル

　次の図は、５つのマークを各面に描いた５個のサイコロを１列に並べて、


どの側面にも５つのマークが揃っているようにせよ、というパズルです。

 
このパズルもグラフを用いて解くことができ、 その解き方が教科書 pp.31-33 に載っています。

前へ / 戻る / 次へ