面グラフの問題？？

質問

面グラフの問題かどうかわからないんですが…というか問題の意味すらわかってないんですけど…問題はこうです。

ある町はＹ字形の大きな川により３つの地区に分かれ、どの２地区も１本の橋で結ばれている。川の合流点の中州にはどの地区からも１本の橋が架かっていて渡ることができる。町のどこかの地点から歩き始めてこれら６本の橋を１度ずつ渡り、もとの地点に帰ることはできない。それはなぜか。また、このことができるためにはあと最低何本の橋があればよいか。

図を書いてみたんです。で・６本の橋で実際に「町のどこかの地点から歩き始めてこれら６本の橋を１度ずつ渡り…」をやってみました。普通に帰ってこれるんですけど！！私が問題のとらえ方を間違えてるんでしょうか？
わかる方、教えてください。

回答No.3

kash · ベストアンサー

オイラーの「ケーニヒスベルクの橋」のエピソードで有名な問題ですね。

＃１さんが指摘するように、恐らく「中洲」の存在を忘れているのではないかと。
問題文の「Ｙ字形」という表現が少し紛らわしいんですよね。
かといって文章だけで簡潔に表せるうまい言葉が浮かぶわけでもなく、図があったほうが一目瞭然ということでこちら↓を。

http://homepage3.nifty.com/sugaku/hasiwatari.htm

図が多少違いますが、考え方は一緒ですので。
要は、「奇数本の線が出ている点の数が２（始点・終点が一致する場合は０）であれば一筆書きが可能」ということです。

ここでは「同じ橋を２度通らずにすべての橋を渡ることは不可能」という証明までしかしていませんが、それを可能にするには、奇節点が２つ（又は０）になるように線を引けばいい訳です。

問題では「元の地点に帰る」とありますので、奇節点の数を０にする必要があります。
そのためには最低あと２本の橋が必要になりますね。

回答No.2

kony0

グラフ理論の問題ですね。

３つの地区＋中州の４つの節点と、任意の２つの節点を結ぶ枝が１つずつ、計６本の枝があるグラフになります。

このとき、すべての節点が奇節点となっているため、題意を満たすことができません。（一筆書き問題ですね）

すべての橋をちょうど１回ずつ渡れるようにするには、どこでもよいので橋を１つ掛ければできます。（奇節点２つと偶節点２つになるので）

題意を満たす、すべての橋をちょうど１回ずつ渡れる＆もとのところに戻るためには、すべての節点が偶節点になる必要があるため、上記に加え、もう１本橋をかければOK。

回答No.1

shushusyu

合っているかわからないけどもしかして中州がないのでは？