うさぎでもわかる離散数学（グラフ理論）　第11羽　木・根付き木

こんにちは、ももやまです。

今回はちょっと特殊なグラフである木についてまとめています。

前回の記事（第10羽）はこちら！

オイラーグラフ・ハミルトングラフについてです。

www.momoyama-usagi.com

スポンサードリンク

１．木・森

(1) 木とは

閉路を持たないような連結なグラフのことを木と呼びます。

下の図を例にすると、左と真ん中のグラフは閉路を持たないような連結なグラフなので木です。しかし、右のグラフは閉路があるので木と言うことができません。

(2) 木の重要な5つの特徴

木構造には重要な5つの特徴があります。

特に点の数 \( n \) と辺の数 \( m \) の数の関係\[
m = n - 1
\]は非常に重要なので必ず頭に入れておきましょう。

(3) 森（林）とは

森とは、木の条件である「閉路を持たず、連結である」の「連結である」部分の縛りをなくしたものです*1。

つまり、閉路を持たないようなグラフが森となります。森のことを林と呼ぶ先生もいますが、本記事では森で統一したいと思います。

下のように木をいくつか集めたものが森と考えてもいいでしょう。

下の図を例にすると、4つの木が集まっていますね。練習にそれぞれの木の点数と辺数を数えてみましょう。

あるグラフが森の場合の辺数 \( m \) は、頂点数 \( n \)、連結数 \( k \) を用いて\[
m = n - k
\]と表すことができます。

例えば上のグラフ（森）の場合、4つの木に分割することができるので連結数は4ですね。さらに頂点数は15なので、辺の数は\[
m = 15 - 4 = 11
\]と計算することができます。

（実際に手で数えても辺の数は11となるので公式が正しいことがわかりますね。

木単体も森と呼ぶので注意しましょう。（連結数 \( k = 1 \) の森）

では1問例題です。

例題1

つぎの(1)～(3)の問いに答えなさい。

(1) 位数（頂点数）が4のとき、5のときの辺の数、次数の総和を答えなさい。
(2) 位数（頂点数）が4の互いに同型ではない木をすべて書きなさい。
(3) 位数（頂点数）が5の互いに同型ではない木をすべて書きなさい。

解説1

(1)

(辺数) = (頂点数) - 1 、(次数の和) = 2 × (辺数) を使う（握手定理）

握手定理忘れた人はこちらで復習しましょう。

頂点数4：辺数は3、次数の和は6
頂点数5：辺数は4、次数の和は8

(2)

頂点数が4の木の次数の和は6であることに注目する。

次数列*2としては、「3,1,1,1」もしくは「2,2,1,1」の2つが考えられる。

※次数列が異なれば当然同型ではないので、次数列をすべて書き出すことで同型ではないグラフをすべて書き出しやすくなる。

（ただし次数列が同じ同型ではないグラフは1つとは限らないので注意）

よってそれぞれの次数列ごとの同型ではない頂点数4のグラフは下のようになる。

(3)

頂点数が5の木の次数の和は8となる。

次数列としては、「4,1,1,1,1」、「3,2,1,1,1」、「2,2,2,1,1」の3つが考えられる。

よってそれぞれの次数列ごとの同型ではない頂点数5のグラフは下の3つである。

スポンサードリンク

２．根付き木

木のとあるノード（点）を根とした木のことを根付き木と呼びます。

根付き木には木にはない特殊な用語がいくつかあるのでまとめて紹介をしたいと思います。

(1) 深さ

深さはある点から根からの長さ（たどる際に通った辺の本数）を表します。

上の図の例でいくと、 \( v_2 \) は根（ \( v_1 \) ）からの距離が1なので深さは1ですんね。同様に \( v_{12} \) だと、根から3本の辺をたどる必要があるため深さは3となります。

(2) 高さ

あるノード（点）からより深い方向（根から遠ざかる方向）にたどっていった際にどれくらい深くたどれるかを表したものが高さとなります。

