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

質問

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

回答No.2

cetus · ベストアンサー

下記に証明があります。
(2章の9.を見てください)

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

お礼

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

回答No.1

gakutensoku

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

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

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

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

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

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

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

お礼

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