[ ホームページ ] [ 携帯用URL ]
DS 数学 BBS
大学以上の内容は DS 数学 BBS・2(携帯電話用)へ。
数学以外の話題は赤猫雑談掲示板で。
注意事項, 記号の書き方例をお読みになった上でご利用ください。

[ EZBBS.NET | 新規作成 | ランキング | オプション ]
iモード&(絵文字)、au対応!ケータイからも返信できる無料掲示板!
名前
 E-mail 
題名
内容

投稿KEY    タグ有効 改行有効 等幅フォント
URL
 
掲示板のTOP | 過去ログ集 | 投稿練習 | よく質問される問題 | エッセイblog



1092.Re: グラフ理論 木  
名前:通りすがり    日付:2020年6月22日(月) 1時50分
【訂正】
 2. G のオイラー標数(= G の辺の数 - 頂点の数)が 1 であること
より,G の辺の数を e とすると
 ・14 + 4v + 5w = 2e
 ・e -(14+v+w) = 1
が成立し,従って 2v + 3w = 16 となるはずです



 2. G のオイラー標数(= G の「頂点」の数 - 「辺」の数)が 1 であること
より,G の辺の数を e とすると
 ・14 + 4v + 5w = 2e
 ・「(14+v+w)-e」 = 1
が成立し,従って 2v + 3w = 12 となるはずです

に訂正します.
(回答者)
p1975128-ipngn2009091fukuokachu.fukuoka.ocn.ne.jp (153.177.213.128)
Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:77.0) Gecko/20100101 Firefox/77.0

1091.Re: グラフ理論 木  
名前:通りすがり    日付:2020年6月22日(月) 1時42分
> 図を描いて求めて、次数4の頂点が3個と次数5の頂点が2つと求めることができ、解答と一致していました。

ありうる全てのグラフを書いて求めたのであれば,それでも良いのですが,単に一つ具体例を挙げただけでは,証明になっていません.

そもそも問題文などに誤りはありませんか?

例えば,縦に線分 L をひき,その中間に L に垂直に交わり,互いに平行である 6 本の線分をひき(6 本の線分が串刺しになったような図を書く),交点と線分の端点を頂点とすれば,次数 1 の頂点(端末点)が 14個,その他の頂点の次数が 4(計 6 つ)の木ができ,問題の条件を満たしている様に思えますが…

少なくとも,単純グラフ G が木であり,次数 1 の頂点が 14 個,その他の頂点の次数が 4 または 5 であり,これらの頂点の個数がそれぞれ v,w ならば
 1. 握手補題
 2. G のオイラー標数(= G の辺の数 - 頂点の数)が 1 であること
より,G の辺の数を e とすると
 ・14 + 4v + 5w = 2e
 ・e -(14+v+w) = 1
が成立し,従って 2v + 3w = 16 となるはずです(グラフ理論に明るくないので,誤りがあるかもしれません).
(回答者)
p1975128-ipngn2009091fukuokachu.fukuoka.ocn.ne.jp (153.177.213.128)
Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:77.0) Gecko/20100101 Firefox/77.0

1090.グラフ理論 木  
名前:k    日付:2020年6月22日(月) 0時24分
グラフ理論の木に関する問題について

「端末点が14個ある1つの木において、すべての端末点でないの頂点の次数は4か5である。次数5の次数4の頂点の数を求めよ。」

という問題がありました。

この問題を自分で解いたのですが、図を描いて求めて、次数4の頂点が3個と次数5の頂点が2つと求めることができ、解答と一致していました。

しかし、この方法が正しい解の求め方かどうかがわかりません。この問題において自分で図を描いて解くという方法以外に木を構築する方法やアルゴリズムはありますでしょうか?
(大学 4 年/質問者)
flh2-133-203-242-128.tky.mesh.ad.jp (133.203.242.128)
Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/83.0.4103.106 Safari/537.36


「1090.グラフ理論 木」への返信

無料アクセス解析

アクセス解析の決定版!無料レンタルで最大100ページ解析!

公序良俗に反する投稿は無予告削除対象です。
   投稿KEY
   パスワード

EZBBS.NET produced by InsideWeb