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で質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
定規で正三角形
-
外接円が存在しない三角形って...
-
立方体の切断面(元の3点とも...
-
正十二面体の展開図の見方
-
周の長さを求める問題
-
『直角三角形であれば、辺の比...
-
二等辺三角形の等しい辺(2つ)...
-
立体の合同条件はあるのでしょうか
-
直角三角形を2枚組み合わせたこ...
-
三角形のフェルマー点と重心が...
-
三角錐の角度
-
確率、事象
-
中学の三平方の定理教えて下さい
-
三角比signθ→小数点
-
無理数は何故「±」があるのか?...
-
立方の対角線が辺となす角度θ求...
-
平方根の大小の並び替えの問題
-
台形立方体の斜辺の長さの求め方
-
グラフが木であるとき、この定...
-
パワーポイントMacBookにて、 ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
定規で正三角形
-
平方根での問題なのですが。
-
三平方の定理で√にくくわれる方...
-
外接円が存在しない三角形って...
-
X軸方向の角度とY軸方向の角度...
-
三角錐の稜線の角度の出し方。
-
四角錐(ピラミッドのような形...
-
一辺が3センチの三角形の高さが...
-
直角三角形以外の三角形の辺の長さ
-
正5角錐を作るにあたり
-
立体の合同条件はあるのでしょうか
-
角錐(四角錘)の展開図
-
「下の図のような△ABCがある。2...
-
直角三角形ではない三角形の計...
-
中学の三平方の定理教えて下さい
-
三角比signθ→小数点
-
サッカーボールの体積と表面積...
-
三角錐の角度
-
正十二面体の展開図の見方
-
【急】数学の解説をお願いした...
おすすめ情報