- 締切済み
Fleauryのアルゴリズムについて
Fleauryのアルゴリズムについて Fleauryのアルゴリズムにおいて 現在いる点をvとする。vが開始点と同じ場合,vは橋に接続していないことを 証明せよ。 確かにそうだなぁ~~とは思うのですが証明方法が分かりません。分かる方、ご教授ください
- mattipolpol
- お礼率19% (8/42)
- 数学・算数
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- hrsmmhr
- ベストアンサー率36% (173/477)
回答No.2
補足ですが 設問はおそらく正確ではありません 全ての点が偶次数のグラフならオイラー小道があり、橋のある点を開始点にすることもできるはずです 証明は出ていく橋はないということで、橋がかかっているときには最後に戻ってくることに なると思われます
- hrsmmhr
- ベストアンサー率36% (173/477)
回答No.1
ｖが開始点なら、その時点で取り除かれた後のグラフにおいてｖの次数は偶数です （開始時に１つ取り除き、通過するごとに２つ取り除かれ、アルゴリズム上のそのステップにおいて１つ取り除かれるので） 次数２以上なら橋があっても渡ることはできずにアルゴリズムは進み、 オイラー小道が存在するなら最終的に０となるので 橋に接続していないと言えると思います
補足
たしかに.......