組合せとグラフの理論(塩田)第1回 (1) はじめに

はじめに

  • 「組合せとグラフの理論」という講義名ですが、グラフ理論を主にやります。
  • 状況にもよりますが、非同期型オンラインで実施します。
  • Web 教材を読むだけでなく、ノートを作って専門用語や図をたくさん書くことをお奨めします。 手を動かすことで脳もいっぱい働くはずです。
  • 毎回宿題を出します。宿題と試験(または学期末レポート)を合わせて成績を付けます。
  • オリジナルのツールでデモをやります。

他分野との関係

 グラフとは「もののつながり」を表現する概念です。 もののつながりに関わる学問は全てグラフ理論と関係していると言っても過言ではありませんが、特に
  • 「データ構造とアルゴリズム」ではデータ構造をグラフで表現してアルゴリズムを記述します。
  • 「ネットワーク論」では、ネットワークをグラフで表現してその安定性や安全性を議論します。
  • 電気回路の回路図、生物学の系統樹、化学分子の構造などもグラフとして表現されます。
また後に述べるように、日常生活の中の色々な最適化問題がグラフで表現されます。

 次ページではグラフ理論誕生のエピソードをご紹介します。