グラフ理論における最長パス

「連結グラフにおいて最長パスは必ず共通点を持つことを証明せよ」という問題を学校でだされたのですがどうしてもわかりません解き方をわかる方もしくはわかるサイトをお知りの方教えてください

No.2 ベストアンサー 回答者： cetus 回答日時： 2004/12/14 01:48

下記に証明があります。

(2章の9.を見てください)

http://coolee.at.infoseek.co.jp/graph_ensyuu_sol …

この回答へのお礼

非常に参考になりましたありがとうございます。とても助かりました。

お礼日時：2004/12/14 16:52

No.1 回答者： gakutensoku 回答日時： 2004/12/14 00:14

確認なのですが、"最長パス"が定義できるということなので、"パス"は重複辺を持たないということでよいですよね。

さて、設問なのですが、この問題で正しいでしょうか?

反例として、下記のグラフを考えます。
(アルファベットが頂点を表します。)

a－b－c－d－e－f－g

このグラフにおいて、2頂点間のパスは一意に決まり、そのパスは2頂点間の最長パスとなりますが、この
パスは共通点を持ちません。

それとも、私が「共通点」や「最長パス」の意味を取り違えているでしょうか?

「最短パスは共通点を持たないことを証明」なら分かるような気がするのですが、、、、、

この回答へのお礼

ありがとうございました。役だちました

お礼日時：2004/12/14 16:53