如何用Python解决图论握手问题？

Question

我去年大学毕业，学的是心理学，但我也为了好玩学了很多数学。最近我买了本书《初步图论》，作者是加里·查特兰，想复习一下数学，顺便玩得开心。书里有个练习让我特别困惑：

假设你和你的丈夫参加了一个聚会，聚会上还有另外三对已婚夫妇。大家握了好几次手。没有人和自己握手，也没有和自己的配偶握手，而且没有人和同一个人握手超过一次。握手结束后，假设你问每个人，包括你的丈夫，他们握了多少次手。每个人的回答都不一样。a) 你握了多少次手？b) 你的丈夫握了多少次手？

我思考了很久这个问题，还试着画一些示例图来帮助理解，但一直没有头绪。我的逻辑是这样的：图中有8个不同的点，其中7个点的度数（也就是握手的次数）是不同的。因此，这些度数的值必须是0, 1, 2, 3, 4, 5, 6，还有一个未知的x。对于一对已婚夫妇来说，他们的度数是(0, 6)。因为所有图都有偶数个奇数度的点，所以x只能是5, 3或1。

你对这个问题有什么解决方案？如果用python来解决，你会怎么做呢？

(python is fun.)

谢谢。

Answer 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)的图，规则依然适用。从这里，你可以用同样的思路去判断是否存在(1,5)这一对夫妻。实际上会是(0,4)，但最后你需要加1，因为这是不算第一对夫妻的子图。

就这样不断重复，直到你只剩下一个人和x这个项，你应该能得到x = 3。

Answer 2

这个问题的有趣之处在于，如果你不想的话，其实并不需要完全解决这个图。你已经很接近了。你发现有一对的数量是(6,0)。剩下的点在第一对的情况下是没有区别的，而且你对这个子图有相同的规则。所以这个子图的数量是0,1,2,3,4,x，并且有一对的数量是(4,0)。在整个图中，这一对的数量是(5,1)。所以当你逐步进行这个过程时，你会得出你的对的数量是(6,0)，(5,1)，(4,2)，(3,3)。当然，你必须得出数量x=3，所以你的丈夫握了3次手。