• 締切済み

グラフ理論の問題

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

  • bat3
  • お礼率41% (7/17)

みんなの回答

  • nagata
  • ベストアンサー率33% (10/30)
回答No.1

分離度1というのは全ての頂点が連結していると言うことでしょうか。 だとするとほぼ自明のような気がしますが。 厳密にやりたいというのなら帰納法を使えばよいでしょう。 とりあえずpー1＜＝qだけについてやってみます。 p＝1の時 pー1＜＝qは成り立つ。 p＜kの時 pー1＜＝qが成り立つと仮定すると p＝kの時 Gのある頂点vとそれに付随する辺を取り去ったグラフをG'とする。 vの次数をnとするとGが連結グラフなのでG'は高々n個の連結成分に分かれる。 その連結成分をr1,r2,,,rm(m<=n)と置き、各連結成分の頂点数をp1,p2,,pm、 各連結成分の辺数をq1,q2,,,qmと置く。 G'の頂点数はkー1なので p1+p2+、、、+pm=k-1ーー(*) また各rは連結グラフで頂点数がk-1以下なので帰納法の仮定よりpi-1<=qiが成り立つ。 (*)に代入すると (q1+1)+(q2+1)+,,,(qm+1)>=k-1 q1+q2+,,,+qm+m>=k-1(**) ここでGの辺の数は各連結成分の辺の数と頂点vから出ている辺の数の和なので q=q1+q2+,,,+qm+n となります。 よって q=q1+q2+,,,+qm+n>=q1+q2+,,,+qm+m>=k-1=p-1 以上よりｐ－１＜＝ｑは成り立つ。 てな感じです。 分離度の定義が違ったらごめんなさい。

bat3
質問者

お礼

