質問: 慶應・環境情報学部の情報科目2017年度の「6次の隔たり」問題を解ける方いませんか? 来年、慶應を受ける浪人生です。 去年この問題がまったくわかりませんでした。 問題(24P~27P)→https://goo.gl/oBbrhH 自分なりにといてよくわからない所をまとめました。 ![イメージ説明](https://teratail.storage.googleapis.com/uploads/contributed_images/f93019507975ef61acc0a25503b7790c.png) --- 1すべてのx∉Gに対して友人の集合F(x)と書いていますが、図のようにxの友人のことをF(x)というという解釈で間違いないでしょうか? 2これはxの友達にyがいた場合のことを言っているのでしょうか? 3図にの解釈で間違いないでしょうか? 4なぜxとyの距離が(xとyの要素数)- 1 なのでしょうか? これは距離にyを含んでいるから-1なのでしょうか? 5これはまったく言いたいことがわかりません。一応自分の解釈を図にしました。 --- ![イメージ説明](https://teratail.storage.googleapis.com/uploads/contributed_images/e5f0b3a344f6b49063868fc6601c763a.png) --- 自分でわかるとこだけ解いていますが、たぶんあっていないところもあると思います。 番号のところは分からないところです。 ------------------ よろしくお願いいたします。
回答: ### 5に関して これを可能にしているのは、データの性質として3つ目に挙げられている「x,yの経路がただ1つ」と言うものです。これは言い換えれば、知り合いの知り合いの...と繋ぐ線が1本であり、**A↔B↔C↔Aのようにループする場所が無い**ということです(このようなループがある場合、AとBの経路が{A,B}と{A,C,B}のように複数存在することになる)。 これを踏まえると、集合Gを友人の網と考えると、ループがないため**必ず端となる人物が存在します。** 直感的に考えると、最長候補はこの端から端までの長さということになります。それを調べるため、まず適当なところから一番遠い端を探し、その端から最も遠い端を探して最長としていることになります。 詳しい証明はこの問題でやっていることでしょう。 で、この証明ですが、まずsとtの経路とvとwの経路に共通部分があることを示すために、次の図のように点を設置しました(便宜上、人物に相当するものを点と呼びます)。 !点aと点b これで、sからwまで、s→a→b→wとたどればいけます。 ただし、条件αから、st間はsからどこへ行くよりも遠いか同じなので、d(s,t)≧d(s,w)です。 これを各点までの長さに分割した式が(102)より、からの式です。 同じことをvw間とvt間でもやります。 その結果、ab間の距離が0以下という結論に至りましたが、距離は負になりませんので、ab間は0です。 これは、**aとbが同じ点である**ことを意味します。つまりこうなります。 !イメージ説明 これで2つの経路に少なくとも1点共通部分があることが確定しました。 次に、こんな風に点cを設定します。 !イメージ説明 前段と同じように、st間がsからの経路中最長であることを利用し、cからの距離比較を行います。vw間も同じです。 計算を進めると、ct間はcw間以上かつ以下、ということになったので、これを満たす関係は「ct間とcw間は等しい」しかありません。 そして、条件βからtu間はt起点経路中最長なので、tv間はそれ以下ということになりますが、先ほど示した「ct間とcw間は等しい」から、tv間はvw間と等しくなってしまい、「vw間はtu間以下」という帰結になります。しかしこれは最初の仮定の真逆です。つまり最初の仮定がおかしいということになり、tu間が全経路中最長ということになるのです。