例えば深さが1であるオレンジで囲われたノードは深い方向にたどっていくと「深さ3」のノードまでたどることができますね。2つ分深いところまでたどれるので高さは2となります*3。

同様に深さが2であるピンクで囲われたノードは「深さ4」のノードまでたどれますね。2つ深いところまでたどれるので高さは2となります。

根（深さ0）の高さは根付き木の高さとなります。

根からは深さ4までのノードまでたどれ、4つ深いところまでたどれるので高さは4となります。

(3) 親・子

根付き木では頂点の関係を家系図のように例えます。

隣接してる2つの点に対して、より根に近い方を親、遠い方を子と呼びます。表記法としては、「xxxはyyyの親/子である」と表現します。

例えば \( v_8 \) と \( v_{13} \) であれば「\( v_{8} \) は \( v_{13} \) の親」、「\( v_{13} \) は \( v_{8} \) の子」のように呼びます。

（\( v_{8} \) の子は \( v{13} \), \( v_{14} \) の2つあります）

(4) 先祖・子孫

あるノードを先祖としたとき、先祖のノードからより深い方向にたどっていったときにあるノードすべてを子孫と呼びます。

言い換えると、子孫のノードからより浅い方向にたどっていったときにあるノードすべてが先祖となります。

（親子関係と同じく、「xxxはyyyの先祖/子孫」であると表記します。）

例えば \( v_{5} \) を基準に考えると \( v_{10} \), \( v_{11} \), \( v_{15} \) の3つが \( v_{5} \) の子孫となります。

逆に \( v_{5} \) の先祖は \( v_{2} \), \( v_{1} \) の2つがあてはまります。

(5) 兄弟

同じ深さにいるノード同士は兄弟となります。

例えば \( v_{2} \) と \( v_{3} \) は兄弟となります。

同様に \( v_{4} \), \( v_{5} \), \( v_{6} \), \( v_{7} \) 同士も兄弟となります。

では、例題で用語の復習をしてみましょう。

例題2

\( v_1 \) を根とする根付き木がある。これについて、(1)～(5)の問いに答えなさい。

(1) \( v_2 \) の深さ、高さを求めなさい。
(2) この根付き木の高さを求めなさい。
(3) \( v_2 \) の親、子を求めなさい。
(4) \( v_2 \) の先祖、子孫を求めなさい。
(5) \( v_2 \) の兄弟を求めなさい。

（ (3)～(5)は複数ある場合はすべて求めること）

解説2

(1)

解答：深さ1　高さ2

\( v_2 \) と根 \( v_1 \) の距離は1なので深さは1、\( v_2 \) から深くなる方向にたどった際に一番深くなるのは \( v_7 \), \( v_8 \), \( v_9 \) がある深さ3の部分である。よって高さは3 - 1 = 2となる。

(2)

解答：4

根（深さ0）から見たときにもっとも深いノードは \( v_{12} \) となり、深さは4である。よって高さも4となる。

(3) 親：\( v_1 \)　子：\( v_4 \), \( v_5 \)

(4) 先祖：\( v_1 \)　子孫：\( v_4 \), \( v_5 \), \( v_7 \), \( v_8 \), \( v_9 \)

(5) \( v_3 \)

スポンサードリンク

３．m分木（2分木）・完全m分木（完全2分木）

\( m \) 分木の中でも \( m = 2 \) のとき、つまり2分木はデータ構造などでも頻繁に利用されます。

2分木は少なくとも頭にいれておきましょう。

(1) m分木（2分木）とは

根付き木の中でもそれぞれの点における子の数が \( m \) 個以下である根付き木のことを \( m \) 分木と呼びます。

例えば \( m = 2 \) のとき（2分木）であればそれぞれの点が2個以下の子を持ちます。\( m = 3 \) （3分木）であればそれぞれの点が3個以下の子を持ちます。

(2) 完全m分木（完全2分木）とは

\( m \) 分木の中でも葉以外のすべての点が \( m \) 個ずつ子をもつ根付き木のことを完全 \( m \) 分木と呼びます。

