 コメント ( No.14 ) |
- 日時： 2015/11/04 12:54
- 名前： あれれ
- ヒントです。
町の数が3個の場合、自由度の最大値は2
町の数が4個の場合、自由度の最大値は3
ですので、町の数は4以上と考えてよいです。
自由度を大きくするために道路を増やしていくと、
道路によって平面がいくつかの区画に分割されることになります。
町の数をv、道路の数をe、区画の数をfとすると、
この道路網は頂点がv個、辺がe個、面がf個の多面体と位相同型です。
オイラーの多面体定理により、v-e+f=2です。
(現実には作れない多面体の場合でもこの公式は問題なく使えます)
辺を増やしたときに自由度が減らないのは明らかです。
三角形でない面があれば辺を増やして三角形に分割することができますので、
すべての面は三角形と考えてよいです。
一つの面には3つの辺があり、一つの辺は2つの面に共有されますので、
e=3f/2
です。
自由度がkの場合、一つの頂点に集まる辺はk個以上。
一つの辺には2つの頂点がありますので、
e>=kv/2
です。
これらを使えば自由度の上限が求められると思います。
|
|
FAQ
RSS