人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

単純平面グラフには5次以下の点が少なくとも1点存在することを、以下の手順で示せ

(a)グラフの点の集合をV、辺の数をmとすると、
Σ_{v∈V}d(v)=2m
の関係があることを示せ。ただし、d(v)は点vの次数である。

(b)全ての点の次数を6以上として、点の数nとmの関係を求めよ。

(c)(b)の結果とm≦3n-6の関係より矛盾を導け。

よろしくお願い致します。

●質問者: gurugurucafe
●カテゴリ:学習・教育
✍キーワード:グラフ 存在
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● 186
●40ポイント

http://coolee.at.infoseek.co.jp/graphtheory2.html#10

?O???t???_?Q

http://coolee.at.infoseek.co.jp/graph_ensyuu_sol.html#10

?O???t???_???K????

URLはグラフ理論の解説のサイトです.

1番目は平面グラフについて扱っています. 2番目はその演習問題の略解です.

1番目の10章の演習問題の2がまさにその問題となっています.


a)

単純グラフなので各辺は頂点を二つずつ結ぶ. よって、辺の本数の二倍と、各頂点の次数の和は一致する.

従って?_{v ∈ V} d(v) = 2m.


b)

a)より

2m = ?_{v∈V} d(v) ≦ ?_{v∈V} 6 = 6n.

よってm ≦ n.


c)

b)より m ≦ 3n. よって矛盾.

「m≦3n-6」は頂点数が3以上の単純平面グラフについて言えます.

オイラーの定理から導いてください. これも1のサイトに載っています(定理10.1からその系の辺りを読んでください).

◎質問者からの返答

大変良い解答で助かりました。

ありがとうございます。

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