- ベストアンサー
情報数学 単純無向グラフについての問題
G が切断点を持てば,G は橋を持つ 正しくない G = (V, E) が連結,かつ |E| < |V | ならば,G は無向木である 正しい すべての完全グラフの直径は 1 である 正しい 節点数 5 の完全グラフ K5 は平面描画可能である 正しくない それぞれの理由を教えてほしいです。
- akaheru0228
- お礼率61% (8/13)
- 数学・算数
- 回答数1
- ありがとう数2
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
G が切断点を持てば、G は橋を持つ → 正しくない 反例として、2 個の輪状グラフが 1 頂点を共有しているようなグラフ。 G = (V, E) が連結、かつ |E| < |V| ならば、G は無向木である 正しい 連結有向グラフの各頂点は流入辺を持ち、したがって |E| ≧ |V| である。 あとは、「連結無向グラフの辺の最小数は |E| = |V|-1 であり、そのとき グラフは木である」を、頂点数についての帰納法で。 すべての完全グラフの直径は 1 である 正しい 「完全グラフ」と「直径」の定義より自明 …としか言いようがない。 節点数 5 の完全グラフ K5 は平面描画可能である 正しくない 辺が囲む領域の数を f と置くと、平面グラフについて オイラーの公式 |V| - |E| + f = 2 が成り立つ。 また、単純グラフでは、辺が囲む各領域は頂点数 3 以上だから、 2|E| = 各領域を囲む辺数の総和 ≧ 3f でもある。 f を消去して 3|V| - |E| ≧ 6 だが、 K5 では、|V| = 5, |E| = 10 だから、この式は成り立たない。
関連するQ&A
- 情報数学 単純グラフの問題
この中で2部グラフはどれか ５個 正則グラフはどれか ４個 補グラフが非連結になるグラフはどれか ３個 オイラーグラフはどれか ３個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか ２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。
- 締切済み
- 数学・算数
- 情報数学 単純グラフの問題
この中で2部グラフはどれか ５個 正則グラフはどれか ４個 補グラフが非連結になるグラフはどれか ３個 オイラーグラフはどれか ３個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。
- 締切済み
- 数学・算数
- 情報数学 単純無向グラフについての問題
この中で2部グラフはどれか ５個 正則グラフはどれか ４個 補グラフが非連結になるグラフはどれか ３個 オイラーグラフはどれか ３個 辺を一本追加また削除するとオイラーグラフになるのはどれか 2個 橋 (bridge) を持つグラフはどれか２個 切断点 (cut point) を持つグラフはどれか ４個 分かる方教えてくださいお願いします。
- 締切済み
- 数学・算数
- グラフ理論の問題についての質問です
大学のグラフ理論の問題でわからないものがあったので質問させていただきます。 ****************** 問題： グラフGが位数|V(G)|=nでk個の連結成分を持つグラフの時、辺数|E(G)|が n-k≦|E(G)|≦1/2(n-k+1)(n-k) をみたすことを示しなさい。 ******************* 以上の問題を帰納法をつかって証明しようとしたのですが、詰まってしまいました。 よろしければこの問題の証明方法を教えてください。 よろしくお願いします。
- 締切済み
- 数学・算数
- グラフ理論について
全然分からなくて困っています。誰か助けてください。 １．グラフ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は非平面的グラフである。 〔５〕平面的グラフは５-彩色可能である。
- 締切済み
- 数学・算数
- 平面グラフの問いです。
平面グラフの頂点（節点）を凹凸多角形に、頂点連結用の辺（稜）を凹凸多角形の境界線に、それぞれ変換したとします。 その場合、元の平面グラフの連結性と、変換後の凹凸多角形の境界線共有性とは、同値になりますか。 つまり、平面グラフ頂点の彩色問題を、４色問題のような地図色分け問題に、変換できますか。
- ベストアンサー
- 数学・算数
- グラフの性質の問題について
以下の問題、よろしくお願いします。 点の集合と点同士とを結ぶ辺の集合とからなる図形をグラフと呼びます。以下では立方体の頂点と辺からなるグラフを一般化して出来るグラフの性質を考察します。正方形は2次元の立方体なので２-cubeと呼ばれます。立方体は３-cubeです。数学では次元の低い方にも一般化を行います。 ２点と２点を結ぶ直線からなるグラフは１-cubeです。n-cubeはn次元ユークリッド空間の超立方体の頂点と辺とからなるグラフです。nーcubeに関して以下の問に答えなさい。 問１ 全ての辺の長さを１とします。ある点を１度だけ通過して点と点をつなぐ辺を辿り、異なる２点を結ぶ経路をパスと呼びます。あるグラフの上で、任意の２点ｘ，yを結ぶパスp(ｘ，ｙ)の中でその長さ[p（ｘ，ｙ)] の最小値[p（ｘ，ｙ）］を点ｘ，ｙの距離と呼びます。グラフ上で［p（ｘ，ｙ）］の最大値のグラフを直径と呼びます。n-cubeの直径をnの式で表しなさい。 問２ 点の位置や辺の長さを自在に変えて曲線も許すとき、辺が交わらないように平面に作図可能なグラフを平面グラフと呼びます。２-cube、３-cubeは平面グラフですが、４-cubeはそうではありません。平面に描けないグラフを平面に描ける幾つかの部分に分解することができます。このとき、分解の最小数をグラフの厚さと呼びます。n-cubeの厚さをnの式で表しなさい。
- ベストアンサー
- 数学・算数
お礼
親切な解答ありがとうございます。