面グラフの問題かどうかわからないんですが…というか問題の意味すらわかってないんですけど…問題はこうです。
ある町はY字形の大きな川により3つの地区に分かれ、どの2地区も1本の橋で結ばれている。川の合流点の中州にはどの地区からも1本の橋が架かっていて渡ることができる。町のどこかの地点から歩き始めてこれら6本の橋を1度ずつ渡り、もとの地点に帰ることはできない。それはなぜか。また、このことができるためにはあと最低何本の橋があればよいか。
図を書いてみたんです。で・6本の橋で実際に「町のどこかの地点から歩き始めてこれら6本の橋を1度ずつ渡り…」をやってみました。普通に帰ってこれるんですけど!!私が問題のとらえ方を間違えてるんでしょうか?
わかる方、教えてください。
No.3ベストアンサー
- 回答日時:
オイラーの「ケーニヒスベルクの橋」のエピソードで有名な問題ですね。
#1さんが指摘するように、恐らく「中洲」の存在を忘れているのではないかと。
問題文の「Y字形」という表現が少し紛らわしいんですよね。
かといって文章だけで簡潔に表せるうまい言葉が浮かぶわけでもなく、図があったほうが一目瞭然ということでこちら↓を。
http://homepage3.nifty.com/sugaku/hasiwatari.htm
図が多少違いますが、考え方は一緒ですので。
要は、「奇数本の線が出ている点の数が2(始点・終点が一致する場合は0)であれば一筆書きが可能」ということです。
ここでは「同じ橋を2度通らずにすべての橋を渡ることは不可能」という証明までしかしていませんが、それを可能にするには、奇節点が2つ(又は0)になるように線を引けばいい訳です。
問題では「元の地点に帰る」とありますので、奇節点の数を0にする必要があります。
そのためには最低あと2本の橋が必要になりますね。
No.2
- 回答日時:
グラフ理論の問題ですね。
3つの地区+中州の4つの節点と、任意の2つの節点を結ぶ枝が1つずつ、計6本の枝があるグラフになります。
このとき、すべての節点が奇節点となっているため、題意を満たすことができません。(一筆書き問題ですね)
すべての橋をちょうど1回ずつ渡れるようにするには、どこでもよいので橋を1つ掛ければできます。(奇節点2つと偶節点2つになるので)
題意を満たす、すべての橋をちょうど1回ずつ渡れる&もとのところに戻るためには、すべての節点が偶節点になる必要があるため、上記に加え、もう1本橋をかければOK。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報