完全 \( m \) 分木は中途半端に \( m \) 個未満の子を持つような点はなく、すべての点が \( m \) 個の子を持つか葉のどちらかになっています。

例えば \( m = 2 \) のとき（2分木）であれば葉以外のすべての点が2つの子をもち、\( m = 3 \) （3分木）であれば葉以外のすべての点が3つの子を持ちます。

さらに完全2分木の頂点と葉数の数には下のような関係式が成り立ちます。

今回は練習問題に入れていませんが、与えられた葉の数から同型でない完全2分木をすべて答えるような問題の場合、上の公式から頂点数を求めると形を絞ることができます。

４．練習問題

では4問ほどですが練習してみましょう。

練習1

頂点数6の木について次の問いに答えなさい。

(1) 辺数と次数の合計を答えなさい。
(2) 頂点数6で互いに同型ではない木構造は全部で何個ありますか。

練習2

頂点数7の木で、葉の数が2～6個のグラフをそれぞれ1つずつ書きなさい。

練習3

任意の木は2部グラフであることを示しなさい。

練習4

点の数が \( n \) 個、辺の数が \( n-1 \) 個のグラフは必ず木となることを数学的帰納法を用いて示しなさい。

５．練習問題の答え

練習1

(1)

頂点数 \( n \) と辺数 \( m \) には、\[
m = n - 1
\]の関係があるので、辺数は5となる。よって次数の和は10となる。

(2)

次数の和が10、点の数が6の場合の次数列の組み合わせを列挙すると、

• 5,1,1,1,1,1
• 4,2,1,1,1,1
• 3,3,1,1,1,1
• 3,2,2,1,1,1（2通り同型でないグラフが書ける）
• 2,2,2,2,1,1

の5つである。さらにそれぞれの次数列ごとに同型でない木を書いていくと、下のように6個書ける。

よって答えは6個となる。

練習2

頂点数7なので、辺数は6、次数の和は12となる。

頂点数7、次数の和が12の場合の次数列の組み合わせを列挙すると、

• 葉が5つ：6,1,1,1,1,1
• 葉が4つ：5,2,1,1,1,1（4,3,1,1,1,1）
• 葉が3つ：4,2,2,1,1,1（3,3,2,1,1,1）
• 葉が2つ：3,2,2,2,1,1

となる。よってそれぞれの次数列ごとのグラフは下のようになる。

（別解）

葉が5つで次数列が「4,3,1,1,1,1,1」の場合、葉が4つで次数列が「3,3,2,1,1,1,1」の場合のグラフは下のようになる。

練習3

2部グラフの条件を少し変形させるだけで簡単に証明ができます。

（証明）

2部グラフの条件はすべての閉路の長さが偶数となるである。

つまり、長さが奇数となるような閉路が存在しないようなグラフが2部グラフとなる。

どのような木であっても閉路は持たないため、当然長さが奇数となるような閉路も存在しない。

よって木は2部グラフであることが示された。

練習4

頂点数に関する数学的帰納法で示す。

（数学的帰納法が怪しい人はこちらの記事で復習しましょう。）

(1) 頂点数 \( n = 1 \) のとき

頂点は孤立点となるので辺の数は0本。よって(1)のとき成立。

(2) 頂点数が \( n + 1 \) のとき

頂点数が \( n + 1 \) のグラフを \( T_1 \) とする。

ここで \( T_1 \) の辺の数が \( n \) になることを示す。

\( T_1 \) から次数が1である頂点、頂点に接続する辺を除去したグラフを \( T_2 \) とする。

ここで \( T_2 \) は \( T_1 \) から点を1本除去しているので頂点数は \( n \) となる。さらに帰納法の仮定より \( T_2 \) の辺の数は \( n-1 \) となる。

\( T_1 \) から辺を1本除去したグラフが \( T_2 \) なので \( T_2 \) の辺の数は \( n \) となり、(2)のときも成立。

(1), (2) より題意は満たされた。

６．さいごに

今回はグラフ理論における木・根付き木についてまとめました。

次回は探索アルゴリズムについて簡単にですがまとめていく予定です。