- 締切済み
グラフ理論の問題についての質問です
- みんなの回答 (1)
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
左はほぼ自明なので省略. 右は「頂点数が n1, n2 である 2つの完全グラフの辺の本数の和」よりも「頂点数が (n1+n2-1) 及び 1 である 2つの (以下略) 」の方が小さくないことを示せば OK.
関連するQ&A
- グラフ理論の問題について
Gをn個の頂点とM本の辺を含む、以下の条件を満たすグラフとします。 このグラフの全ての辺をk通りの異なる色に彩色したとき、そのうち任意のm個の異なる色が選ばれたとしても残りのk-m色のみで塗られた辺によって出来た部分グラフが連結であるような彩色の仕方が存在する。 ここでk,n,mをパラメーターとした時、「最小の」Mの値を求めたいのですが、m=1の時の解しか得られませんでした。どのようなグラフ理論的なテクニックを用いてこの問題を解くべきなのでしょうか?この種の問題は一般的にグラフ彩色の問題として分類されるのでしょうか?なにか一般解を得るためのヒントや手助けとなりそうなアイディアや論文などありましたらお教え願いたいです。
- ベストアンサー
- 数学・算数
- 【グラフ理論】証明問題が分かりません。【難問】
テストに向けてグラフ理論の勉強をしているのですが・・・ 下記の証明問題で行き詰まってしまいました。 『uv ∉ E(G) → uw ∉ E(G)というグラフは完全K部グラフしか存在しない事を証明せよ。』 当方、証明問題に滅法弱く、どう解けば良いのか方針すら分かりません。 方針や証明の過程など詳しくご教授して頂ければ幸いです。 何卒宜しくお願い致します。
- 締切済み
- 数学・算数
- グラフ理論について
全然分からなくて困っています。誰か助けてください。 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-彩色可能である。
- 締切済み
- 数学・算数
- 数学的帰納法でこの問題に詰まっています
連続したk個の整数の積はk!で割り切れることを数学的帰納法で証明せよ。 という問題です。数学的帰納法というからには、nやn+1を使うのだと思うのですがよくわかりません。どなたか解法と解答をお願いします。
- ベストアンサー
- 数学・算数