- 締切済み
グラフの問題
正しくないものを選ぶ問題なのですが、 (1)有限グラフのすべての頂点の次数が奇数であるとき、頂点の数は偶数である。 (2)連結グラフから分離辺を除いたグラフは、２つの連結成分をもつグラフである。 (3)連結グラフから分離辺を集めて得られるグラフの連結成分は樹木である。 (4)組み合わせグラフは平面グラフである。 (5)完全グラフは組み合わせグラフである。 (4)(5)は正しいのはわかるのですが、(1)～(3)のどの部分がまちがっているのかわかりません。 教えてください。
- yamakenn1111
- お礼率25% (2/8)
- 数学・算数
- 回答数4
- ありがとう数2
- みんなの回答 （4）
- 専門家の回答
みんなの回答
- graphaffine
- ベストアンサー率23% (55/232)
まだ締め切られていないようなので、ちょっと突っ込み。 組合せグラフと言う用語は有ります。で、具体的な定義は失念しましたが、#3で書いているようなものではないはず。#3で言ってる組合せグラフとは一般的には単純グラフと言います。そのテキストは、あまり言葉づかいが良くないようですね。 グラフ理論は、幾何学と関係無いのに、幾何入門と言う 科目名も気になるし。 が、
- hinarikako
- ベストアンサー率0% (0/6)
この問題は放送大学平成16年度2期「幾何入門」の通信指導問題です。この問題は他人の教えで回答するのは ルール違反で不正行為となります。今後このようなことはしてはいけません。提出期限である12月2日以後に教えを請いましょう。この回答はNO１さんの適切な助言があるように、組み合わせグラフの定義は印刷教材ｐ９０に記載しています。よく見てください。因みに組み合わせグラフとは重複辺、ループ辺のないグラフです。したがって（４）が誤りです。
- gakutensoku
- ベストアンサー率35% (14/40)
再びgakutensokuです。 すみません、補足情報を頂けていないような気がするのですが、、、 > これが有向グラフか、無向グラフか多重辺やLOOPを含むかは私には知識がなく区別できません。 知識ではありません。 お使いの参考書なり、お受けになっている講義なりの最初で、「グラフとは何であるか」という定義がなされていたいたはずです。 そこでの内容をご自身の中で確認していただきたいのです。 ・有向グラフか、無向グラフ これは、辺に向きを考えるかどうかというものです。 2つの頂点a,bに対して、aからbへ向かう辺と、bからaへ向かう辺を区別する場合、一般的な用語では有向グラフと呼びます。 また、2つの頂点a,bに対して、方向を区別せず単に「aとbを結ぶ辺」とするもののことを、一般的な用語では無向グラフと呼びます。 (もちろん、yamakenn1111さんがご使用の書籍or講義では別の名前で呼ばれている可能性もあります。) ・多重辺やLOOPを含むか これは、「2つの頂点を結ぶ、複数の辺が存在する」ことや「ある頂点から出て、自分自身に戻ってくるような辺の存在」が許されるかどうか問いうものです。 このような定義のあと、「本書(本講義)では単純に『グラフ』と言った場合、○○○○のような条件を満たすグラフを意味するものとする」などとするのが一般的です。 同様に、 ・有限グラフ ・頂点の次数 ・連結グラフ ・分離辺 ・連結成分 ・樹木 ・組み合わせグラフ ・平面グラフ ・完全グラフ の定義が正しく理解できているか、ご確認ください。 グラフ理論での議論や証明においては、もともとの定義に立ち返る事が非常に多く、定義を正しく理解することが大変重要です。(というか、定義をおろそかにした状態では議論することは不可能です。) > ということは（５）が間違いなんでしょうか？ > 間違えました（４）ですね。 「組み合わせグラフ」が何者であるか分からないので、なんともいえません。 ただ、両方が正しいとすると、#1で書いたように「完全グラフは平面グラフである」ということになりますので、少なくともどちらか片方は誤りであると思われます。(ここで、「平面グラフ」および「完全グラフ」の定義は、私学習した定義によります。別の定義によれば、別の結論が出るかも知れません。) それではお勉強がんばってください。
- gakutensoku
- ベストアンサー率35% (14/40)
補足要求です。 グラフ理論の用語って、書籍によって定義が異なることが多くあります。 たとえば単純に「グラフ」と言った場合でも。 ・有向グラフか、無向グラフか ・多重辺やLOOPを含むか など様々な定義が考えられます。 設問の前提となる条件の確認をお願いいたします。 特に「組み合わせグラフ」というのは聞きなれない用語なのですが、どのようなグラフのことなのでしょうか? それから、 >(4)(5)は正しいのはわかるのですが とおっしゃっていますが、これは正しいでしょうか? (4)と(5)が正しいとすると、 完全グラフは組み合わせグラフである 組み合わせグラフは平面グラフである から 完全グラフは平面グラフであるということになりますが、頂点数が5以上の完全グラフは平面グラフではありません。
関連するQ&A
- グラフの証明を教えてください
背理法の証明で 連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの そのうち最も辺の少ないグラフをＧとします Ｇの中のツアーで中で、最も辺の数が多いものをＣとします。 そのときＧからＣの辺をすべて取り除いたグラフの連結成分Ｈがあるとしたとき Ｈの各頂点の次数は偶数である。 この証明を教えてください。
- 締切済み
- 数学・算数
- ケー二スバルグの橋の問題（一筆書き）
以前、他の方が、聞いてましたが、もっと具体的にケー二スバルグの橋の問題（一筆書き）を。 (1) 連結な平面グラフの各頂点が偶数個の辺に隣接している⇒ 連結な平面グラフは、同一の始点・終点を持つように一筆書き可能である。 (2) 連結な平面グラフのちょうど２つの頂点が奇数個の辺に隣接し、残りのすべての頂点は、偶数個の辺に隣接している⇒連結な平面グラフは異なる始点・終点をもつように一筆書き可能 (1)、(2)をそれぞれ、数学的帰納法を用いて、証明したいんです。自分でやってみたんですが、うまくいかないんです。 力を貸して頂けないでしょうか？ どなたか教えていただけないでしょうか？
- 締切済み
- 数学・算数
- グラフ理論について
全然分からなくて困っています。誰か助けてください。 １．グラフKn,Kn￣、Km,n,Cn,Tn〔Ｔnは位数nの木〕の染色数をそれぞれ求めよ。 ２．グラフKn,Km,n,Cn,Tnの辺染色数をそれぞれ求めよ。 ３．オイラーの多面体公式を証明せよ。 ４．以下の問題を証明せよ。 〔１〕頂点数が３以上の平面グラフGが極大平面グラフであるための必要十分条件は、Gのすべての領域が三角形であることである。 〔２〕４頂点以上の極大平面グラフGにおいて、 △〔G〕 不等式 Σ 〔6-i〕Ni =12 〔Ni = {次数がiの頂点の数}〕が成立する。 〔３〕４頂点以上の平面的グラフには、次数５以下の頂点が存在する。 〔４〕K5,K3,3は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。
- 締切済み
- 数学・算数
- 平面グラフの問いです。
平面グラフの頂点（節点）を凹凸多角形に、頂点連結用の辺（稜）を凹凸多角形の境界線に、それぞれ変換したとします。 その場合、元の平面グラフの連結性と、変換後の凹凸多角形の境界線共有性とは、同値になりますか。 つまり、平面グラフ頂点の彩色問題を、４色問題のような地図色分け問題に、変換できますか。
- ベストアンサー
- 数学・算数
- グラフの性質の問題について
以下の問題、よろしくお願いします。 点の集合と点同士とを結ぶ辺の集合とからなる図形をグラフと呼びます。以下では立方体の頂点と辺からなるグラフを一般化して出来るグラフの性質を考察します。正方形は2次元の立方体なので２-cubeと呼ばれます。立方体は３-cubeです。数学では次元の低い方にも一般化を行います。 ２点と２点を結ぶ直線からなるグラフは１-cubeです。n-cubeはn次元ユークリッド空間の超立方体の頂点と辺とからなるグラフです。nーcubeに関して以下の問に答えなさい。 問１ 全ての辺の長さを１とします。ある点を１度だけ通過して点と点をつなぐ辺を辿り、異なる２点を結ぶ経路をパスと呼びます。あるグラフの上で、任意の２点ｘ，yを結ぶパスp(ｘ，ｙ)の中でその長さ[p（ｘ，ｙ)] の最小値[p（ｘ，ｙ）］を点ｘ，ｙの距離と呼びます。グラフ上で［p（ｘ，ｙ）］の最大値のグラフを直径と呼びます。n-cubeの直径をnの式で表しなさい。 問２ 点の位置や辺の長さを自在に変えて曲線も許すとき、辺が交わらないように平面に作図可能なグラフを平面グラフと呼びます。２-cube、３-cubeは平面グラフですが、４-cubeはそうではありません。平面に描けないグラフを平面に描ける幾つかの部分に分解することができます。このとき、分解の最小数をグラフの厚さと呼びます。n-cubeの厚さをnの式で表しなさい。
- ベストアンサー
- 数学・算数
- 平面グラフは直線だけで描けるか？
頂点を３つもつ完全グラフK3は、正三角形の各頂点に頂点をおけば、そして、それを直線(線分)で結べば、その線分は正三角形の辺になります 頂点を４つもつ完全グラフK4は、長方形の各頂点に頂点をおけば、そして、それを直線(線分)で結べば、長方形の辺と対角線になります。しかし、対角線は交差してしまうので、どちらか一方を迂回させて(線分でなく)描くことになります。 しかし、正三角形の各頂点とその重心を頂点とすれば、線分の長さは２種類になりますが、K4でも線分で描けます。 頂点を５つもつ完全グラフK5は平面グラフにはなりません。それ以上の完全グラフでも平面グラフにはなりません。 そこで質問です。完全グラフに限らず、どんな平面グラフでも、変形さえすれば、頂点以外で曲がったりカーブしたりすることなく、描くことはできるのでしょうか？
- ベストアンサー
- 数学・算数
- オイラーグラフの十分条件について
グラフ理論についての質問です。よろしくお願いします。 「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」 を証明したいです。 「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。 （最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました） また、そもそもGは連結という条件が必要だと思うのですが（非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので）、問題文中にそのような記載は特にありませんでした。 非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか？ 以上になります。ご教示いただければ幸いです。
- ベストアンサー
- 数学・算数
お礼
間違えました（４）ですね。
補足
グラフっていろんな定義があるんですか～～！！ しらなかったです。 オイラーほこうをつかったケーニヒスベルクの問題などしております。これが有向グラフか、無向グラフか多重辺やLOOPを含むかは私には知識がなく区別できません。すいません。ただ、よく考えたら組み合わせグラフは平面グラフだと私がかってに解答し決め付けておりましたが、確かに５つ以上あるときは平面グラフになりませんね！！？ ということは（５）が間違いなんでしょうか？