No.3ベストアンサー
- 回答日時:
証明の前に,少し,おさらいをします.
『木(tree)とは,連結グラフで,サイクルと同型な部分グラフをもたないもの』
を言います.以下,点を頂点といい,枝を辺といいます.
いま,n頂点とは,頂点の数がn個の頂点のことで,m辺とは,辺の数がm個の辺のこととします.
定理A:グラフGが連結で,n頂点とm辺をもつならば,n≦m+1 である.
(定理Aの証明は省略します)
定理B:Gを,n頂点とm辺をもつ木とすると,n=m+1である.
証明: 辺の個数に関する帰納法で証明します.Gが辺をもたないならば,定理Bは,このGについては,正しい.
m辺より少ない辺をもつ木については,定理Bが正しいと仮定する.
いま,Gの最長の道を選び,その端頂点をaとbとする.
頂点aは,次数1です.もし,そうでないとすると,この道は,もっと長くすることが出来るか,
または,Gにサイクルが存在してしまうことになるからです.
ここで,「頂点a」と「頂点aと接続する辺」を取り除く.こうして得られたグラフをHとする.
Hは,まだ依然として木であり,n-1頂点と,m-1辺をもつ.帰納法の仮定から,
n-1=(m-1)+1です.これにより,n=m+1であり,
定理Bは,Gについても正しい.■
ちょっと,すっきりしない証明かも知れませんので,以下に木に関する別の定理を書いておきます.
定理C:グラフGが連結で,n=m+1ならば,Gは木である.
証明:定理Cが正しくないと仮定すると,連結なグラフGで,n=m+1であるが,
木でないグラフが存在することになる.いま,Gは木でないのだから,Gはサイクルを含む.
このサイクル上の1辺を取り除くことにより,連結でn頂点とm-1辺をもつグラフHを得る.
定理Aにより,n≦(m-1)+1=m となるが,n=m+1と仮定したのだから,
これは矛盾である.よって,Gは木である.■
(余談)直感的に,感覚的に,木のn=m+1を理解するには,
頂点と辺(点と枝)を一対にしたもの( ―――● )を木から,何度も取り除いてゆく.
頂点と辺の数は有限なので,最後に頂点(●)だけが1個の残ります.
これが,直感的な証明です.
(一応,見直したのですが,どこかに誤記や間違いがあるかも知れません.
今は,気が付きませんが,間違えていたら,ごめんなさい)
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 グラフ理論の数学の問題です。このタイプの問題は初めて見たので、どうやって解けばいいかわからないです。 1 2023/05/27 19:09
- 数学 『◯と●の帰納法』 2 2023/04/19 20:57
- 数学 高校数学の問題です。 aを定数とする。放物線y=x^2+aと関数y=4|x-1|-3のグラフの共有点 3 2022/05/09 08:59
- その他(プログラミング・Web制作) どういうプログラムで組みますか?google colabでやってるんですけど、出来る方お願いします。 1 2022/07/17 18:41
- その他(プログラミング・Web制作) このプログラミングをどう組みますか? Googlecolabでやってるんですが、出来る方お願いします 1 2022/07/13 10:52
- 数学 微分の問題です 1 2022/07/31 11:15
- 高校 三次関数のグラフにつきまして 3 2022/05/15 11:14
- Excel(エクセル) Excelでグラフを作りたいです。散布図でしょうか? 3 2023/02/09 12:48
- ガーデニング・家庭菜園 柘榴の剪定の見極め 2 2023/02/28 17:51
- 数学 無理数の数字の組み合わせ。無限の意味について 5 2022/05/28 22:53
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正十二面体の展開図の見方
-
定規で正三角形
-
直角三角形以外の三角形の辺の長さ
-
三角錐の稜線の角度の出し方。
-
数検2級の問題のついてです。 ...
-
X軸方向の角度とY軸方向の角度...
-
θの求め方
-
証明の角と辺ってどうやって見...
-
ハーバード大学の数学の問題で...
-
正5角錐を作るにあたり
-
中学の三平方の定理教えて下さい
-
二辺と高さしかわからない三角...
-
角錐(四角錘)の展開図
-
立方の対角線が辺となす角度θ求...
-
数学の証明についてです 点 E,F...
-
三角比signθ→小数点
-
四角錐(ピラミッドのような形...
-
正八面体の展開図
-
【数学】傾斜の角度から何ミリ...
-
直角三角形ではない三角形の計...
おすすめ情報