グラフの問題

質問

正しくないものを選ぶ問題なのですが、

(1)有限グラフのすべての頂点の次数が奇数であるとき、頂点の数は偶数である。

(2)連結グラフから分離辺を除いたグラフは、２つの連結成分をもつグラフである。

(3)連結グラフから分離辺を集めて得られるグラフの連結成分は樹木である。

(4)組み合わせグラフは平面グラフである。

(5)完全グラフは組み合わせグラフである。

(4)(5)は正しいのはわかるのですが、(1)～(3)のどの部分がまちがっているのかわかりません。
教えてください。

回答No.4

graphaffine

まだ締め切られていないようなので、ちょっと突っ込み。

組合せグラフと言う用語は有ります。で、具体的な定義は失念しましたが、#3で書いているようなものではないはず。#3で言ってる組合せグラフとは一般的には単純グラフと言います。そのテキストは、あまり言葉づかいが良くないようですね。
グラフ理論は、幾何学と関係無いのに、幾何入門と言う
科目名も気になるし。

が、

回答No.3

hinarikako

この問題は放送大学平成16年度2期「幾何入門」の通信指導問題です。この問題は他人の教えで回答するのは
ルール違反で不正行為となります。今後このようなことはしてはいけません。提出期限である12月2日以後に教えを請いましょう。この回答はNO１さんの適切な助言があるように、組み合わせグラフの定義は印刷教材ｐ９０に記載しています。よく見てください。因みに組み合わせグラフとは重複辺、ループ辺のないグラフです。したがって（４）が誤りです。

回答No.2

gakutensoku

再びgakutensokuです。

すみません、補足情報を頂けていないような気がするのですが、、、

> これが有向グラフか、無向グラフか多重辺やLOOPを含むかは私には知識がなく区別できません。

知識ではありません。
お使いの参考書なり、お受けになっている講義なりの最初で、「グラフとは何であるか」という定義がなされていたいたはずです。
そこでの内容をご自身の中で確認していただきたいのです。

・有向グラフか、無向グラフ
これは、辺に向きを考えるかどうかというものです。
2つの頂点a,bに対して、aからbへ向かう辺と、bからaへ向かう辺を区別する場合、一般的な用語では有向グラフと呼びます。
また、2つの頂点a,bに対して、方向を区別せず単に「aとbを結ぶ辺」とするもののことを、一般的な用語では無向グラフと呼びます。
(もちろん、yamakenn1111さんがご使用の書籍or講義では別の名前で呼ばれている可能性もあります。)

・多重辺やLOOPを含むか
これは、「2つの頂点を結ぶ、複数の辺が存在する」ことや「ある頂点から出て、自分自身に戻ってくるような辺の存在」が許されるかどうか問いうものです。

このような定義のあと、「本書(本講義)では単純に『グラフ』と言った場合、○○○○のような条件を満たすグラフを意味するものとする」などとするのが一般的です。

同様に、
・有限グラフ
・頂点の次数
・連結グラフ
・分離辺
・連結成分
・樹木
・組み合わせグラフ
・平面グラフ
・完全グラフ
の定義が正しく理解できているか、ご確認ください。

グラフ理論での議論や証明においては、もともとの定義に立ち返る事が非常に多く、定義を正しく理解することが大変重要です。(というか、定義をおろそかにした状態では議論することは不可能です。)

> ということは（５）が間違いなんでしょうか？
> 間違えました（４）ですね。

「組み合わせグラフ」が何者であるか分からないので、なんともいえません。
ただ、両方が正しいとすると、#1で書いたように「完全グラフは平面グラフである」ということになりますので、少なくともどちらか片方は誤りであると思われます。(ここで、「平面グラフ」および「完全グラフ」の定義は、私学習した定義によります。別の定義によれば、別の結論が出るかも知れません。)

それではお勉強がんばってください。

回答No.1

gakutensoku

補足要求です。

グラフ理論の用語って、書籍によって定義が異なることが多くあります。

たとえば単純に「グラフ」と言った場合でも。
・有向グラフか、無向グラフか
・多重辺やLOOPを含むか
など様々な定義が考えられます。

設問の前提となる条件の確認をお願いいたします。

特に「組み合わせグラフ」というのは聞きなれない用語なのですが、どのようなグラフのことなのでしょうか?

それから、
>(4)(5)は正しいのはわかるのですが
とおっしゃっていますが、これは正しいでしょうか?

(4)と(5)が正しいとすると、

完全グラフは組み合わせグラフである
組み合わせグラフは平面グラフである

から

完全グラフは平面グラフであるということになりますが、頂点数が5以上の完全グラフは平面グラフではありません。

お礼

間違えました（４）ですね。

補足

グラフっていろんな定義があるんですか～～！！
しらなかったです。
オイラーほこうをつかったケーニヒスベルクの問題などしております。これが有向グラフか、無向グラフか多重辺やLOOPを含むかは私には知識がなく区別できません。すいません。ただ、よく考えたら組み合わせグラフは平面グラフだと私がかってに解答し決め付けておりましたが、確かに５つ以上あるときは平面グラフになりませんね！！？
ということは（５）が間違いなんでしょうか？