組み合わせ理論 規則的な木構造の扱い方
木構造の正しい扱い方
[編集]この項目は非専門家によって書かれた間違いの含まれている可能性の高い講座です。 専門家による訂正をお待ちしております。
内部頂点の数と葉の数
[編集]木構造Aの枝(内部頂点という)と葉(頂点という)に関する問題。 内部頂点の数が一定なら、頂点の数が一定に収まることの証明。
一見違うように見える木Aと木B、しかし内部頂点の数も頂点の数も同じである。 この性質は木を取り扱う理論では極めて重要な要素を含んでいる。 なぜこうなるのかの証明を行う。
- 木Aと木Bの図準備中
木Aの内部頂点(枝)を切り取って木Aの頂点（葉）に接木する操作を繰り返すことによって、木Aを木Bに変形できる。 このとき内部頂点を切り取って頂点に接木することによって、木全体の頂点が一つ減る。 切り取った内部頂点の親が子をひとつしか持たない場合、木全体の頂点の数は変わらない。 接木を内部頂点に行う場合頂点の数は不変となる。 頂点を切り取った場合、どこに移動しても頂点の数は変わらない。 この性質が、木構造にかんする数学の基本となる。 変形操作を基準にした頂点の数による木の分類である。
頂点の数が増えることを水が低いほうに流れるイメージで扱うとすると、一番上にある木構造は棒であり、一番下にある木構造は根の下がすべて葉になっている構造となる。
ここでは上から規則的に、棒を木に崩していく作業を解説する。
講座製作者
[編集]講座製作者はこちらに名前を書いてください。
- 郵便番号 日本国675-0033-79-16 堀江伸一