ありがとうございます 参考になりました

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

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

    大学のグラフ理論の問題でわからないものがあったので質問させていただきます。 ****************** 問題： グラフGが位数|V(G)|=nでk個の連結成分を持つグラフの時、辺数|E(G)|が n-k≦|E(G)|≦1/2(n-k+1)(n-k) をみたすことを示しなさい。 ******************* 以上の問題を帰納法をつかって証明しようとしたのですが、詰まってしまいました。 よろしければこの問題の証明方法を教えてください。 よろしくお願いします。

  • グラフ理論の問題

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

  • 【グラフ理論】証明問題が分かりません。【難問】

    テストに向けてグラフ理論の勉強をしているのですが・・・ 下記の証明問題で行き詰まってしまいました。 『uv ∉ E(G) → uw ∉ E(G)というグラフは完全K部グラフしか存在しない事を証明せよ。』 当方、証明問題に滅法弱く、どう解けば良いのか方針すら分かりません。 方針や証明の過程など詳しくご教授して頂ければ幸いです。 何卒宜しくお願い致します。

  • グラフ理論で

    グラフΓがtree（無閉路グラフ）であるとき、♯E（Γ）＝♯V（Γ）－１　が成り立つことを証明するという問題がわかりません。　教えていただけませんか？

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

    連結な平面グラフにおいて位数=p、サイズ=q,とおくと q=<3p-6 という公式？定理？がありますが、 完全二部グラフK(3,3)の非平面性を証明するのに使おうと思ったら 9<=18-6=12 で成り立ってしまいます。 すべての領域が四角形以上なら q=<2p-4というのを使えば証明できるのですが、前の方の公式がこの場合に使えないのはなぜなんでしょう

  • 続・グラフ理論

    Gを頂点数ｎ、変数ｍの単純グラフとし、PG(k)をGの彩色多項式をし、PG(k)のk^n-1の係数が－ｍであることを示せ。という問題で ・任意の辺 e に対し P(G, k) = P(G-e, k) - P(G/e, k) ・n頂点のグラフ G に対し, P(G, k) は k に関する整数係数 n次多項式かつ k^n の係数は 1 ・P(empty graph, k) = k^n まで出来たんですがk^n-1の係数が－ｍであることをどうやって示せばいいのでしょうか？ 再度すみません

  • 確率、グラフ理論(?)の質問です。

    以下の問題に途中まででもよいのでご回答よろしくお願いします。 少し間違っててもよいのでアドバイスをお願いします。 解答してみましたが、 I．１．平均：0 分散：2/3*n ２．e(k) = 10/3*e(k - 1) + 10/3*e(k + 1) ３．(不明) II．１．(解答できました) ２．(不明) ３．(不明) という状況です。 整合の方お願いします。 I．１つの粒子が数直線に沿って運動している。粒子は原点０から出発し、毎ステップごとに、等確率1/3でランダムに、-1または０または+1だけ移動する。以下の問いに答えよ。 １．ｎステップ後の粒子の位置の平均および分散を求めよ。ｎは正の整数とする。 ２．Ｌを正の整数とする。粒子は数直線上の-Lまたは+Lに到着すると運動を終了する。粒子がｋに位置するとき、運動を終了するまでに要するステップ数の期待値をe(k)と表す。ただし、ｋは、-L<k<Lを満たす整数であるとする。e(k),e(k-1),e(k+1)の間に成り立つ差分方程式を示せ。 ３．前問で求めた差分方程式の解はｋについての２次式で表される。e(k)を求めよ。ただし、終端条件をe(-L) = e(L) = 0とする。 II．すべての異なる頂点が辺で繋がっているグラフを完全グラフと呼び、頂点数がｎの完全グラフをKnで表す。図６．２と図６．３はそれぞれK5とK6の例である。完全グラフの辺を２通りにラベル付けをする。図６．１に完全グラフK4のラベル付け例を示す。以下では２通りのラベルの辺をそれぞれ実線と点線で表す。このとき次の問いに答えよ。 1. 図 6.1 のラベル付けには，同じラベルの３辺をもつ K3 が含まれない。同様にして，図 6.2 の完全グラフ K5 の辺を２通りにラベル付けして，同じラベルの３辺をもつ K3 が含まれないようにせよ。 2. 「6 人集まれば，互いに知り合いである 3 人組か，互いに見知らぬ 3 人組が必ず存在する」という命題がある。この命題を図6.3 に示した完全グラフ K6 の辺のラベル付けを利用して証明せよ。ただし，一方的に知っているという関係は考えない。 3. 完全グラフ K8 の辺を２通りにラベル付けする。このとき次の２種類の完全グラフを両方とも含まないようなラベル付けの例を示せ。 - 全ての辺が実線である完全グラフ K3 - 全ての辺が点線である完全グラフ K4

  • 相対性理論の問題です。

    相対性理論の問題です。 ローレンツ変換と固有時間で特殊相対性理論が分かってきましたが、式での計算問題となると答えがハッキリ分かりません。 20歳の双子の兄弟がいて、兄が宇宙旅行へ行き、地球上の弟が40歳になった時に兄が帰還しました。兄は相対性理論により弟より歳をとらないので、帰還した時30歳の若さでした。 この時ロケットの固有時間ｔは、地球上の時間Tと微小時間間隔の関係として、dt=dT√1-(v/c)^2と表せます。 ロケットの平均速度ｖは 1. v=0.0001c 2. v=0.01c 3. v=0.15c 4. v=0.85c 5. v=1.25c のうちどれでしょうか？ cは光速度です。 分かる方いらっしゃいましたら、宜しくお願いします。

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

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

  • 帰納法の証明で後一歩

    帰納法というんでしょうか、証明する問題を解いていますが後一歩でどうすればよいのか分かりません。 というか自分のやったところも書き方とかあっているかどうか分かりません。 問題の"any graph"というのも引っ掛かります。 Cycleが含まれるグラフだとVよりも大きくなるような気が…。 これがその問題です。 Let G = (V, E) be any graph. Prove the following claim: If there is any walk between vi ∈ V and vj ∈ V, then there must be a path of length no larger than |V|-1 between these two vertices. G = (V, E)はどんなタイプのグラフでもよいとする。次の主張を証明せよ: もしvi ∈ Vとvj ∈ Vの間にいくらかの歩行距離があれば、それらの二つの頂点の間には|V|-1よりも大きくない(つまり|V|-1よりも小さいか等しい)長さの経路が存在するはずである。 ※ちなみに|V|はVの絶対値ではなく、Vの全体の長さです。例えばV={v1, v2, v3}であれば|V|=3です。 自分のやったところまで書きます。 証明: もしvi ∈ Vとvj ∈ Vの間にいくらかの歩行距離があれば、 |(vi, vj)| <= |V|-1 であることを証明したい。 根拠: P(1)は真である、なぜなら |(v1, v2)| <= |{v1, v2}|-1 1 <= 2-1 1 <= 1 帰納的仮定: P(K)が真だと仮定すると |(v1, v2)(v2, v3)(v3, v4), ... ,(v_K-1, v_K)| <= |K|-1 そしてP(K+1)が真であることも証明しないといけないので |(v1, v2)(v2, v3)(v3, v4), ... ,(v_K-1, v_K)(v_K, v_K+1)| <= |K+1|-1 …これからどうすればいいのか分かりません。 |K+1|-1の部分はそのまま1をプラスマイナスして0なので |K|でいいと思うんですが、それが私の出来る精一杯です。 これからどうすればいいのか教えてください。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する