平成30年度 秋期 午前 問6

✓ これが正解エ葉の個数が n ならば，葉以外の節点の個数は n-1 である。

解説

葉以外の節点は葉の個数より必ず1つ少なくなります。

葉以外の節点がすべて二つの子をもち、根から葉までの深さが等しい木構造について、常に成り立つ記述を選ぶ問いです。式のまま眺めるより、小さい木を実際に描いて四つの記述を当てるほうが確実です。いちばん小さい木は、根が一つとその子である葉が二つです。このとき枝は二本、節点は三個、葉は二個、葉以外は一個になります。もう一段深くすると、枝は六本、節点は七個、葉は四個、葉以外は三個です。この二つの例を並べると、葉の個数と葉以外の個数の差がどちらも一であることが見えてきます。これは偶然ではありません。葉以外の節点は必ず二つの子をもつので、この形の木を大きくする手は、葉を一つ選んでそこに子を二つ付けることだけです。その操作をすると、選んだ葉は葉でなくなり子が二つ増えるので葉は差し引き一つ増え、葉以外も一つ増えます。増え方が同じですから、差は最初の一のまま動きません。深さの数え方は設問が定義しています。根から葉に至るまでの枝の本数であって、段数ではありません。見分けの軸は、小さな二例で試してから、なぜそうなるかまで確かめることです。二例で合っただけでは、常に成り立つとは言えません。

ほかの選択肢はなぜ違うのか

• ア枝の個数が n ならば，節点の個数も n…：根だけは親をもたないので、枝の本数は節点の個数よりも必ず一つ少なくなります。最小の木で試すと枝が二本に対して節点が三個で、この時点で一致しません。もう一段深くしても六本と七個でずれたままです。
• イ木の深さが n ならば，葉の個数は 2^…：最小の木は深さが一で葉が二個ですが、この式に一を入れると2の0乗となって一になってしまいます。正しくは2のn乗で、指数が一つずれた形です。深さを枝の本数ではなく段数で数えると、この誤りに落ちます。
• ウ節点の個数が n ならば，木の深さは l…：節点が三個の木で試すと、2を底とする対数はおよそ1.58になります。深さは枝の本数なので整数にしかならず、実際の深さである一とは合いません。深さと葉の個数の関係なら対数で表せますが、節点の個数ではありません。