例題で学ぶグラフ理論

TOC

グラフの基礎概念

木と探索アルゴリズム

周遊性

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

マッチング

平面的グラフ

Detailed

グラフの基礎概念

グラフ理論とは

基本的な定義

次数

隣接行列

道と閉路

木と探索アルゴリズム

木とは

木と最小全域木

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

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

重み最小の経路

周遊性

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

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

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

ネットワークとは

ネットワークの基礎概念

最大流アルゴリズム

マッチング

マッチングとは

最大マッチング

2部グラフのマッチング

平面的グラフ

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

平面的グラフ

多面体グラフと厚さ