グラフ理論 最長道の共通点

質問

『連結グラフに複数の最長道（もっとも長いパス）が存在するとき，それらのうちの任意の二つの最長道は，必ず共通点を持つ（最低でも一か所は同じ点を通る）』

と教わりました．しかし，なぜそうなるのでしょうか．

http://coolee.at.infoseek.co.jp/graph_ensyuu_sol.html#2
の「第２章　９．」も参照しましたが，今一つよく分かりません．

分かりやすい，証明・解説をお願いします．

回答No.2

SortaNerd_ · ベストアンサー

1. 共通点を持たない2つの最長道AとBが存在したとする。
2. その2つの最長道をつなぐパスCを考える。
3. 最長道AおよびBをCとの共通点でそれぞれ2つに分けたとき、Aの長いほう+Bの長いほう+CはAやBより長い。

ということだと思います。
OKWaveの新機能で画像が添付できるようになったので図をつけておきます。

参考URL：

http://okwave.jp/qa4519710.html

回答No.7

lmsjdff

>ところで：　No.5 の「反例」で、
>頂点 2, 5, 8 は、共有されてないですか？

すべての最長パスに共有される点は存在しません。
No.5の隣接行列であらわされるグラフをGとします。
Gは12の頂点と15の辺をもつ連結グラフです。
12の頂点を、1,2,3,…,12 とし、
頂点1と頂点2を結ぶ辺を(1,2)というふうに書くことにします。
Gの15の辺は、
(1,2),(2,3),(2,9),(3,4),(3,10),(4,5),(4,11),
(5,6),(5,12),(7,8),(8,10),(8,11),(9,11),(9,12),(10,12) です。
Gには、次に示すような、少なくとも9個の最長パスがあります。

7-8-10-12-9-2-3-4-5-6,
7-8-10-3-4-11-9-12-5-6,
7-8-10-12-5-4-11-9-2-1,
7-8-10-3-2-9-11-4-5-6,
1-2-3-10-8-11-9-12-5-6,
1-2-3-4-11-9-12-10-8-7,
1-2-3-10-12-9-11-4-5-6,
1-2-3-4-5-12-9-11-8-7,
1-2-3-10-12-5-4-11-8-7.

これらの9個のパス全てに共通に含まれる頂点は存在しません。

回答No.6

arrysthmia

陳謝と訂正：　No.4 は取り下げます。
最長パスが奇数辺なら、中点は存在もしませんね。

ところで：　No.5 の「反例」で、
頂点 2, 5, 8 は、共有されてないですか？

回答No.5

lmsjdff

連結グラフGにおいて、
「Gのすべての最長道に共有される点が存在する」
と Gallai は予想していたようです。
しかし、この予想は正しくないことがわかっています。
隣接行列が次のように表されるグラフには、
Gのすべての最長道に共有される点は存在しません。
この反例は H.J.Walther によるものだそうです。

[0 1 0 0 0 0 0 0 0 0 0 0 ]
[1 0 1 0 0 0 0 0 1 0 0 0 ]
[0 1 0 1 0 0 0 0 0 1 0 0 ]
[0 0 1 0 1 0 0 0 0 0 1 0 ]
[0 0 0 1 0 1 0 0 0 0 0 1 ]
[0 0 0 0 1 0 0 0 0 0 0 0 ]
[0 0 0 0 0 0 0 1 0 0 0 0 ]
[0 0 0 0 0 0 1 0 0 1 1 0 ]
[0 1 0 0 0 0 0 0 0 0 1 1 ]
[0 0 1 0 0 0 0 1 0 0 0 1 ]
[0 0 0 1 0 0 0 1 1 0 0 0 ]
[0 0 0 0 1 0 0 0 1 1 0 0 ]

回答No.4

arrysthmia

蛇足ですが：　その証明は、
複数の最長パスは、共通の中点で交わらなければならない
ということでもあります。

回答No.3

SortaNerd_

ポップアップが止められてしまい画像添付に失敗しました。
改めて添付します。

回答No.1

Tacosan

概略図を描けば, その証明はほとんど明らかだと思いますが....
どこまでが理解できて, どこからがわからないんでしょうか?