締切済み

K(3,3)完全二部グラフ非平面性グラフ理論

2014/11/10 18:03

連結な平面グラフにおいて位数=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)

2014/11/10 23:34 回答No.1

「逆必ずしも真ならず」ってやつだ. 正確には「裏必ずしも真ならず」というべきかもしれんが.

関連する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
グラフ理論の問題

グラフ理論の問題で分からないものがあります。次の問題の答えがわかる方は、解答を教えてください。単純グラフG＝(V,E)で、分離度ｋ＝１のとき、｜V｜＝ｐ、｜E｜＝ｑであるなら、次の式が成り立つことを証明せよ。　　ｐ－１＜＝ｑ＜＝(１／２)×ｐ×(ｐ－１) よろしくお願いします。
グラフ理論の問題

ちょっとした定理なのですが… Vを頂点集合としてKをVの部分集合とする。KがグラフGのクリークをなすための必要十分条件は、V-K がGの補グラフG^の頂点被覆になることである。図で証明は出来るのですが、数式ではキビシい感じなんです。これは一体どうすれば宜しいのでしょうか？
直線と平面の平行

立体幾何学の証明で疑問があったので質問します。平面に平行な直線に、その平面上の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)が命題の左辺に等しくなるにはどうすればよいのでしょうか。。
グラフの問題

正しくないものを選ぶ問題なのですが、 (1)有限グラフのすべての頂点の次数が奇数であるとき、頂点の数は偶数である。 (2)連結グラフから分離辺を除いたグラフは、２つの連結成分をもつグラフである。 (3)連結グラフから分離辺を集めて得られるグラフの連結成分は樹木である。 (4)組み合わせグラフは平面グラフである。 (5)完全グラフは組み合わせグラフである。 (4)(5)は正しいのはわかるのですが、(1)～(3)のどの部分がまちがっているのかわかりません。教えてください。
グラフ理論の問題について

Gをn個の頂点とM本の辺を含む、以下の条件を満たすグラフとします。このグラフの全ての辺をk通りの異なる色に彩色したとき、そのうち任意のm個の異なる色が選ばれたとしても残りのk-m色のみで塗られた辺によって出来た部分グラフが連結であるような彩色の仕方が存在する。ここでk,n,mをパラメーターとした時、「最小の」Mの値を求めたいのですが、m=1の時の解しか得られませんでした。どのようなグラフ理論的なテクニックを用いてこの問題を解くべきなのでしょうか？この種の問題は一般的にグラフ彩色の問題として分類されるのでしょうか？なにか一般解を得るためのヒントや手助けとなりそうなアイディアや論文などありましたらお教え願いたいです。
オイラーグラフの十分条件について

グラフ理論についての質問です。よろしくお願いします。「グラフGのすべての辺eについてeを含むサイクルが奇数個ならば、Gはオイラーグラフ」を証明したいです。「辺を含むサイクルの個数」という条件をどう活かすかが思いつかず、背理法で示そうとしましたが、そちらもうまくいきません。（最長のトレイルPを定めて、「Pに含まれない辺を含むサイクル」を用いてPの最長性に矛盾させる方針で考えていました）また、そもそもGは連結という条件が必要だと思うのですが（非連結でもよいとすると各連結成分がサイクルであるグラフが反例になってしまうので）、問題文中にそのような記載は特にありませんでした。非連結だとオイラーグラフにはなり得ないので、自明な前提として省略している可能性もあるとは思いますが、「Gは連結である」ということは暗に認めてしまっても良いものなのでしょうか？以上になります。ご教示いただければ幸いです。
情報数学　単純無向グラフについての問題

G が切断点を持てば,G は橋を持つ　正しくない G = (V, E) が連結,かつ |E| < |V | ならば,G は無向木である　正しいすべての完全グラフの直径は 1 である　正しい節点数 5 の完全グラフ K5 は平面描画可能である　正しくないそれぞれの理由を教えてほしいです。
一筆書き可能の証明

