分水界はいくつまでできる？
- 平面をk個の海岸線に分ける
- 分水界を「どの海岸線とどの海岸線とを分けるか」で数えるとき、行く通りにまで増やせるか？
- 最大値は
で上に抑えられている
- １点から星形に分けるときには
通りに分けられるから、これ以上にはできる
- さて。
- 分水界をどんどん分けていくと、２分岐木になるから、２分岐木の辺の数に相当する
- 一般に、木は、頂点の数
に対して、辺の数は
- この場合の頂点は「葉」と呼ばれる端の頂点と、「節」と呼ばれる、端ではない頂点との合わせたものである
- 分水界を考えるとき、「葉」の数が
- では、葉の数が
- 葉をトーナメントのチームとして考えよう。試合の数は、チーム数-1
- したがって、節の数は
- ただし、この場合は、「決勝戦」に節頂点を与えている
- 分水界の場合には、「決勝戦」はいらない(
の場合は、葉が２つで節は０、辺が１にしたい)
- したがって、葉の数
。頂点数は
- 辺の数は頂点数より１小さいから、辺の数は
