ここから質問投稿すると、最大4000ポイント当たる!!!! >>

全然分からなくて困っています。誰か助けてください。

1.グラフKn,Kn ̄、Km,n,Cn,Tn〔Tnは位数nの木〕の染色数をそれぞれ求めよ。

2.グラフKn,Km,n,Cn,Tnの辺染色数をそれぞれ求めよ。

3.オイラーの多面体公式を証明せよ。

4.以下の問題を証明せよ。

〔1〕頂点数が3以上の平面グラフGが極大平面グラフであるための必要十分条件は、Gのすべての領域が三角形であることである。

〔2〕4頂点以上の極大平面グラフGにおいて、
   
      △〔G〕
  不等式 Σ 〔6-i〕Ni =12 〔Ni = {次数がiの頂点の数}〕が成立する。

〔3〕4頂点以上の平面的グラフには、次数5以下の頂点が存在する。

〔4〕K5,K3,3は非平面的グラフである。

〔5〕平面的グラフは5-彩色可能である。

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

A 回答 (2件)

なるほど, せいぜい「あんまり理解できてない」くらいの理解度だってことはわかった.



たとえば, 「補グラフ」を理解しているなら「単に『補グラフ』とだけ書いても無意味」ということまでわかっていなきゃいけない. つまり
_
Knは補グラフ
なんて書き方はしないはず.

そして,
・「グラフKn,Kn ̄、Km,n,Cn,Tn〔Tnは位数nの木〕」とはなんなのか
とわざわざ書かせたのは, これら (Kn ̄ は「補グラフ」では全く無意味なのでさしあたり無視) に関しては「染色数はわかるはず」だから. 辺彩色数はちょっと微妙なところがあるけど, 染色数は簡単にわからないとだめ.
    • good
    • 0

とりあえず


・「グラフKn,Kn ̄、Km,n,Cn,Tn〔Tnは位数nの木〕」とはなんなのか
・「染色数」や「辺染色数」はどのように定義されているのか
・「オイラーの多面体公式」とはどのような公式なのか
・「極大平面グラフ」とはいかなる条件を満たすグラフなのか
・「△〔G〕」が何を表すのか
くらいはきちんと書いてほしい.

もちろん, それができないならこんなところで聞いている場合じゃない.

この回答への補足

Knは完全グラフ
_
Knは補グラフ
Km,nは完全二部グラフ
Cnはサイクル
TnはN点からなる木
木:閉路(サイクル)を含まない連結グラフのこと

染色数と辺染色数は一番小さい数を答えとする。

オイラーの多面体公式とは、連結な平面グラフの頂点数V、辺数E、面数Fに対してV-E+F = 2となる公式
△(G)
 ∑ の△(G)は最大次数のこと
i = 3
極大平面グラフとは平面グラフに可能なかぎり辺を加えてできる平面グラフ

補足日時:2011/06/30 20:34
    • good
    • 0

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

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

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

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

Q平面グラフは直線だけで描けるか?

頂点を3つもつ完全グラフK3は、正三角形の各頂点に頂点をおけば、そして、それを直線(線分)で結べば、その線分は正三角形の辺になります

頂点を4つもつ完全グラフK4は、長方形の各頂点に頂点をおけば、そして、それを直線(線分)で結べば、長方形の辺と対角線になります。しかし、対角線は交差してしまうので、どちらか一方を迂回させて(線分でなく)描くことになります。

しかし、正三角形の各頂点とその重心を頂点とすれば、線分の長さは2種類になりますが、K4でも線分で描けます。

頂点を5つもつ完全グラフK5は平面グラフにはなりません。それ以上の完全グラフでも平面グラフにはなりません。

そこで質問です。完全グラフに限らず、どんな平面グラフでも、変形さえすれば、頂点以外で曲がったりカーブしたりすることなく、描くことはできるのでしょうか?

Aベストアンサー

ちょうど手元にあった本を見ただけで, web とかを参考にしたわけではないんですが....
「グラフ G が平面的 ⇔ G には K5 も K3,3 もマイナーとして含まない」
という有名な定理があるんですが, その証明方法 (の 1つ) として
[1] K5 も K3,3 もマイナーとして含まない, 5点以上の 3連結グラフは平面的
[2] K5 も K3,3 もマイナーとして含まない 5点以上のグラフは, 隣接していない 2点をうまく選ぶとその間に辺を加えて得られるグラフにはやっぱり K5 も K3,3 もマイナーとして含まれない
という 2つの命題を組合せる, というのがあるんですが, [1] を証明するときに実際に平面にグラフを描いていて, その描き方をよく見ると「単純グラフならどの辺も直線分で描ける」ことがわかるわけです.
手元で参考にした本は
Bernhard Korte and Jens Vygen, Combinatorial Optimization, Springer
ですが, グラフ理論の本で上の [1] を証明しているのがあれば多分どの本でもよいかと思います.

ちょうど手元にあった本を見ただけで, web とかを参考にしたわけではないんですが....
「グラフ G が平面的 ⇔ G には K5 も K3,3 もマイナーとして含まない」
という有名な定理があるんですが, その証明方法 (の 1つ) として
[1] K5 も K3,3 もマイナーとして含まない, 5点以上の 3連結グラフは平面的
[2] K5 も K3,3 もマイナーとして含まない 5点以上のグラフは, 隣接していない 2点をうまく選ぶとその間に辺を加えて得られるグラフにはやっぱり K5 も K3,3 もマイナーとして含まれない
という 2つの命題を...続きを読む


人気Q&Aランキング