
スポンサードリンク
こんにちは、ももやまです。
今回はちょっと特殊なグラフである木についてまとめています。
前回の記事(第10羽)はこちら!
オイラーグラフ・ハミルトングラフについてです。
目次 [hide]
スポンサードリンク
1.木・森
(1) 木とは
閉路を持たないような連結なグラフのことを木と呼びます。
下の図を例にすると、左と真ん中のグラフは閉路を持たないような連結なグラフなので木です。しかし、右のグラフは閉路があるので木と言うことができません。
(2) 木の重要な5つの特徴
木構造には重要な5つの特徴があります。
- グラフが閉路を持たず、連結である。
- 連結なグラフの位数(点数)が
のとき、辺数が となる。
( (辺の数) = (点の数) - 1 で覚えましょう) - 閉路を持たないグラフに隣接していない2点の間にどのように辺を加えても、閉路が1つだけできる。
- グラフの辺を1本でも消すと連結ではなくなる。
- グラフのどの2点間の道は1通りしかない(たどり方は必ず1通り)
特に点の数
(3) 森(林)とは
森とは、木の条件である「閉路を持たず、連結である」の「連結である」部分の縛りをなくしたものです*1。
つまり、閉路を持たないようなグラフが森となります。森のことを林と呼ぶ先生もいますが、本記事では森で統一したいと思います。
下のように木をいくつか集めたものが森と考えてもいいでしょう。
下の図を例にすると、4つの木が集まっていますね。練習にそれぞれの木の点数と辺数を数えてみましょう。
あるグラフが森の場合の辺数
例えば上のグラフ(森)の場合、4つの木に分割することができるので連結数は4ですね。さらに頂点数は15なので、辺の数は
(実際に手で数えても辺の数は11となるので公式が正しいことがわかりますね。
(イメージ:木が何個か集まったもの)また、あるグラフが森であるときの辺の数
木単体も森と呼ぶので注意しましょう。(連結数
では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つである。
スポンサードリンク
2.根付き木
木のとあるノード(点)を根とした木のことを根付き木と呼びます。
根付き木には木にはない特殊な用語がいくつかあるのでまとめて紹介をしたいと思います。
(1) 深さ
深さはある点から根からの長さ(たどる際に通った辺の本数)を表します。
上の図の例でいくと、
(2) 高さ
あるノード(点)からより深い方向(根から遠ざかる方向)にたどっていった際にどれくらい深くたどれるかを表したものが高さとなります。
例えば深さが1であるオレンジで囲われたノードは深い方向にたどっていくと「深さ3」のノードまでたどることができますね。2つ分深いところまでたどれるので高さは2となります*3。
同様に深さが2であるピンクで囲われたノードは「深さ4」のノードまでたどれますね。2つ深いところまでたどれるので高さは2となります。
根(深さ0)の高さは根付き木の高さとなります。
根からは深さ4までのノードまでたどれ、4つ深いところまでたどれるので高さは4となります。
(3) 親・子
根付き木では頂点の関係を家系図のように例えます。
隣接してる2つの点に対して、より根に近い方を親、遠い方を子と呼びます。表記法としては、「xxxはyyyの親/子である」と表現します。
例えば
(
(4) 先祖・子孫
あるノードを先祖としたとき、先祖のノードからより深い方向にたどっていったときにあるノードすべてを子孫と呼びます。
言い換えると、子孫のノードからより浅い方向にたどっていったときにあるノードすべてが先祖となります。
(親子関係と同じく、「xxxはyyyの先祖/子孫」であると表記します。)
例えば
逆に
(5) 兄弟
同じ深さにいるノード同士は兄弟となります。
例えば
同様に
では、例題で用語の復習をしてみましょう。
例題2
(1)
(2) この根付き木の高さを求めなさい。
(3)
(4)
(5)
( (3)~(5)は複数ある場合はすべて求めること)
解説2
(1)
解答:深さ1 高さ2
(2)
解答:4
根(深さ0)から見たときにもっとも深いノードは
(3) 親:
(4) 先祖:
(5)
スポンサードリンク
3.m分木(2分木)・完全m分木(完全2分木)
2分木は少なくとも頭にいれておきましょう。
(1) m分木(2分木)とは
根付き木の中でもそれぞれの点における子の数が
例えば
(2) 完全m分木(完全2分木)とは
完全
例えば
さらに完全2分木の頂点と葉数の数には下のような関係式が成り立ちます。
今回は練習問題に入れていませんが、与えられた葉の数から同型でない完全2分木をすべて答えるような問題の場合、上の公式から頂点数を求めると形を絞ることができます。
4.練習問題
では4問ほどですが練習してみましょう。
練習1
頂点数6の木について次の問いに答えなさい。
(1) 辺数と次数の合計を答えなさい。
(2) 頂点数6で互いに同型ではない木構造は全部で何個ありますか。
練習2
頂点数7の木で、葉の数が2~6個のグラフをそれぞれ1つずつ書きなさい。
練習3
任意の木は2部グラフであることを示しなさい。
練習4
点の数が
5.練習問題の答え
練習1
(1)
頂点数
(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) 頂点数
頂点は孤立点となるので辺の数は0本。よって(1)のとき成立。
(2) 頂点数が
頂点数が
ここで
ここで
(1), (2) より題意は満たされた。
6.さいごに
今回はグラフ理論における木・根付き木についてまとめました。
次回は探索アルゴリズムについて簡単にですがまとめていく予定です。
関連広告・スポンサードリンク