- ベストアンサー
完全グラフが平面的となるための証明について
- みんなの回答 （2）
- 専門家の回答
関連するQ&A
- グラフ理論について
全然分からなくて困っています。誰か助けてください。 １．グラフ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は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。
- 締切済み
- 数学・算数
- グラフ理論について教えてください。
n,n,n-1,n-1,n-2,n-2,・・・・2,2,1,1(n:正の整数) というグラフがグラフ的かグラフ的でないかを理由と共に 調べています。 どなたか証明して頂けませんでしょうか？ よろしくお願いいたします。
- 締切済み
- 数学・算数
- 数学の証明の問題なのですが、まったく方向性もたてられず困っています。ど
数学の証明の問題なのですが、まったく方向性もたてられず困っています。どなたか教えていただけにあでしょうか？以下の問題です。 （１）∫1/(x^2+1)^(n+1) dx=(2n-1)!!・π/(2n)!! （２）∫x^n/x^n+1 dx=π/nsin(mπ/n) (0<m<n、nは奇数) １の積分範囲は-∞～∞で、２の積分範囲は0～∞です。 どなたかわかる方是非ご教授願えないでしょうか？ よろしくお願いします。。
- ベストアンサー
- 数学・算数
- 平面グラフの問いです。
平面グラフの頂点（節点）を凹凸多角形に、頂点連結用の辺（稜）を凹凸多角形の境界線に、それぞれ変換したとします。 その場合、元の平面グラフの連結性と、変換後の凹凸多角形の境界線共有性とは、同値になりますか。 つまり、平面グラフ頂点の彩色問題を、４色問題のような地図色分け問題に、変換できますか。
- ベストアンサー
- 数学・算数
- ハミルトングラフの証明
単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。 このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加した グラフG'もハミルトングラフである。 これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。 しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。 なにかうまい証明方法があればお教えください。 回答、よろしくお願いします。
- 締切済み
- 数学・算数
- K(3,3)完全二部グラフ 非平面性 グラフ理論
連結な平面グラフにおいて位数=p、サイズ=q,とおくと q=<3p-6 という公式？定理？がありますが、 完全二部グラフK(3,3)の非平面性を証明するのに使おうと思ったら 9<=18-6=12 で成り立ってしまいます。 すべての領域が四角形以上なら q=<2p-4というのを使えば証明できるのですが、前の方の公式がこの場合に使えないのはなぜなんでしょう
- 締切済み
- 情報工学
補足
グラフが平面的であるための必要十分条件は、K5あるいはK3,3に縮約可能な部分グラフを含まないことである。 ということでしょうか？ しかし、どのようにしてnの条件不等式を導出できるのでしょうか？