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


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

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

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

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

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2005/07/02 01:44:12
  • 終了:--

回答(1件)

id:smoking186 No.1

186回答回数74ベストアンサー獲得回数62005/07/02 02:03:41

ポイント40pt

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からその系の辺りを読んでください).

id:gurugurucafe

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

ありがとうございます。

2005/07/02 02:09:39
  • id:smoking186
    訂正

    b)の最後の式を書き間違えました。
    「2m = ��_{v∈V} d(v) ≦ ��_{v∈V} 6 = 6nよりm ≦ 3n」
    です。失礼。
  • id:dasm
    すごい

    昨日見つけて明日直ってなかったら指摘してやれウシシシとか思ってたのに。テレパシーが通じた。

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません