Fleauryのアルゴリズムについて

Fleauryのアルゴリズムについて

Fleauryのアルゴリズムにおいて
現在いる点をvとする。vが開始点と同じ場合,vは橋に接続していないことを
証明せよ。
確かにそうだなぁ~~とは思うのですが証明方法が分かりません。分かる方、ご教授ください

No.2 回答者： hrsmmhr 回答日時： 2011/06/29 19:42

補足ですが

設問はおそらく正確ではありません
全ての点が偶次数のグラフならオイラー小道があり、橋のある点を開始点にすることもできるはずです
証明は出ていく橋はないということで、橋がかかっているときには最後に戻ってくることに
なると思われます

この回答への補足

たしかに.......

補足日時：2011/06/30 09:29

No.1 回答者： hrsmmhr 回答日時： 2011/06/29 19:18

ｖが開始点なら、その時点で取り除かれた後のグラフにおいてｖの次数は偶数です

（開始時に１つ取り除き、通過するごとに２つ取り除かれ、アルゴリズム上のそのステップにおいて１つ取り除かれるので）
次数２以上なら橋があっても渡ることはできずにアルゴリズムは進み、
オイラー小道が存在するなら最終的に０となるので
橋に接続していないと言えると思います