数学の問題を出し合う場所コミュの【一筆書き？の証明】

グラフ理論という分野があるようで、この分野には巡回セールスマン問題という有名な問題もあるようです。もう一つ有名な問題が・・・「ケーニヒスベルクの橋」でございます。
これはとても有名です。これを解いたのが・・恐れ多くて名前もだせない方でございます。。。

その問題がきっかけとなったようですが一般に
すべての辺を通りもとの点に戻るならば「全ての点において次数が偶数である必要がある」ようです。
元の点に戻れなくてもいい場合は、「次数が奇数である点がちょうど2つ」というのが条件のようです。
これは凄いことだと思います。
どのｻｲﾄもわかりやすくはありますが、とっつきにくいですね。点と辺はそのまんまで、次数というのは、なんてことはなくて点から出ている　辺の数　です。

問題】
任意の連結グラフにおいて、往復（同じ辺を逆に進む）を許すとき、すべての辺を通り出発した点に戻れることを証明せよ。

ただし往復は一回のみ可能とする
--------------------------------------------------

言い換えると、
どんな経路でも、一筆書きはできなくても「二筆書き可能」ということですね。直観的にはホントかよ？と
思ってしまいますが。

コメント(4)

最初
全て
最新の40件

[1] mixiユーザー 08月20日 22:49

少しこのモｿﾀﾞｲにはもんだいがあるみたいですね。

探偵の探偵

みたいな。

ちなみにハンネ変えました。半沢直樹っていつ続ヘソ　やるんでしょうか。

もう面白さ、1/4くらいになってますよ。倍返ししても半返しです。

[2] mixiユーザー 09月12日 08:28

いやたぶんOKでしょう。

暇なんで、答え書き込みたいんですが、いいですかね。

実は問題出しておいて、解答を忘れてしまったものがいくつかあります。

[3] mixiユーザー 09月13日 04:09

・・・どうなんでしょう。

グラフ理論ではジメイなんでしょうかわかりませんが。

そーれなので・・・

これが可能かどうかも含めて解答をお待ちしております。

当初はすぐに証明可能と考えていたんですが、むしろ不可能だと思いました。

しかしながらはじめとは違うなんとなくの証明を考えました。

言い忘れていたというより意図して書かなかったのかもしれません（もう出題時の記憶はありません）が、

頂点は何回通っても構いません。

これがないと
まず
無茶です。

[4] mixiユーザー 09月23日 20:39

あまりにも鮮やかに解けたので、
記念に
ルール違反を犯して、答えを↓

これは可能ですた。
2つのことを証明すれば、帰納法チックに解けます。

まず、連結グラフの点の個数をnとします。
ⅰ）与えらえた連結グラフは2筆書き可能
ⅱ）どの点から出発しても2筆書き可能

n=2のときは、自明。

n=kのとき成り立つとする。
これからn=k+1のとき
初めからn=kのときの経路のまま進み、新たな点とつながっている点まで来たら新たな点と往復するといういうやり方で経路を進むと、
成り立つ。

よって、すべての連結グラフで2筆書き可能

なんかエレガントじゃないな。
もっとズバッといえないかな。う～む＞＜

ログインすると、みんなのコメントがもっと見れるよ