親子におすすめの新型プラネタリウムとは?

G が切断点を持てば,G は橋を持つ  正しくない
G = (V, E) が連結,かつ |E| < |V | ならば,G は無向木である 正しい
すべての完全グラフの直径は 1 である 正しい
節点数 5 の完全グラフ K5 は平面描画可能である 正しくない
それぞれの理由を教えてほしいです。

このQ&Aに関連する最新のQ&A

A 回答 (1件)

G が切断点を持てば、G は橋を持つ → 正しくない


反例として、2 個の輪状グラフが 1 頂点を共有しているようなグラフ。

G = (V, E) が連結、かつ |E| < |V| ならば、G は無向木である 正しい
連結有向グラフの各頂点は流入辺を持ち、したがって |E| ≧ |V| である。
あとは、「連結無向グラフの辺の最小数は |E| = |V|-1 であり、そのとき
グラフは木である」を、頂点数についての帰納法で。

すべての完全グラフの直径は 1 である 正しい
「完全グラフ」と「直径」の定義より自明 …としか言いようがない。

節点数 5 の完全グラフ K5 は平面描画可能である 正しくない
辺が囲む領域の数を f と置くと、平面グラフについて
オイラーの公式 |V| - |E| + f = 2 が成り立つ。
また、単純グラフでは、辺が囲む各領域は頂点数 3 以上だから、
2|E| = 各領域を囲む辺数の総和 ≧ 3f でもある。
f を消去して 3|V| - |E| ≧ 6 だが、
K5 では、|V| = 5, |E| = 10 だから、この式は成り立たない。
    • good
    • 0
この回答へのお礼

親切な解答ありがとうございます。

お礼日時:2012/08/21 01:15

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q反射律・対称律・推移律

お世話になります。数学大嫌い男です。
やや数学っぽい本を見ていたら、反射律・対称律・推移律というのが書いてありました。
しばらくいくと次の問題がありました。

問「対称律と推移律が成り立つとき、対称律によって a~b ならば b~a,したがって推移律によって a~a となって反射律が成り立つという論法は誤りであることを説明せよ」

答「問題の論法は関係のついている元aだけについて a~aを言ったにすぎない」

私にはチンプンカンプンです。
答も何を言っているのかわかりません。
だって本には簡単にしか書いてません。反射律・対称律・推移律の定義を私がよく分かっていないのかな?

どなたか分かる人がいらっしゃいましたら、お教えください。
数学嫌いの私でも分かるように、よろしくお願いいたします。

Aベストアンサー

あぁ, 確かにひっかかりますね....
この問題を理解するためにはもちろん「反射律」, 「対称律」, 「推移律」を理解しなければならないんですが, 根底には「数学における『ならば』の意味」というポイントがひそんでいます.
日常での「A ならば B」という表現では, 「A が成り立たないとき」は考えていません. しかし, 数学における「A ならば B」は, 「A が成り立っているときには B も成り立つ」, つまり「A が成り立っていないときには B が成り立つかどうかに関係なく『A ならば B』は成り立つ」と解釈します. この, 日常と数学における「ならば」の意味の違いをきちんと理解しなければなりません.
さて, その上で「どの要素も (自分自身を含めて) どの要素とも関係を持たない」という関係 (日常用語では「関係」とはいわないけど, 数学ではこれも「関係」とみなします) を考えてみましょう.
まず対称律: 「全ての a, b に対し a~b ならば b~a」について考えます. 今考えている関係では, どの要素に対しても a~b は成り立ちません. このことから「全ての a, b に対し a~b ならば b~a」は成り立ってしまいます. ということは, この関係は対称律を満たします.
次に推移律: 「全ての a, b, c に対し a~b かつ b~c ならば a~c」ですが, これも同じように考えると満たしていることがわかります.
最後に反射律: 「全ての a に対し a~a」ですが, これは明らかに成り立ちません.
結局, 対称律と推移律では「ならば」を使っているのに対し反射律では「ならば」が出てこないことが差異として現れています.

う~ん, わかりづらそうだ.... どこがわからないか書いてもらえれば, 詳しく説明するかもしれません.

あぁ, 確かにひっかかりますね....
この問題を理解するためにはもちろん「反射律」, 「対称律」, 「推移律」を理解しなければならないんですが, 根底には「数学における『ならば』の意味」というポイントがひそんでいます.
日常での「A ならば B」という表現では, 「A が成り立たないとき」は考えていません. しかし, 数学における「A ならば B」は, 「A が成り立っているときには B も成り立つ」, つまり「A が成り立っていないときには B が成り立つかどうかに関係なく『A ならば B』は成り立つ」と解釈します...続きを読む


人気Q&Aランキング