ホーム > libalgo

有名かもしれない事実

最大流-最小カット定理

フローネットワークで $s-t$ 最大流と最小カットは等しい.

DAGの最小パス被覆

DAGの頂点 $v$ を $v, v’$ に分裂させ辺 $(u,v)$ が存在するなら $u_i \to v_i’$ に流量 $1$ の辺を張る.$n - ( \{ v _i \}, \{ v _i’ \}$ の二部マッチング) 本のパスで DAG を被覆できる.

行列木定理

無向グラフ $G$ のラプラシアン行列 $A$ を, $a_{ij} = $ 頂点 $i$ の次数 ($i=j$), $v_i-v_j$ 間の辺の数 $(i \neq j)$ で定義する. $A$ の $n$ 行 $n$ 列を削ってできる $(n-1)\times(n-1)$ 行列の $\det$ は $G$ の全域木の個数に等しい.

特に木のとき $n^{n-2}$ 個.

参考 グラフと線形代数

全域木への分解の可能性判定

無向グラフに Disjointな $k$ 個の全域木が存在する $\iff$ 任意の頂点の $r$ 分割に対して,異なる集合間を結ぶ辺が $k(r-1)$ 個以上存在する

証明 A short proof of the tree-packing theorem