回答編集履歴

1

解法解説

2017/07/04 16:12

投稿

swordone
swordone

スコア20649

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間が全経路中最長ということになるのです。