木は2部か?

太郎さんと花子さんが教室Zoomで会話している—


太郎:ねえ花子さん、木は2部なのかな?

花子:木って何?

太郎:ああ、花子さんはまだグラフ理論を履修していなかったんだ。じゃあ簡単に定義から述べてみるね。

花子:うん、お願い。

定義(グラフ)
グラフとは、次のような集合 V, E の組である。
i) V の要素は頂点とよばれる。
ii) E の要素は相異なる2頂点の非順序対であり、辺とよばれる。

定義(頂点の次数)
頂点 v を端点にもつ辺の個数を v の次数という。

太郎:グラフ G の頂点集合・辺集合を強調したいときは G(V, E) と表記するよ。V, E が有限であるようなグラフを有限グラフというんだ。今回は有限グラフのみを考えることにするね。

花子:わかった。

太郎:それから、E の性質から明らかにループ(頂点自身への辺)や多重辺(同じ2頂点間を結ぶ複数の辺)は許されないんだ。ちなみに、ループや多重辺を許すものを多重グラフ、許さないものを単純グラフとよぶこともあるようだね。

花子:なるほどね。続けて。

定義(歩道)
歩道とは、頂点と辺の交互列
v0, e1, v1, ..., en, vn
である。n を歩道の長さとよぶ。v0 を(歩道の)始まり、vn を(歩道の)終わりとよぶ。とくに始まりと終わりが同じであるとき、歩道が閉じているという。

定義(道)
道とは、すべての頂点が異なる歩道である。

定義(閉路)
閉路とは、終わりを除くすべての頂点が始まりと相異なる閉じた歩道である。

花子:ちょっと待って。歩道とか道とか、ちょっと分かりにくいネーミングじゃない?

太郎:確かに。英語表記だと歩道は walk、道は path、閉路は cycle っていうらしいよ。

花子:英語もあわせて覚えると混乱しなくて済みそうだね。

定義(連結)
グラフの任意の2頂点間に道が存在するとき、グラフは連結であるという。

定義(木)
木とは、閉路を持たない連結なグラフである。

太郎:頂点が1個の木は退化木とよばれるけど、今回は退化木は考えない。つまり、頂点が2個以上の木だけを考えることにするよ。

花子:わかった。

太郎:余談だけど、閉路を持たないグラフで連結とは限らないものを森というんだ。林とよぶ本もあるらしいよ。だから木は森であり林なんだね。

花子:大自然を感じるね。

定義(2部)
グラフ G(V, E) について、V がある部分集合 V1, V2 に分割され、E の任意の辺が V1 の頂点と V2 の頂点を結んでいるとき、G は2部であるという。

太郎:必要な定義はこのくらいかな。

花子:ありがとう。ええと、木は次数1の頂点を持つんだよね。

太郎:というと?

花子:木の頂点をひとつ固定して根とよぶことにするよ。頂点 v を任意にとる。木は閉路を持たず連結であるから、根を始まりとし v を終わりとする道がただひとつ存在する。このような道の長さを d とおく。v の次数が1ならば主張が成立する。v の次数が2以上ならば、根を始まりとし v を含む道であって長さが d より大きいものが存在するから、このような道の終わりを v とおきなおして同じ議論を繰り返せば、グラフが有限であることから最終的に次数1の頂点に到達する。違う?

太郎:ああ、そうかも。

花子:じゃああとは簡単だよ。自然数 n の条件 P(n) を「頂点数 n の木は2部である」と定義する。頂点が2個の木は2部であるから、P(2) が成立する。つぎに任意の n, n≧2 に対して P(n) の成立を仮定して、頂点数 n の任意の木をとる。この木の次数1の頂点に新たな辺と頂点をつなげたグラフは木かつ2部であるから P(n+1) が成立する。したがって、任意の n, n≧2 に対して P(n) が成立する。すなわち木は2部である。簡単だね。

太郎:花子さん、本当に未履修なの? 


数学の入試問題は問題文が短いと話題になったりしますが、問題文の短さでいうと「木は2部か?」は個人的に結構好きな問題です。ところで葉(木がもつ次数1の頂点)に関する帰納法は Leaf Reduction ともよばれると聞いた覚えがありますが、ソースが見つからずなんとも言えません。全体を通して誤りがあれば(たぶんありそうですが)修正しますのでご指摘くださると幸いです。

参考文献

  • マグロウヒル大学演習 離散数学 コンピュータサイエンスの基礎数学

いいね
MENU