グラフ理論で

質問

グラフΓがtree（無閉路グラフ）であるとき、♯E（Γ）＝♯V（Γ）－１　が成り立つことを証明するという問題がわかりません。　教えていただけませんか？

回答No.10

alice_44 · ベストアンサー

既に No.7 でも No.9 でも言われていることだが、
＞ 証明することさえできれば
＞ どの定義を使っても
という姿勢が、そもそも大いに問題あり。
定義を確認しなくては、証明なんてありえない。

例えば、
連結かつ (辺の数)=(頂点の数)-1 が成立つグラフ
のことを「木」と呼ぶことに決めても、
普通に「木」と呼ばれるのと同じものが定義できるが、
この定義によれば、質問の証明は
「それは定義の一部である」だけで終わる。

教科書等を調べて、貴方が何らかの定義を補足すれば、
その定義に基づいて証明を書いてくれる回答者が
現われるはず。No.8 の続きも、きっと誰かが。

ここでは、No.3 No.7 への返礼として、
No.6 の続きを書いてみる。

連結かつ閉路がないグラフを「木」と定義し、
頂点数についての帰納法で題意を証明する。

[1] 頂点数 1 のグラフは連結であり、
閉路がなければ辺数は 0 に限られる。
よって、(辺の数)=(頂点の数)-1 が成立つ。

[2] 頂点数 n 以下の木については
(辺の数)=(頂点の数)-1 が成立つものと仮定する。
ここに頂点数 n+1 の木があるとして、
このグラフのどこか一頂点から、同じ頂点を二度通らずに
辺をたどってゆくと、n 歩以内に、それ以上行けなくなる。
行き止まりの頂点と既に通過した頂点との間に
まだ通っていない辺があれば、閉路があることになるから、
行き止まりの頂点は、辺を 1 本しか持たない。
行き止まりの頂点と辺を木から取り除いたグラフは
頂点数 n の木になるから、
(頂点数 n の木の辺数)=(頂点数 n の木の頂点数)-1 により、
(頂点数 n+1 の木の辺数)-1={ (頂点数 n+1 の木の頂点数)-1 }-1。

[1][2] により、数学的帰納法によって、題意は成立つ。

お礼

お手数をおかけして
すみませんでした。

alice_44さんTacosanさん本当にありがとうございました。

回答No.9

Tacosan

定義にもよるけど, 「連結かつ無閉路」ならその線が楽でしょうね＞#8.

ちなみに #5 の補足で
「証明することさえできればどの定義を使っても大丈夫だと思います。」
と書いてるけど, もし
連結かつ「頂点が辺より 1つだけ多い」グラフ
を木の定義に使うのなら, この命題の証明など造作もありませんよ... というか, これで証明できなかったらどうかと思う.

回答No.8

alice_44

一辺点の存在を後回しにして帰納法を行うとすると、
定理を、森において (辺の数)=(頂点の数)-(連結成分の数)
に拡張して、これを帰納法で示す方針かな？

補足

ありがとうございます。

すみませんできれば
詳しく教えていただけませんでしょうか??

回答No.7

graphaffine

Tascon氏が定義を確認してるのに、なんで答えられないんだろ。

>証明することさえできれば
>どの定義を使っても大丈夫だと思います。

これは、課題ではないのですか。課題だったら、講義に出てきた定義を使わないとまずいんだが。

#6
>「木」の定義をいづれに置くとせよ、
>一辺点の存在を示せばよいという方針は同じなのでは？

私の知ってる場合に限れば、質問されてることを、帰納法で証明し、それを使って「一辺点の存在を示す」という流れですね。当然、定義が変われば流れも違ってくるんだが、そういう認識無しに質問してるみたいですね。

補足

確かにまったく認識できずに質問しています。
すみません。

課題ではあるのですがネットや本など、どのように調べてもよいのでこの証明をしてこいと言われました。

ノートなどを確認してみましたが木の定義は見当たりませんでした。

なので帰納法で証明し、それを使って「一辺点の存在を示す」という流れで大丈夫だと思います。

その流れを詳しく教えていただけないでしょうか？

回答No.6

alice_44

←No.3 なるほど。
「連結なグラフで」という条件を欠いては駄目ですね。
つい忘れがちだから、気をつけないと。

「木」の定義をいづれに置くとせよ、
一辺点の存在を示せばよいという方針は同じなのでは？

回答No.5

Tacosan

あえて木の定義を聞いたのは, 等価な定義がいくつもあってかつどの定義を使うかによって証明の難易度が完全に違うからなんだけど....
例えば
・連結だけど辺を 1本でも取り除いたら非連結になるグラフ
・連結かつ「頂点が辺より 1つだけ多い」グラフ
は結果的に同じ (「木」という) ものを定義するんだけど, どちらの定義であるかによって証明の難しさが違うというのは直感的に明らかだよね?

補足

えっと…
証明することさえできれば
どの定義を使っても
大丈夫だと思います。

僕自身が定義について
あまり深く理解できていないので
もし的外れなことを
言っていたら
ごめんなさい…

回答No.4

1234sgo

木は、一つの頂点からなるグラフを起点とし、そこに頂点と辺の組を次々と付加していくことで作ることができる、
ということから明らかです。

また、任意の頂点V0に注目した場合、他の全ての頂点からそこに至る経路は、閉路がないという性質からそれぞれ一意に決まります。
これらの経路は両端に頂点を持つ一直線なので頂点が辺よりも必ず1つ多くなります。

お礼

ありがとうございます。

回答No.3

Tacosan

単に「閉路がない」ことをもって「木」を定義することはないはずです＞#2. たとえば「頂点が 1000個あって辺は 1本もない」グラフを「木」と呼ぶことはないと思います.
もちろんそのようなグラフを「木」と呼ぶ, と定義しても構いませんが, その場合 #2 で挙がっている「木には辺数 1 の頂点が存在すること」は証明できない (というか反証できる... けど実はこの命題は通常の「木」の定義においても危ない) し, さらにはもともとの命題も成り立ちません.

普通に定義される「木」で (上に書いた微妙な問題点を回避して) あればいいんだけど.

補足

おそらくですが「閉路がない」というのは「木」についての簡単な説明のためにつけてくれただけだと思うので、普通に定義される「木」として考えて大丈夫だと思います。

回答No.2

alice_44

「木」と「閉路がない」は、同等だと思うけど。

木には辺数 1 の頂点が存在することを証明して、
その点と辺をコミでグラフから取り除くことを考えれば、
帰納法によって題意は証明できる。

回答No.1

Tacosan

「木」と「閉路がない」こととは等価じゃないよね.
とりあえず「木」を正確に定義できますか?