グラフ理論とは

　例えばコンピュータネットワークは計算機を点、 回線を辺と見做すとグラフになります。 ネットワークの設計では データ通信の効率や 安全性（事故が起こった時の予備経路の確保） が問題になりますが、 これらはグラフ理論の言葉に直して考えられます。

　次のような問題はすべてグラフ理論の問題として定式化されます。

1. ひと筆がきの問題

2. 最短路問題：
   　地図上の都市を点、道を辺と考えた時、 ふたつの都市間を結ぶ最短の経路を求める問題です。

3. 郵便配達夫問題：
   　地図上の道を辺と考えた時、 郵便配達夫がすべての道を最低１回以上通って郵便局に帰って来る 最短の経路を求める問題です。

4. 巡回セールスマン問題：
   　家を点、道を辺と考えた時、 セールスマンがすべての家を回る最短の経路を求める問題です。

5. 地図の色の塗り分け問題：
   　国を点、境界線を辺と考えるとグラフ理論の問題になります。 特に平面地図が４色で塗り分けられるという「４色問題」は グラフ理論の手法を用いて解決されました。

6. プリント基盤の設計：
   　電気回路をプリント基盤上に設計するとき、 素子を点、配線を辺と考えると何層の基盤が必要かが グラフ理論を用いて考えられます。