ケー二スバルグの橋の問題から、下のことが出てきました。 (1) 連結な平面グラフの各頂点が偶数個の辺に隣接している⇒ 連結な平面グラフは、同一の始点・終点を持つように一筆書き可能である。 (2) 連結な平面グラフのちょうど２つの頂点が奇数個の辺に隣接し、残りのすべての頂点は、偶数個の辺に隣接している⇒連結な平面グラフは異なる始点・終点をもつように一筆書き可能 (1)、(2)をそれぞれ、証明したいのですが、なかなかできません。どなたか教えていただけないでしょうか？
位数45の群が位数9の正規部分群をもつことの証明はどうすればいいのでし

位数45の群が位数9の正規部分群をもつことの証明はどうすればいいのでしょうか？シローの定理が必要だとおもうのですが。。。 <シローの定理> (1)p^r | |G| ==> Gは位数p^rの部分群をもつよってシローp-部分群は存在する (2)H: Gのp-部分群とすれば Hを含むシローp-部分群が存在する (3)シローp-部分群は互いにG共役 (4)シローp-部分群の個数は 1+k*p の形 (k∈Z,k≧0)
グラフの証明を教えてください

背理法の証明で連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときのそのうち最も辺の少ないグラフをＧとしますＧの中のツアーで中で、最も辺の数が多いものをＣとします。そのときＧからＣの辺をすべて取り除いたグラフの連結成分ＨがあるとしたときＨの各頂点の次数は偶数である。この証明を教えてください。
平面図形について

高3で数学の勉強をしています。 MARCHの理工学部志望で現在黄チャートをひたすら解いています。ところでIAにある平面図形の分野なんですが、センターや私大入試の過去問を見る限り全く出題されてない気がします。平面図形は入試には出ないんでしょうか？チェバ、メテラウス、接弦定理や法べきの定理、内心、重心などはベクトルで使うことはあるので、最低限公式の理解と暗記はやっておくべきだと思うんですが、チャートの例題や章末にある平面図形の特有の問題(ex.証明)問題は入試に出ないのでやらなくていいんでしょうか？時間がなくて焦っています。
平面上の３直線の平行関係

平面上の３直線の平行関係『同一平面上の直線p, q , rにおいて、 p//q , p//r　ならばq//r』は中学レベルの初等幾何で証明可能でしょうか？平行の定義は「どこまでいっても交わらない」「２直線がある直線と垂直に交わる」などあるみたいですが、どちらでも結構ですので、よろしくお願いします。
ケー二スバルグの橋の問題（一筆書き）

以前、他の方が、聞いてましたが、もっと具体的にケー二スバルグの橋の問題（一筆書き）を。 (1) 連結な平面グラフの各頂点が偶数個の辺に隣接している⇒ 連結な平面グラフは、同一の始点・終点を持つように一筆書き可能である。 (2) 連結な平面グラフのちょうど２つの頂点が奇数個の辺に隣接し、残りのすべての頂点は、偶数個の辺に隣接している⇒連結な平面グラフは異なる始点・終点をもつように一筆書き可能 (1)、(2)をそれぞれ、数学的帰納法を用いて、証明したいんです。自分でやってみたんですが、うまくいかないんです。力を貸して頂けないでしょうか？どなたか教えていただけないでしょうか？
座標平面状にＯ（０，０）Ａ（１，０）を取る。この平面上の２点Ｐ，Ｑを条

座標平面状にＯ（０，０）Ａ（１，０）を取る。この平面上の２点Ｐ，Ｑを条件（ａ）ＯＰ＝１、∠ＡＱＰ≦９０° （ｂ）ＰＱ＝１，∠ＯＰＱ≧９０° を満たすように動かす。ただし角の大きさは０°から１８０°までの範囲で測るものとする。＜問＞点Ｑの動く領域を求め、図示せよ。この問題がわかりません。できるだけやさしくご教授ください。
巡回群について

