您将如何解决Python中的这个图理论握手问题？

Question

去年，我获得了心理学学位的大学毕业，但我也花了很多数学来娱乐。最近，我得到了加里·夏普兰德（Gary Chartrand）的《介绍性图理论》一书，以刷新我的数学并玩得开心。这是我发现的书中特别迷人的一本练习：

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

现在，我已经对此进行了推理一段时间，并试图绘制可以说明解决方案的示例图，但是我空手而出。我的逻辑是：图中有8个不同的顶点，其中7个具有不同的度。因此，学位的值必须为0、1、2、3、4、5、6和x。一对已婚夫妇的学位＃是（0，6）。由于所有图具有均匀数量的奇数顶点，因此X必须为5、3或1。

您解决这个问题的方法是什么？而且，如果您可以在Python中解决它，您将如何做？

(python is fun.)

干杯。

Answer 1

这个问题的好处是，如果您不想，您真的不需要解决图表。您实际上很近。您认为一对夫妇具有多重性（6,0）。相对于第一对夫妇，其余的顶点彼此之间没有分歧，并且您对该子图有相同的规则。因此，子图的多重性为0,1,2,3,4，x，并且有一些夫妇具有多重性（4,0）。那对夫妇在完整图中具有多重性（5,1）。因此，当您在整个过程中迭代时，您将得出结论，您的夫妻具有多重性（6,0），（5,1），（4,2），（3,3）。当然，您必须有多重性X = 3，所以您的丈夫握住了3只手。

Answer 2

我认为此邻接列表代表了一个解决方案：

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度才能使此工作起作用。然后只是弄清楚应该如何工作。

史蒂文（Steven）说的是，您已经推论出一对夫妇（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。