グラフ理論と最適化 | 長崎大学 情報データ科学部

学生による講義紹介

科目名
グラフ理論と最適化
講義分類
両コース選択
履修学年
2年生 第1・2クオーター
担当教員
講義の目的

 簡単な最適化問題の解き方を理解し、条件内で最大効率の結果を導く方法を学びます。

講義の内容

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

図1:ケーニヒスベルクの七つの橋問題
図2:最大流問題(図は0-フロー)
講義を受けてみての感想

課題として、その回の要点となる1題を解くのですが、それを解くことで理解でき成長を感じました。グラフの定義から始まり、一見全く別の学問に感じますが、線形代数の行列や情報基礎数学の写像など、前年度の学びが度々活きてつながる楽しさがありました。

教科書・教材・参考書

例題で学ぶグラフ理論(安藤清、土屋守正、松井泰子 共著、森北出版)