書記が数学やるだけ#610 根付き木と向きづけの性質

根付き木と向きづけの性質は，アルゴリズムの基礎として重要である。

問題

説明

正則木については，内点の数と葉の数が決まっている。

グラフに向きをつけられるか。

有向グラフの例としてトーナメントを挙げておく。

解答

正則木は，トーナメント戦を考えるとわかりやすい。

この強連結な向きづけ可能な必要十分条件のことをロビンスの定理ともいう。

本記事のもくじはこちら：