4.11. トーナメントに関する練習問題
トーナメントに関する話題は当然これだけではない。[Moon13] では様々な話題が解説されている。これまでに触れていない話題の簡単な紹介として、練習問題をいくつか示す。
次の三つの練習問題は「\(3\)-閉路」の概念を利用する。
トーナメント \(D=\left( V,A\right) \) に含まれる \(3\)-閉路 (\(3\)-cycle) とは、\(V\) に属する頂点からなる三つ組 \(\left( u,v,w\right) \) であって組 \(\left( u,v\right) \), \(\left( v,w\right) \), \(\left( w,u\right) \) が全て \(A\) に属するものを言う。
例えば、例 4.10.4 で示したトーナメントは \(9\) 個の異なる \(3\)-閉路を持つ:
\(D=\left( V,A\right) \) をトーナメントとする。\(n=\left\vert V\right\vert \) および \(\displaystyle m=\sum_{v\in V}\dbinom{\deg^{-}v }{2}\) と定める。
-
\(\displaystyle m=\sum_{v\in V}\dbinom{\deg^{+} v }{2}\) を示せ。
-
\(D\) に含まれる \(3\)-閉路の個数は \(3\left( \dbinom{n}{3}-m\right) \) だと示せ。
次の練習問題では有向グラフ \(D\) における頂点 \(v\) の入次数を \(\deg_{D}^{-}v\) と表記している。
トーナメント \(D\) が \(3\)-閉路 \(\left( u,v,w\right) \) を持つとき、新しいトーナメント \(D_{u,v,w}^{\prime}\) を次のように定める: \(D_{u,v,w}^{\prime}\) の頂点集合は \(D\) の頂点集合と等しい。\(D_{u,v,w}^{\prime}\) の弧集合は \(D\) の弧集合の \(\left( u,v\right) \), \(\left( v,w\right) \), \(\left( w,u\right) \) を \(\left( v,u\right) \), \(\left( w,v\right) \), \(\left( u,w\right) \) に置き換えた集合に等しい。 トーナメント \(D\) から新しいトーナメント \(D_{u,v,w}^{\prime}\) を得る操作を \(3\)-閉路反転 (3-cycle reversal) と呼ぶ。
\(V\) を有限集合、\(E\) と \(F\) を頂点集合が \(V\) のトーナメントとする。\(E\) に施すことで \(F\) が得られる \(3\)-閉路反転の列が存在するのは、任意の \(v \in V\) が \(\deg _{E}^{-}\left( v\right) =\deg_{F}^{-}\left( v\right) \) を満たすとき、かつそのときに限ると示せ。
トーナメント \(D=\left( V,A\right) \) が \(3\)-閉路を持たないとき、\(D\) は推移的 (transitive) と言う。
トーナメント \(D=\left( V,A\right) \) の異なる三頂点 \(u\), \(v\), \(w\) が \(\left( u,v\right) \in A\) と \(\left( v,w\right) \in A\) を満たすとき、新しいトーナメント \(D_{u,v,w}^{\prime\prime}\) を次のように定める: \(D_{u,v,w}^{\prime\prime}\) の頂点集合は \(D\) の頂点集合と等しい。\(D_{u,v,w}^{\prime\prime}\) の辺集合は \(D\) の辺集合の \(\left( u,v\right) \), \(\left( v,w\right) \) を \(\left( v,u\right) \), \(\left( w,v\right) \) に置き合えたものに等しい。トーナメント \(D\) から新しいトーナメント \(D_{u,v,w}^{\prime\prime}\) を得る操作を \(2\)-路反転 (2-path reversal) と呼ぶ。
\(D\) を任意のトーナメントとする。\(D\) を推移的なトーナメントに変換する \(2\)-路反転の列が存在することを示せ。