グラフグラフ, 有向グラフ, 閉路, 最小値, BFS, ベルマンフォード法, ダイクストラ法

アルゴリズム

最小コストの閉路:

任意の辺 e = (u,v) について以下を繰り返すグラフ G から e を取り除く
v から u への最短経路 d を求める(ダイクストラ/BFS など)
d+cost(u, ...

2020年3月30日グラフグラフ, 重み付きグラフ

任意の2頂点間の最短距離を求める問題を全点対最短経路問題といいます。

ワーシャル・フロイド法は、動的計画法を用いて全点対最短経路を求める有名なアルゴリズムです。

負の辺が含まれていても動作する
負の閉路がある場 ...

グラフグラフ, 貪欲法, 最小全域木, プリム法

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木(Spanning Tree) と言います。

\(T\) は木
\(T\) では\(V\) の任意の ...

グラフグラフ, 貪欲法, クラスカル法, 最小全域木

無向グラフ \(G=(V,E)\) について、\(G\) の部分グラフ \(T\) が以下を満たす時、\(T\) は全域木(Spanning Tree) と言います。

\(T\) は木
\(T\) では\(V\) の任意の ...

2020年3月20日グラフ幅優先探索, グラフ, 深さ優先探索, 連結成分, Union-Find, 連結成分のサイズ, 同じ連結成分か判定

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

グラフ \(G=(V,E)\) 上の2頂点 \(u,v\) が同じ連結成分に属しているか判定するアルゴリズムについてです。 ...

グラフ幅優先探索, グラフ, 深さ優先探索, 連結成分, 連結成分の数

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

連結成分は3つアルゴリズム

グラフ \(G=(V,E)\) の連結成分の個数を数えるアルゴリズム:

「未探索」 ...

グラフ競プロ, フロー, 最大フロー, Ford-Fulkerson, フローネットワーク, 最大フロー・最小カット定理, カット, 最小カット

アルゴリズム

最小カットの容量を求めるアルゴリズム:

フローネットワーク \(G=(V,E)\) の最大フロー \(f^*\) の値 \(|f^*|\) を求める
\(|f^*|\) が最小カットの容量

...

グラフ競プロ, フロー, 最大フロー, 二部グラフ, 最大マッチング, マッチング

アルゴリズム

二部グラフの最大マッチングを求めるアルゴリズム:

二部グラフ \(G=(L \cup R, E)\) に対応する以下のようなフローネットワーク \(G’\) を作る\(G\) にソース \(s\) ...

2020年3月19日グラフ競プロ, フロー, 最大フロー, Ford-Fulkerson, フローネットワーク, 最大フロー・最小カット定理

アルゴリズム

最大フローを求めるアルゴリズム(Ford-Fullkerson法):

フロー \(f\) を 0 としてはじめる
ソース(入口) からシンク(出口)までの増加可能経路 \(p\) が残余ネットワーク \ ...

グラフフロー, フローネットワーク, 用語・定義

フローフローとフローネットワーク

関数 \(f : V×V \rightarrow \mathbb{R}\)で表現されるフローは、以下の特徴を持つ重み付き有向グラフ(フローネットワーク) \(G=(V,E)\) 上で定義されます。