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

次の問に理由を付して答えよ

出発点と終点が同じ点であるような一筆書き可能なグラフは、全ての点の次数が偶数であることを示せ。

この問題の解答をしてください。

●質問者: gurugurucafe
●カテゴリ:学習・教育
✍キーワード:グラフ 一筆書き 偶数
○ 状態 :終了
└ 回答数 : 6/6件

▽最新の回答へ

1 ● ctrearr
●10ポイント

http://ja.wikipedia.org/wiki/%E4%B8%80%E7%AD%86%E6%9B%B8%E3%81%8...

一筆書き - Wikipedia

一筆書きができるには次数が偶数でないと、その点に「入る」と「出る」ができないから。

「入る」と「出る」というのは下の図のような状態。

→・→

この図だと次数は2ですが、4であろうと6であろうと偶数である限り、出入が1セットになる。

しかし、そのどちらかしかない場合(奇数の場合)、「出入」のセットを消化していくと最終的に

入→・

出・→

が残って、出発点と終点が同じであるような一筆書きが可能なグラフはできない。

したがって、出発点と終点が同じ点であるような一筆書き可能なグラフは、全ての点の次数が偶数である。

ということでいいでしょうか?


2 ● bakusee
●10ポイント

http://www.hatena.ne.jp/1120485525-001ダミー:detail]

出発点と終点が同じという前提であれば

その図の全ての点に置いて、

入力数と出力数がイコールにならなければならないので、

ある点の入力数を(n)とすると、その点の次数は(2n)となる。

ゆえに、その図に属する全ての点の次数は偶数になる。


簡単に言うと

点に入ったら出るので、偶数でないと困る。

奇数だったら、入っても出られなくなる。


という事ですかね。

http://www.hatena.ne.jp/1120485525-002ダミー:detail]

ちょっと脇道になりますが、

出発点と終点が同じ点でなくても良いのならば、

次数が奇数となる点が2つ以下の場合、

その図は一筆書きで描くことができます。


3 ● yoshidori
●10ポイント

http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%8...

グラフ理論 - Wikipedia

一筆書き可能なグラフということは、一つのサイクルもしくは、いくつかのサイクルで、グラフができているということなので、一筆書き可能なグラフは、全ての点の次数が偶数である。上手く説明できなくてゴメンナサイ。。。


4 ● dungeon-master
●20ポイント

http://www.hatena.ne.jp/ダミー:detail]

始点と終点が同一である一筆書きにおいて、線分上の任意の1点を見ると

その点に入る線と出て行く線を仮定した場合、それらの線は同数でなければならない。

入ってくる線がn本あれば、出て行く線も同数のn本である。

したがって、その任意の点における線分の数は2nとなり、nは整数だから

そのようなグラフの全ての点の次数は偶数となる。


で、どうでしょう。


5 ● sttjapan
●20ポイント

http://baseball.yahoo.co.jp/npb/

Yahoo!???????

URLはダミーです。

出発点と終点が同じということは全てのの点は必ず入ったら出なければいけないので

n(入る道の数)+n(出る道の数)=2n


なので全ての点は偶数の次数になります


1-5件表示/6件
4.前の5件|次5件6.
関連質問


●質問をもっと探す●



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