出発点と終点が同じ点であるような一筆書き可能なグラフは、全ての点の次数が偶数であることを示せ。
この問題の解答をしてください。
一筆書きができるには次数が偶数でないと、その点に「入る」と「出る」ができないから。
「入る」と「出る」というのは下の図のような状態。
→・→
この図だと次数は2ですが、4であろうと6であろうと偶数である限り、出入が1セットになる。
しかし、そのどちらかしかない場合(奇数の場合)、「出入」のセットを消化していくと最終的に
入→・
か
出・→
が残って、出発点と終点が同じであるような一筆書きが可能なグラフはできない。
したがって、出発点と終点が同じ点であるような一筆書き可能なグラフは、全ての点の次数が偶数である。
ということでいいでしょうか?
http://www.hatena.ne.jp/1120485525-001ダミー:detail]
出発点と終点が同じという前提であれば
その図の全ての点に置いて、
入力数と出力数がイコールにならなければならないので、
ある点の入力数を(n)とすると、その点の次数は(2n)となる。
ゆえに、その図に属する全ての点の次数は偶数になる。
簡単に言うと
点に入ったら出るので、偶数でないと困る。
奇数だったら、入っても出られなくなる。
という事ですかね。
http://www.hatena.ne.jp/1120485525-002ダミー:detail]
ちょっと脇道になりますが、
出発点と終点が同じ点でなくても良いのならば、
次数が奇数となる点が2つ以下の場合、
その図は一筆書きで描くことができます。
http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E7%90%8...
グラフ理論 - Wikipedia
一筆書き可能なグラフということは、一つのサイクルもしくは、いくつかのサイクルで、グラフができているということなので、一筆書き可能なグラフは、全ての点の次数が偶数である。上手く説明できなくてゴメンナサイ。。。
http://www.hatena.ne.jp/ダミー:detail]
始点と終点が同一である一筆書きにおいて、線分上の任意の1点を見ると
その点に入る線と出て行く線を仮定した場合、それらの線は同数でなければならない。
入ってくる線がn本あれば、出て行く線も同数のn本である。
したがって、その任意の点における線分の数は2nとなり、nは整数だから
そのようなグラフの全ての点の次数は偶数となる。
で、どうでしょう。
http://baseball.yahoo.co.jp/npb/
Yahoo!�ץ�����
URLはダミーです。
出発点と終点が同じということは全てのの点は必ず入ったら出なければいけないので
n(入る道の数)+n(出る道の数)=2n
なので全ての点は偶数の次数になります
オイラーが解いたんだらしいんですが、
簡単に言うと、点には「開始点」「終了点」「(複数の)経過点」があります。
経過点は、入ってくる線と出て行く線が対(つまり2の倍数=2本)ないと一筆書きできません。
「出発点」は出て行く線1本+「出発線が途中で何度か経過点となる場合なら=偶数」なので必ず奇数となります。「終了点」同じ考えで、入ってくる線1本+経過点としての偶数線なので結局奇数。
ここで出発点と終点が同じであれば、、、奇数+奇数=偶数となります。
つまり、一筆書きでできる条件は
出発点と終点が同じ・・・すべての点が偶数線を持つ。
出発点と終点が別物・・・双方は奇数、それ以外はすべて偶数、、、となります。
コメント(0件)