3

我去年大学毕业，获得了心理学学位，但我也为了好玩而学习了很多数学。我最近得到了 Gary Chartrand 的《Introductory Graph Theory》一书来复习我的数学并从中获得乐趣。这是书中的一个练习，我发现它特别令人困惑：

假设您和您的丈夫与另外三对已婚夫妇参加了一个聚会。发生了几次握手。没有人与自己（或她自己）或他（或她）的配偶握手，也没有人与同一个人握手超过一次。握手结束后，假设你问每个人，包括你的丈夫，他或她握手了多少次手。每个人都给出了不同的答案。a) 你握手了多少手？b) 你丈夫握了多少手？

现在，我已经对此进行了一段时间的推理，并试图绘制可以说明解决方案的示例图，但我空手而归。我的逻辑是这样的：图中有 8 个不同的顶点，其中 7 个有不同的度数。因此，度数的值必须是 0、1、2、3、4、5、6 和 x。一对已婚夫妇的度数是 (0, 6)。由于所有图都有偶数个奇数顶点，因此 x 必须是 5、3 或 1。

你对这个问题的解决方案是什么？而且，如果你能用python解决它，你会怎么做？

(python is fun.)

干杯。

4

2 回答 2

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}

请注意，每个偶数顶点都与比自身少一个的顶点结婚。你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 回答
1

这个问题的好处是，如果您不想解决图表，您实际上并不需要解决。你实际上非常接近。你认为一对夫妇有多重性（6,0）。相对于第一对顶点，其余顶点彼此没有区别，并且您对该子图具有相同的规则。所以子图的多重性是 0,1,2,3,4,x 并且有一些具有多重性的对 (4,0)。那对夫妇在整个图中有多重性（5,1）。因此，当您遍历该过程时，您将得出结论，您的夫妻有多重性 (6,0)、(5,1)、(4,2)、(3,3)。当然，你必须有多重性 x=3，所以你的丈夫握了 3 手。

于 2010-05-25T09:24:41.507 回答