グラフ理論

有限で離散的な対象なので一見全ての場合を尽くすことでコンピュータでの解析ができそう

有限離散的対象の構造理解が必要

グラフ理論は、有限離散的対象の構造を理解するための学問である

TOC

グラフの基礎概念

木と探索アルゴリズム

木とは

木と最小全域木

根付き木とBFS(幅優先探索)アルゴリズム

向きづけとDFS(深さ優先探索)アルゴリズム

重み最小の経路

周遊性

オイラーグラフとハミルトングラフについて

オイラーグラフと郵便配達員問題

ハミルトングラフと巡回セールスマン問題

ネットワークフローと最大流問題

ネットワークとは

ネットワークの基礎概念

最大流アルゴリズム

マッチング

マッチングとは

最大マッチング

2部グラフのマッチング

平面的グラフ

幾何学的にグラフを捉える

平面的グラフ

多面体グラフと厚さ

用語集