グラフ・全域木・閉路

グラフ $G=(V,E)$ は有限集合 $V$（頂点）と、各辺 $e\in E$ に二つの相異なる端点を対応させるデータからなる。同じ 2 頂点を結ぶ辺が複数あってもよい（多重辺）が、自己ループは考えない。$|V|=n$、$|E|=m$ と書く。辺の列 $e_1,\dots,e_k$ と頂点の列 $v_0,v_1,\dots,v_k=v_0$ で、$e_j$ が $v_{j-1}$ と $v_j$ を結び、$v_0,\dots,v_{k-1}$ が相異なり、辺も相異なるものを閉路という（多重辺 2 本は長さ 2 の閉路をなす）。閉路を含まない辺集合を森、連結な森を木という。辺集合 $S\subseteq E$ が全頂点を連結する木をなすとき、$S$ を全域木という。