「Gを位数nの巡回群とする．このとき，Gの部分群の位数はnの約数で，各約数に対してただ一つ存在する．」この証明でいくつか分からなかったので教えてください．（以下証明） G=<g>とし，m|nであるとする．ここでn/m=cとおくと，<g^c>は位数mの巡回部分群になる．また，これと異なる位数mの巡回部分群Sが存在すると仮定する． g^k∈S （kはこれを満たす最小の正整数）とすると，剰余の定理から n=qk+r （0<q∈Z，0≦r<k）となるq,rが存在する．このとき， g^r=g^(n-qk)=g^n(g^(-k))^q∈S で，kの最小性よりr=0を得る．よってn=qkとなり，Sの位数はqとなる．－(1) したがってm=qとなり，S=<g^c>．－(2) 以上より，nの約数に対して，ただひとつの巡回部分群が存在する．（証明終）この証明の最後の， (1)：Sの位数はqとなる (2)：S=<g^c> の部分がわかりませんでした． (1)について (g^k)^q=g^qk=g^n=e となりますが，これより「Sの位数はq」ということですか？ (2)については包含関係を示しているのでしょうか？その辺がよくわかりませんでした．長文申し訳ありませんがよろしくお願いいたします．
「直線m , nが平行で、平面pがmを含み、nを含まなければ、p//n

「直線m , nが平行で、平面pがmを含み、nを含まなければ、p//n」の証明この定理の証明を教えて頂きたいのですが。調べても見つけられなかったのですが、この証明が載っている本、HPをご存じでしたらご紹介ください。よろしくお願い致します。

K(3,3)完全二部グラフ非平面性グラフ理論

みんなの回答

関連するQ&A

グラフ理論について

グラフ理論の問題についての質問です

グラフ理論においての「木」

グラフ理論の問題

グラフ理論の問題

直線と平面の平行

"平面"におけるグリーンの定理の証明

グラフの問題

グラフ理論の問題について

オイラーグラフの十分条件について

情報数学　単純無向グラフについての問題

一筆書き可能の証明

位数45の群が位数9の正規部分群をもつことの証明はどうすればいいのでし

グラフの証明を教えてください

平面図形について

平面上の３直線の平行関係

ケー二スバルグの橋の問題（一筆書き）

座標平面状にＯ（０，０）Ａ（１，０）を取る。この平面上の２点Ｐ，Ｑを条

巡回群について

「直線m , nが平行で、平面pがmを含み、nを含まなければ、p//n

注目のQ&A

カテゴリ
一覧

専門家に質問してみよう
専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

K(3,3)完全二部グラフ 非平面性 グラフ理論

みんなの回答

関連するQ&A

グラフ理論について

グラフ理論の問題についての質問です

グラフ理論においての「木」

グラフ理論の問題

グラフ理論の問題

直線と平面の平行

"平面"におけるグリーンの定理の証明

グラフの問題

グラフ理論の問題について

オイラーグラフの十分条件について

情報数学 単純無向グラフについての問題

一筆書き可能の証明

位数45の群が位数9の正規部分群をもつことの証明はどうすればいいのでし

グラフの証明を教えてください

平面図形について

平面上の３直線の平行関係

ケー二スバルグの橋の問題（一筆書き）

座標平面状にＯ（０，０）Ａ（１，０）を取る。この平面上の２点Ｐ，Ｑを条

巡回群について

「直線m , nが平行で、平面pがmを含み、nを含まなければ、p//n

注目のQ&A

カテゴリ 一覧

専門家に質問してみよう 専門家登録

あなたにピッタリな商品が見つかる！ OKWAVE セレクト

K(3,3)完全二部グラフ非平面性グラフ理論

情報数学　単純無向グラフについての問題

カテゴリ
一覧

専門家に質問してみよう
専門家登録