全然分からなくて困っています。誰か助けてください。
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-彩色可能である。
Knは完全グラフ _ Knは補グラフ Km,nは完全二部グラフ Cnはサイクル TnはN点からなる木 木:閉路(サイクル)を含まない連結グラフのこと
染色数と辺染色数は一番小さい数を答えとする。
オイラーの多面体公式とは、連結な平面グラフの頂点数V、辺数E、面数Fに対してV-E+F = 2となる公式 △(G) の△(G)は最大次数のこと i = 3 極大平面グラフとは平面グラフに可能なかぎり辺を加えてできる平面グラフ
softbank219199148044.bbtec.net (219.199.148.44)
Mozilla/5.0 (Windows NT 6.1; rv:2.0.1) Gecko/20100101 Firefox/4.0.1
|
|