No.1ベストアンサー
- 回答日時:
(a)Gは木である。
(サイクルがなく連結)(b)Gはサイクルを持たず、n-1本の辺を持つ。
(c)Gは連結であり、n-1本の辺を持つ。
a->b,a->c
木だからサイクルがなく連結。辺の数をmとする。端点(辺1本しかない)とその辺を取っても木であるから、n-mは一定。この操作を繰り返すと、孤立点が残る。よってn-m=1。
b->c
サイクルがなくn-1本の辺を持ち、連結でないとする。適当に辺を加えて連結すればこれは木で、辺の数>n-1。一方木ならm=n-1のはずで、矛盾。
c->b
連結でn-1本の辺を持ち、サイクルがあるとする。サイクルを構成する辺の一つを取ればサイクルはなくなり、連結でサイクルがないからこれは木で、辺の数<n-1。一方木ならm=n-1のはずで、矛盾。
b->a
サイクルがなくn-1本の辺を持てばb->cにより連結であるから、木。
こんなのでOK?
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 グラフ理論の数学の問題です。このタイプの問題は初めて見たので、どうやって解けばいいかわからないです。 1 2023/05/27 19:09
- 高校受験 数学の問題いくつか捨てても大丈夫?残り1ヶ月、点数が取れない教科ばっか勉強しても大丈夫? 高校受験 2 2023/01/07 17:55
- 数学 (問題) xy平面において,6本の直線x=k(k=O, 1, 2, 3, 4, 5)のうちの2本と, 3 2023/03/19 21:56
- 統計学 正規分布に関する問題 3 2023/03/02 22:02
- 憲法・法令通則 日本国憲法の問題点について日本国憲法の問題点を【⠀】の中のどれかの範囲で600字で書くのですが全く思 1 2023/01/24 10:25
- 大学受験 ある大学の数1,Aの過去問なのですが回答に解説がなく困っています。誰か解説をつけて欲しいです(><) 1 2022/11/05 12:57
- 情報処理技術者・Microsoft認定資格 基本情報技術者試験について 基本情報技術者試験の午後問題についてなのですが、 大門①の情報セキュリテ 1 2022/10/30 00:34
- 数学 【 数I 二次方程式の実数解 】 問題 ※写真の(2) 解答 いずれか一方のみが実数解を持つため に 1 2022/06/25 17:36
- その他(教育・科学・学問) 高校受験について 1 2022/10/29 11:03
- 高校 数学Aの問題で、円に内接するN角形(N>4)の対角線の総数は ア 本である。また、Fの頂点三つからで 1 2023/04/13 17:47
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正十二面体の展開図の見方
-
定規で正三角形
-
直角三角形以外の三角形の辺の長さ
-
三角錐の稜線の角度の出し方。
-
数検2級の問題のついてです。 ...
-
X軸方向の角度とY軸方向の角度...
-
θの求め方
-
証明の角と辺ってどうやって見...
-
ハーバード大学の数学の問題で...
-
正5角錐を作るにあたり
-
中学の三平方の定理教えて下さい
-
二辺と高さしかわからない三角...
-
角錐(四角錘)の展開図
-
立方の対角線が辺となす角度θ求...
-
数学の証明についてです 点 E,F...
-
三角比signθ→小数点
-
四角錐(ピラミッドのような形...
-
正八面体の展開図
-
【数学】傾斜の角度から何ミリ...
-
直角三角形ではない三角形の計...
おすすめ情報