グラフ理論

グラフとは, 点と線(辺)からなる図形である．多数の要素間の結合関係をモデル化する道具として有用である．その応用分野は, 電気回路網の解析, 光学異性体の分類, VLSIの配線設計など多岐に渡る．グラフの各点や各辺に長さや容量といった数量が付加されたものをネットワークという. 数理情報工学においては, 単に数学的対象としてのグラフの諸性質を調べるよりも, むしろ現実の問題をグラフやネットワークを用いてモデル化し, 効率的なアルゴリズムを設計して問題を解決することが重要である. 効率的なアルゴリズムの設計は, 最大流最小カット定理のような自明でない定理を発見し, 証明を与えることと表裏一体の関係にあることが多い.