回答編集履歴
1
解法解説
test
CHANGED
@@ -7,3 +7,37 @@
|
|
7
7
|
直感的に考えると、最長候補はこの端から端までの長さということになります。それを調べるため、まず適当なところから一番遠い端を探し、その端から最も遠い端を探して最長としていることになります。
|
8
8
|
|
9
9
|
詳しい証明はこの問題でやっていることでしょう。
|
10
|
+
|
11
|
+
|
12
|
+
|
13
|
+
で、この証明ですが、まずsとtの経路とvとwの経路に共通部分があることを示すために、次の図のように点を設置しました(便宜上、人物に相当するものを点と呼びます)。
|
14
|
+
|
15
|
+
![点aと点b](58b6ca9c86ea03a1e6dd6fee1e888e57.jpeg)
|
16
|
+
|
17
|
+
これで、sからwまで、s→a→b→wとたどればいけます。
|
18
|
+
|
19
|
+
ただし、条件αから、st間はsからどこへ行くよりも遠いか同じなので、d(s,t)≧d(s,w)です。
|
20
|
+
|
21
|
+
これを各点までの長さに分割した式が(102)より、からの式です。
|
22
|
+
|
23
|
+
同じことをvw間とvt間でもやります。
|
24
|
+
|
25
|
+
その結果、ab間の距離が0以下という結論に至りましたが、距離は負になりませんので、ab間は0です。
|
26
|
+
|
27
|
+
これは、**aとbが同じ点である**ことを意味します。つまりこうなります。
|
28
|
+
|
29
|
+
![イメージ説明](aa9667eb3f3c4d56e2431d8b72d91b33.jpeg)
|
30
|
+
|
31
|
+
これで2つの経路に少なくとも1点共通部分があることが確定しました。
|
32
|
+
|
33
|
+
|
34
|
+
|
35
|
+
次に、こんな風に点cを設定します。
|
36
|
+
|
37
|
+
![イメージ説明](32e50b06c4ebf21f4a50bb087f499c74.jpeg)
|
38
|
+
|
39
|
+
前段と同じように、st間がsからの経路中最長であることを利用し、cからの距離比較を行います。vw間も同じです。
|
40
|
+
|
41
|
+
計算を進めると、ct間はcw間以上かつ以下、ということになったので、これを満たす関係は「ct間とcw間は等しい」しかありません。
|
42
|
+
|
43
|
+
そして、条件βからtu間はt起点経路中最長なので、tv間はそれ以下ということになりますが、先ほど示した「ct間とcw間は等しい」から、tv間はvw間と等しくなってしまい、「vw間はtu間以下」という帰結になります。しかしこれは最初の仮定の真逆です。つまり最初の仮定がおかしいということになり、tu間が全経路中最長ということになるのです。
|