ちょっと難易度の高い問題だと「N個の頂点を持つ木が…」なんて出てきて、初心者は意味がわからず逃げ出したい気分になるでしょう。（自分だけ？）
今回は木構造について軽くまとめます。本当は1日1ACの記事の中で書くはずのものだったので本当に軽く。
木構造について
どういうものか
まずグラフについて説明します。ここでいうグラフとは以下のようなものです。
図中の丸を「頂点」、頂点間の線を「辺」と呼びます。言葉で説明すれば「頂点と辺の集まり」です。
図の 1, 2, 4の頂点のように、ループする部分を閉路と言い、どの2頂点間もそれらを繋ぐルートがある状態を連結であると言います。（連結であるグラフは連結グラフと言います。）
例えば、連結でないグラフは次のようなものです。
木とは「閉路がなく、連結であるグラフ」です。例えば、次のようなものは木です。（普通は上2つのように絡まった形ではなく、この図のように書きます。）
根・親・子
先ほどの図では、1番の頂点を「一番上」に書いていますが、このような頂点を特に「根」と言います。（一番上にする頂点はなんでもいいです。）
また、根を持つ木を「根付き木」と言います。
辺で結ばれた頂点について、根に近い方を「親」、遠い方を「子」と言います。図では「3番の頂点は8番の頂点の親」であり、「9番の頂点は8番の頂点の子」です。
部分木とは
木のある頂点を選んで、そこから「下」の頂点をまとめて抜き出すと、それが木になったりします。この木を、もとの木の部分木と言います。
終わりに
問題で問われる内容を網羅しているとは思いませんが、基礎知識は十分得られると思います。この記事の内容が分かれば、次の記事で取り上げる問題文の意味は理解できると思います。
コメント