「グラフ」と聞くとほとんどの方が視覚的に表現された図や曲線を思い浮かべるでしょう。しかし、本講義で教わる内容はそれとは異なります。頂点と辺からなる図形としての側面を意味し、点と線を用いて様々な現象をモデル化して現象の性質や構造を解析することを学びます。
グラフ理論が活用される代表例として、ケーニヒスベルクの七つの橋問題(図1)はご存知でしょうか?詳しい説明は省略しますが、与えられた線図形(グラフ)が一筆書き可能かを判別する問題です。これを解くときに、一つ一つすべてのパターンを判定すると時間がかかってしまいます。しかし、定義を理解し それに当てはめれば簡単に判別できます。
そのほかにも、最大流問題(図2)というものがあります。これは最大の量がゴールに流れるように考える問題で、イベント後の道路から駅までの交通規制に例えられます。
このように、事象の判別や最適な答えを導くことができる興味深い学問です。