数学です

質問

Ｇを，ｎ頂点とｍ辺をもつ木とす ると，ｎ＝ｍ＋１である

この定理の証明がうまく説明できません。
数学的に答えなければならないのですが、言い回しが私には難しくて。

誰か教えていただけませんか？

回答No.2

shuu_01 · ベストアンサー

「木」、「頂点」、「辺」 をどう定義するかで、数え方も違うので、証明できないのでないでしょうか？

下図は僕が普通に考えて、頂点、辺を数えたのですが、n ＝ m + 1 となりません

あえて、n ＝ m + 1 となるように、「木」、「頂点」、「辺」 を定義したとして、

m ＝ 1 の時、１つの辺の両端に頂点が２つでき、n ＝ 2 である

辺が m 本あった時の頂点の数を n とし、n ＝ m + 1 が成り立っているとする

そこに１本 辺を加えると、頂点の数は １個増え、m+1 本の時もこの式が成り立つ

と帰納法を使って証明したら？

お礼

やはり。難しいですね。

ちょっと取り組んでみます。

ありがとうございました

回答No.3

asuncion

木構造であるから、
1個の親
(n - 1)個の子
という構造である（はず）。

親から子への対応は1対1であるから、
親から子への辺の数 = n - 1
これがmに等しいから、
m = n - 1
n = m + 1

見当違いだったら、すみません。

お礼

そう考えたらとても簡潔ですね。
帰納法に付け加えて取り入れてみたいと思います。、

ありがとうございました

回答No.1

Tacosan

帰納法まわせ.

お礼

ありがとうございます