質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.50%

  • アルゴリズム

    498questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

慶應・環境情報学部の情報科目2017年度の「6次の隔たり」問題を解ける方いませんか?

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 675

codetaisei

score 13

慶應・環境情報学部の情報科目2017年度の「6次の隔たり」問題を解ける方いませんか?
来年、慶應を受ける浪人生です。
去年この問題がまったくわかりませんでした。

問題(24P~27P)→https://goo.gl/oBbrhH

自分なりにといてよくわからない所をまとめました。

イメージ説明


①すべてのx∉Gに対して友人の集合F(x)と書いていますが、図のようにxの友人のことをF(x)というという解釈で間違いないでしょうか?

②これはxの友達にyがいた場合のことを言っているのでしょうか?

③図にの解釈で間違いないでしょうか?

④なぜxとyの距離が(xとyの要素数)- 1 なのでしょうか?
これは距離にyを含んでいるから-1なのでしょうか?

⑤これはまったく言いたいことがわかりません。一応自分の解釈を図にしました。


イメージ説明


自分でわかるとこだけ解いていますが、たぶんあっていないところもあると思います。

番号のところは分からないところです。

よろしくお願いいたします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • yuba

    2017/06/16 18:44

    どの空欄がわからないのですか? 例えば最初の空欄に入るのがGであることは考えるまでもなく明らかです。

    キャンセル

  • 退会済みユーザー

    2017/06/20 16:27

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

回答 2

+1

空欄を埋めてほしいとは書いてませんでしたので、とりあえず質問についてだけ回答します。

①すべてのx∉Gに対して友人の集合F(x)と書いていますが、図のようにxの友人のことをF(x)というという解釈で間違いないでしょうか?

そうです。

②これはxの友達にyがいた場合のことを言っているのでしょうか?

"y ∈ F(x)" は、「x の友達のうちの一人を y とする」という意味です。
「y がいた場合」という言い方はちょっとおかしいです。

③図にの解釈で間違いないでしょうか?

y につながっているのは z_3 ではなく z_n ですが、それ以外は合ってます。

④なぜxとyの距離が(xとyの要素数)- 1 なのでしょうか?
これは距離にyを含んでいるから-1なのでしょうか?

そうだと考えてもらって構いません。
要素数が1のとき ⇔ x=y のとき、距離を 0 にしたいからです。

⑤これはまったく言いたいことがわかりません。一応自分の解釈を図にしました。

ご記載の図の解釈はあまり正しくありません。

  1. は、s から一番遠い友達の集合を求め、その中から t を一人任意に選ぶという意味です。
  2. は、t から一番遠い友達の集合を求め、その中から u を一人任意に選ぶという意味です。

空欄も埋めてほしいということでしたら、後で回答します。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/07/04 01:27

    回答ありがとうございます。

    ⑤に関して理解が追い付きません。
    なぜs から一番遠い友達の集合を求め、その中から t を一人任意に選び、
    そのtから一番遠い友達の集合を求め、その中から u を一人任意に選ぶ必要があるのですか?

    >>空欄も埋めてほしいということでしたら、後で回答します。
    質問後に回答を見つけたので答えは知っています。

    キャンセル

  • 2017/07/04 06:54

    その説明が書いてあるのがp26からの(イ)です。それは解きましたか?

    キャンセル

  • 2017/07/05 00:05

    (条件γ)あるv,wについてd(v,w)>d(t,u)と仮定し、矛盾を示す。
    もしd(v,w')>d(v,w)となるw'があれば、w'を改めてwとおくことができるので、
    すべてのx∈Gに対してd(v,w)≧d(v,x)としてよい。

    まず、P(s,t)とP(v,w)に共通部分があることを示す。
    sとwの経路が存在するので、それがsとtの経路と分岐する箇所をa,
    vとwの経路と分岐する箇所をbとする。
    (条件αより)

    d(s,t) = d(s,a) + d(a,t) ≧ d(s,w) = d(a,s) + d(a,b) + d(b,w)

    となる。同様に
    (条件γより)

    d(v,w) = d(v,b) + d(b,w) ≧ d(t,v) = d(b,v) + d(a,b) + d(a,t)

    となる。この2つの式の不等式の両辺を足して整理すると0≧d(a,b)となるが、距離は負にならないのでd(a,b)=0となり、P(s,t)とp(v,w)には共通部分が存在することがわかる。

    c∈P(s,t)∩P(v,w)とする。cはP(s,v)P(s,w)のどちらかに含まれるが、P(s,v)に含まれる場合はvとwを交換して考えることができるので、c∈P(s,w)としてよい。
    (条件αより)

    d(s,t) = d(s,c) + d(c,t) ≧ d(s,w) = d(s,c) + d(c,w)

    であるからd(c,t)≧d(c,w)となる。同様に
    (条件γより)

    d(v,w) = d(v,c) + d(c,w) ≧ d(t,v) = d(v,c) + d(c,t)

    であるからd(c,w)≧d(c,t)となる。この2つの式からd(c,t)=d(c,w)となる。
    (条件βより)

    d(t,u) ≧ d(t,v) = d(v,c) + d(c,t) = d(v,c) + d(c,w) = d(v,w)

    となる。これは最初の仮定に反するので、証明された。

    キャンセル

  • 2017/07/05 00:06

    回答を見てまとめましたが、さっぱり理解できません。

    キャンセル

checkベストアンサー

-1

⑤に関して

これを可能にしているのは、データの性質として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間が全経路中最長ということになるのです。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/07/05 01:32

    回答ありがとうございます。
    すごくわかりやくて助かりました。

    質問があるのですが、
    ①この問題は慶應の環境情報学部の情報科目の2017年の問題なのですが、これって普通の高校生が解ける問題なのでしょうか?
    ②このような数学とアルゴリズムを利用した穴埋め問題はどうすれば解けるようになりますか?
    一応、基本情報技術者の午後試験でアルゴリズムを勉強していますが、それだけでこのような問題を試験会場で導き出せるのでしょか。

    キャンセル

同じタグがついた質問を見る

  • アルゴリズム

    498questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。