家系図での例

ウィキペディア小見出し辞書

家系図での例

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/16 02:01 UTC 版)

「構造的帰納法」の記事における「家系図での例」の解説

家系図は次のように再帰的に定義される、よく知られた木構造である。 最も簡単なケースでは、家系図はたった1人だけを記す。（その人の両親が知られていない場合。） あるいは、1人と、その両親の家系図2つへの枝からなる。（証明を簡単にするため、一方の親が知られていたら、両方とも知られていることにしている。） 例として、性質「g 世代にわたる家系図は、多くとも 2g-1 人だけを記している。」を、構造的帰納法によって次のように証明する。 単純なケースでは、家系図はちょうど1人だけを記す。そのため g = 1 である。1 ≦ 21 - 1 であるから、前述の性質を満たしている。 あるいは、家系図は1人とその両親の家系図からなる。親の家系図はいずれも全体の家系図の部分構造だから、それらは前述の性質を満たしていると仮定できる。（これを帰納法の仮定(induction hypothesis)という。） すなわち、親の家系図に記される世代の数をそれぞれ g, h で表し、親の家系図に記される人数をそれぞれ p, q で表すと、p ≦ 2g-1 と q ≦ 2h-1 が成り立つ、と仮定する。g ≦ h のとき、全体の家系図は (h + 1) 世代にわたり、記されているのは p + q + 1 人である。p + q + 1 ≦ (2g - 1) + (2h - 1) + 1 ≦ (2h - 1) + (2h - 1) + 1 = (2h + 1 - 1) + 1。ゆえに、全体の家系図が性質を満たしていることが分かる。 h ≦ g のときも同様。 したがって、すべての家系図が上記の性質を持つ。