- 締切済み
K(3,3)完全二部グラフ 非平面性 グラフ理論
連結な平面グラフにおいて位数=p、サイズ=q,とおくと q=<3p-6 という公式？定理？がありますが、 完全二部グラフK(3,3)の非平面性を証明するのに使おうと思ったら 9<=18-6=12 で成り立ってしまいます。 すべての領域が四角形以上なら q=<2p-4というのを使えば証明できるのですが、前の方の公式がこの場合に使えないのはなぜなんでしょう
- domybestatall
- お礼率28% (11/38)
- 情報工学
- 回答数1
- ありがとう数13
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
「逆必ずしも真ならず」ってやつだ. 正確には「裏必ずしも真ならず」というべきかもしれんが.
関連する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は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。
- 締切済み
- 数学・算数
- グラフ理論の問題についての質問です
大学のグラフ理論の問題でわからないものがあったので質問させていただきます。 ****************** 問題： グラフGが位数|V(G)|=nでk個の連結成分を持つグラフの時、辺数|E(G)|が n-k≦|E(G)|≦1/2(n-k+1)(n-k) をみたすことを示しなさい。 ******************* 以上の問題を帰納法をつかって証明しようとしたのですが、詰まってしまいました。 よろしければこの問題の証明方法を教えてください。 よろしくお願いします。
- 締切済み
- 数学・算数
- グラフ理論においての「木」
（１）木はすべて二部グラフであることを証明せよ。 （２）どのような木が完全二部グラフとなるか？ についてそれぞれしりたいのですが・・・。（１）は自明なような気がしますが、きちんとした証明方法が知りたいです。片方だけでもいいのでお願いしますm(__)m
- ベストアンサー
- 数学・算数
- 直線と平面の平行
立体幾何学の証明で疑問があったので質問します。 平面に平行な直線に、その平面上の1点を通って平行に引いた直線は、元の平面に含まれる。・・・(1) という定理があります。 添付した図では、直線YY'と平面Pがあってこれが平行なときに、平面P上の1点Aを通過して、YY'に平行な直線XX'は平面P内に含まれるというものである。 この定理(1)から、平行２直線の1つの交わる平面は他の1つとも交わる・・・(2)の定理も導ける、と本に書いてあります。 題意は、平行線XX',YY'があるとき、一方のXX'と交わる平面Pは他の一方のYY'とも交わる。 証明は、もし仮に平面PがYY'に平行であるとすれば、XX'はP内に含まれなければならない。ゆえに、PはYY'に平行ではなく、したがって、YY'と交わる。 ここから疑問点を書きます。定理(2)は、XX'と交わる平面Pと仮定しているので、定理(1)の結論、YY'に平行な直線XX'は平面P内に含まれるというものである。を否定し対偶をとった証明になっていると自分は思ったのですが、平面と直線の位置の関係は、交わる、平行、平面が直線を含む。の3つあるので、XX'と交わる平面Pと仮定することは、直線XX'は平面P内に含まれるの否定になるのかどうかが、疑問です。平行の場合はどうなのかが考える必要があるのかどうかが分からないのです。 どなたか定理(1)を利用した定理(2)の証明の解説と、直線XX'は平面P内に含まれるは、直線XX'と交わる平面Pで否定できるかを解説してください。お願いします。
- ベストアンサー
- 数学・算数
- "平面"におけるグリーンの定理の証明
"平面"におけるグリーンの定理 平面領域Ｄとその境界∂ＤにてＰ(x,y),Ｑ(x,y),∂P/∂y,∂Q/∂xが連続ならば ∫[∂D](Pdx+Qdy)＝∬[D](∂Q/∂xー∂P/∂y)dxdyが成り立つ。 以上を、ガウスの発散定理を用いて証明することにトライしてみましたが旨くゆきません。 証明 ∬[D]divQ dD＝∬[D](∂Q/∂x＋∂Q/∂y)dxdy＝∫[∂D](Qdy＋Qdx)--(1) ∬[D]divP dD＝∬[D](∂P/∂x＋∂P/∂y)dxdy＝∫[∂D](Pdy＋Pdx)--(2) (1)第2辺－(2)第2辺＝∬[D]｛∂(Q－P)/∂x＋∂(Q－P)/∂y}dxdy＝∬[D](∂Q/∂xー∂P/∂y)dxdy＝命題の右辺--(3) (1)第3辺－(2)第3辺＝∫[∂D]｛(Q－P)dy＋(Q－P)dx}-----(4) (4)が命題の左辺に等しくなるにはどうすればよいのでしょうか。。
- ベストアンサー
- 数学・算数
- グラフ理論の問題について
Gをn個の頂点とM本の辺を含む、以下の条件を満たすグラフとします。 このグラフの全ての辺をk通りの異なる色に彩色したとき、そのうち任意のm個の異なる色が選ばれたとしても残りのk-m色のみで塗られた辺によって出来た部分グラフが連結であるような彩色の仕方が存在する。 ここでk,n,mをパラメーターとした時、「最小の」Mの値を求めたいのですが、m=1の時の解しか得られませんでした。どのようなグラフ理論的なテクニックを用いてこの問題を解くべきなのでしょうか？この種の問題は一般的にグラフ彩色の問題として分類されるのでしょうか？なにか一般解を得るためのヒントや手助けとなりそうなアイディアや論文などありましたらお教え願いたいです。
- ベストアンサー
- 数学・算数
- オイラーグラフの十分条件について
グラフ理論についての質問です。よろしくお願いします。 「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」 を証明したいです。 「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。 （最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました） また、そもそもGは連結という条件が必要だと思うのですが（非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので）、問題文中にそのような記載は特にありませんでした。 非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか？ 以上になります。ご教示いただければ幸いです。
- ベストアンサー
- 数学・算数
