---

グラフ理論について

---

木の定義と二部グラフ

• 木は必ず二部グラフである
  • 二部グラフとは２色塗り分け問題に対応しているということ
  • 二部グラフの塗り分けはdfs等で深さのパリティを取れば良い
• 二部グラフの性質の詳細

---

閉路の性質

• 概要
  • 有向グラフGに最短路が存在するとき必ず、閉路は通らない
    • 負閉路を通るときは無限に通ることでコストを下げられる
    • 正閉路を遠ならなければコストを上げないので通らないほうがいい
  • これはダイクストラ法とベルマンフォード法の根拠にもなっている

\(f_v\)を最小のコストとしたとき以下が成り立つ

\[f_v \leq f_u + d_e, e=(v, u) \in E\]

---

グラフの辺数を削除

• 概要
  • ナイーブにグラフを連結するとすごい数になってしまう時、辺の中間に頂点を設けることで計算量を削減することができる
• 参考1
  • 参考図
  • 参考問題
  • 提出

---

dfs(深さ優先探索)

• dfs

---

bfs(幅優先探索)

• bfs

---

ダイクストラ法

• 概要
  • 優先度付きグラフの最短経路を求める際に用いる
    • 優先度の管理をheapを用いることでソートをせずにアクセスできる
  • 計算量は\(O(V^2)\)
• 挙動
  1. ネットワークの最小コストの経路を常に選択する
  2. その時の経路のコストを保存しておく\(f_v\)
  3. ゴール一歩手前の分岐に戻り、次の選択肢を走査する\(f_s\)
  4. \(f_v = f_s\)と更新
  5. 走査する経路がなくなるまでやる
• コードと詳細な説明

---

ワーシャルフロイド法

• 概要
  • 閉路があっても使える。
    • 計算量が多いがすべての経路を三重ループを用いることで最小コストを与える
    • ダイクストラを個別に用いるより効率が良い
• コードと詳細な説明
• 参考
  • 素人によるワーシャルフロイド法

---

フォードファルカーソンアルゴリズム

• 概要
  • コストがある有向グラフにて、最大の運送量を求めるもの
• 挙動
  1. ネットワークをDFSで一つ時最小コストを一つ見る
  2. 差分ネットワークという逆向きのグラフを作り、抵抗する力を定義する
  3. 捜査するネットワークに差分ネットワークを考慮した上で1に戻る
• コードと詳細な説明