3

私は昨年、心理学の学位を取得して大学を卒業しましたが、楽しみのために数学もたくさん取りました。私は最近、Gary Chartrand の「Introductory Graph Theory」という本を手に入れて、数学をブラッシュアップして楽しみました。これは、私が特に困惑している本からの演習です。

あなたとあなたの夫が、他の 3 組の夫婦と一緒にパーティーに出席したとします。握手会が何度か行われました。自分自身または配偶者と握手をした人は誰もおらず、同じ人と 2 回以上握手をした人もいません。すべての握手が終わった後、夫を含む各人に、握手した回数を尋ねたとします。一人一人が異なる答えを出しました。a) 何回握手しましたか? b) あなたの夫は何回握手しましたか?

さて、私はしばらくこれについて推論し、解決策を説明できるサンプル グラフを描こうとしましたが、手ぶらでやってきました。私の論理は次のとおりです。グラフには 8 つの異なる頂点があり、そのうちの 7 つは異なる次数を持っています。したがって、度の値は 0、1、2、3、4、5、6、および x でなければなりません。1 組の夫婦の度数は (0, 6) です。すべてのグラフには偶数個の奇数の頂点があるため、x は 5、3、または 1 のいずれかでなければなりません。

この問題に対するあなたの解決策は何ですか? そして、それを Python で解けるとしたら、どのようにしますか?

(python is fun.)

乾杯。

4

2 に答える 2

1

この問題の良いところは、必要がなければグラフを解く必要がないことです。あなたは実際に非常に近いです。1つのカップルに多重度（6,0）があることがわかりました。残りの頂点は、最初のカップルに関して互いに区別されておらず、そのサブグラフに対して同じルールがあります。したがって、サブグラフの多重度は0,1,2,3,4、xであり、多重度（4,0）を持つカップルがいくつかあります。そのカップルは、完全グラフで多重度（5,1）を持っています。したがって、プロセスを繰り返すと、カップルには多重度（6,0）、（5,1）、（4,2）、（3,3）があると結論付けられます。そしてもちろん、あなたの夫が3つの手を振ったように、あなたは多重度x=3を持っている必要があります。

于 2010-05-25T09:24:41.507 に答える
1

この隣接リストは解決策を表していると思います：

1 ->  {}
2 ->  {3, 4, 5, 6, 7, 8}
3 ->  {2, 5, 6, 7, 8}
4 ->  {2}
5 ->  {2, 3, 7, 8}
6 ->  {2, 3}
7 ->  {2, 3, 5}
8 ->  {2, 3, 5}

偶数の各頂点は、それ自体より 1 つ小さい頂点と結婚していることに注意してください。あなたは8歳で​​す。

私はその解決策を直感的に理解しました。数分間考えた後、これが機能するには、各カップルの合計度が 6 である必要があることに気付きました。次に、それがどのように機能するかを考え出しました。

スティーブンが言っているのは、次数 (0,6) のカップルとそれ以外のすべてのカップル (1, 2, 3, 4, 5, x) が必要であると推測したということです。次に、最初のカップルを削除して作成されたサブグラフを考えてみましょう。「夫」は誰とも握手をしなかったので、影響はありません。「妻」はみんなの心を揺さぶったので、他のすべての度数から 1 を引く必要があります。したがって、同じルールが適用される (0, 1, 2, 3, 4, x-1) のグラフがあります。ここから、(0,6) 対の存在を決定するために使用したのと同じ思考プロセスを使用して、(1,5) 対の存在を把握できます。実際には (0,4) になりますが、これは最初のカップルをカウントしないサブグラフであるため、最後に 1 を追加する必要があります。

誰かと x 項に到達するまで繰り返し続けると、x = 3 になるはずです。

于 2010-05-25T07:45:15.897 に答える