トーナメントグラフの強連結成分について

有向グラフであって，全ての辺の向き付けを取り除いて無向グラフとみなすと完全グラフになるものをトーナメントグラフという．以下では $G=(V,E)$ をトーナメントグラフとして，その性質について述べる．証明についてはどれも冷静に考えたら簡単なので省略する．

性質1. トーナメントグラフを強連結成分分解してできる縮約グラフは 1 本のパスとなる．
性質2. $G$ の強連結成分をトポロジカル順に $V_1, V_2, \ldots, V_k \subseteq V$ とする(性質1からこの順序は一意に定まる)．任意の $1 \le i \lt j \le k$ および $v\in V_i, u\in V_j$ について， $v$ の出次数は $u$ の出次数より大きい．
性質3. $V=\lbrace v_1, v_2, \ldots, v_n\rbrace, 0 \le d_1, d_2, \ldots, d_n \lt n$ とする．このとき頂点 $v_i$ の出次数が $d_i$ であるようなトーナメントグラフ $G=(V, E)$ が存在すれば，その強連結成分分解は一意である． $d_i$ の大きい順から見ていってよしなに処理することでこれを特定することができる．