OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
締切り
済み

グラフ理論の問題

  • 困ってます
  • 質問No.142970
  • 閲覧数122
  • ありがとう数2
  • 気になる数0
  • 回答数1
  • コメント数0

お礼率 41% (7/17)

グラフ理論の問題で分からないものがあります。
次の問題の答えがわかる方は、解答を教えてください。

単純グラフG=(V,E)で、分離度k=1のとき、|V|=p、|E|=qであるなら、
次の式が成り立つことを証明せよ。
  p-1<=q<=(1/2)×p×(p-1)

よろしくお願いします。
通報する
  • 回答数1
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

回答 (全1件)

  • 回答No.1
レベル8

ベストアンサー率 33% (10/30)

分離度1というのは全ての頂点が連結していると言うことでしょうか。 だとするとほぼ自明のような気がしますが。 厳密にやりたいというのなら帰納法を使えばよいでしょう。 とりあえずpー1<=qだけについてやってみます。 p=1の時 pー1<=qは成り立つ。 p<kの時 pー1<=qが成り立つと仮定すると p=kの時 Gのある頂点vとそれに付随する辺を取り去ったグラフをG'とする ...続きを読む
分離度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

以上よりp-1<=qは成り立つ。


てな感じです。
分離度の定義が違ったらごめんなさい。
お礼コメント
bat3

お礼率 41% (7/17)

ありがとうございます
参考になりました
投稿日時 - 2001-10-08 18:40:34


このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