三间小屋问题

三间小屋问题（three cottages problem）也称为水、天然气及电力问题（water, gas and electricity）或Three utilities problem，是经典的数学谜题，描述如下：

三间小屋问题。是否可以让每一间小屋都连接到所有公共资源，而且连接线不会交错？
假设在平面上（或是在球面上）有三间小屋，要连接到天然气公司、水厂以及电力公司。若不考虑使用立体架构，也不通过任何小屋或是其他公共设备来传送资源，是否可以用九条线连结三间小屋及三间公共设备，而且九条线完全没有交错？

三间小屋问题无解，无法在平面上画出让这些连接线不交错的图形。

三间小屋问题是抽象数学问题，是数学领域中拓扑图论（英语：Topological graph theory）的问题，拓扑图论是研究曲面上图的嵌入。若用正式的图论术语，此问题在问完全二分图K3,3是否是平面图，可以让中间的线没有交叉[1]。此图形也常称为utility graph[2]，也称为汤玛森图（Thomsen graph）[3]。

历史

美国数学家大卫·库尔曼（David E. Kullman）曾经回顾过三间小屋问题的历史。他提到大部分有提到此问题的出版资料，都认为此问题是很早就有的[4]。在库尔曼找到最早的文献中，亨利·杜德耐在1917年将此问题命名为“water, gas and electricity”，不过杜德耐也提到“这个问题和山一样古老，比电灯要早很多，甚至比煤气还要早。[5]”杜德耐之前也曾在1913年的《The Strand Magazine（英语：The Strand Magazine）》中刊过同一个问题[6]。

此问题另一个早期的版本是让三个房屋和三个井都连接[7]。另一个不同的版本（而且可以解的）是和三个房屋和三个水泉有关，谜题仍然是找到不互相交叉的路径，不过只需要让三个房屋分别各和一个水泉连接即可，就像Numberlink（英语：Numberlink）游戏的规则一様 [8]。

在数学上，此问题可以表示为完全二分图K3,3的图形绘制。此图曾在亨内贝格尔1908年的论文中出现过[9]。这个图有六个顶点，分为二组，每组三个顶点，有九个边，分别对应从一组的任意点连到另一组的任意点的九种组合。此问题就是问这个图是否是平面图，可以在平面上绘制，而各边不会交叉[1]。

解法

 
 
utility graph，也称为汤玛森图或K3,3，红点和蓝点分别是小屋和公共资源

若将汤玛森图画在二维空间中，就无法避免交叉，三间小屋问题的答案是“不行”。没有办法画出这九条线而彼此又没有交叉。 换句话说，K3,3图不是平面图。卡齐米日·库拉托夫斯基在1930年提出K3,3图不是平面图的概念[10]，因此三间小屋问题没有解。不过库尔曼曾提到：“很特别的是，库拉托夫斯基没有发表[ K3,3是]非平面的细部证明”[4]。

有一个证明无法将K3,3嵌入平面图中的证明，其中用到了有关若尔当曲线定理的案例分析。在此作法中会检查图中所有的四顶点圈中，顶点各种可能的位置，证明全部都和平面图不相容[11]。

另一种作法，也可以证明所有有V个顶点，E个边的无桥二分平面图，会满足E ≤ 2V − 4，证明方式是结合欧拉示性数 V − E + F = 2（其中F是平面嵌入的面数）以及观察其面的个数最多只有边的一半（每一个面边上的顶点，都会照着小屋-公共资源的顺序轮流出现，因此每一个面会有四个边，每一边会属于二个面）。在K3,3图中，E = 9且2V − 4 = 8，违反了上述的不等式，因此汤玛森图不是平面图[12]。

推广

 
只有二个边交叉的K3,3图

平面图有二个重要特征：库拉托夫斯基定理提到平面图就是无法分割出K3,3或是完全图K5的图，而瓦格纳定理提到平面图就是其次图中没有K3,3或K5的图，这二个定理都用到汤玛森图K3,3图的非平面特性。

 
三间小屋问题在环面上的解

K3,3是环面图（英语：toroidal graph），在环面可以画出K3,3，不会有线段彼此交叉的问题。以三间小屋问题来说，也就是若将平面（或是球面）上挖两个洞，且在平面（或是球面）下使这二个洞连通，这就改变表面的拓朴性质（英语：topological properties），而三间小屋问题即可有解。另一种等效的说法是K3,3图的图亏数为1，因此无法嵌入亏格小于一的曲面。亏格为一的曲和环面是等效的。嵌入环面中的K3,3可以用如上所述，用挖洞连通的方式代替交叉而得，在交叉二条线中选择一条，在交叉的二侧挖洞连通，让这条线经过挖好连通的洞，就没有交叉问题了。另一个解法是允许线通过其他的小屋或是其他的公共资源，所增加的自由度即可使三间小屋问题有解答。

匈牙利数学家图兰·帕尔的砖厂问题（英语：Turán's brick factory problem）问了更广泛的问题，要找出二个集合的顶点数分别是a个及b个的完全二分图Ka,b，其交叉数的公式。像K3,3可以在有一个交叉的情形下画出，但无法在没有交叉的情形下画出，因此其交叉数为1[13]。

有关汤玛森图的其他特性

汤玛森图K3,3是循环图（英语：circulant graph），也是(3,4)-cage（英语：Cage (graph theory)）（每一个顶点和三个顶点相连，其中的最小环有四个边），最小的无三角形（英语：triangle-free graph）三次图[3]。汤玛森图类似其他完全二分图，是良好覆盖图（英语：well-covered graph），意思是所有最大独立集（英语：maximal independent set）的大小都相同。图中只有二个最大独立集，分别是完全二分图二侧的端点，这二组集合的大小相同。 三次三连通（英语：k-vertex-connected graph）良好覆盖图共有七个，K3,3是其中的一个[14]。

K3,3也是Laman图（英语：Laman graph），若在平面上排列（允许交叉）的话可以形成最简刚体结构（英语：rigid system），K3,3也是非平面Laman图中最小的例子之一，K5的顶点数量比K3,3要少，也是最简非平面图，但无法形成刚体结构。

参考资料

  1. ^ 1.0 1.1 Bóna, Miklós, A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific: 275–277, 2011, ISBN 9789814335232 . Bóna introduces the puzzle (in the form of three houses to be connected to three wells) on p. 275, and writes on p. 277 that it "is equivalent to the problem of drawing K3,3 on a plane surface without crossings".
  2. ^ Utility Graph （页面存档备份，存于互联网档案馆） from mathworld.wolfram.com
  3. ^ 3.0 3.1 Coxeter, H. S. M., Self-dual configurations and regular graphs, Bulletin of the American Mathematical Society, 1950, 56: 413–455, MR 0038078, doi:10.1090/S0002-9904-1950-09407-5 .
  4. ^ 4.0 4.1 Kullman, David, The Utilities Problem, Mathematics Magazine, 1979, 52 (5): 299–302, JSTOR 2689782. 
  5. ^ Dudeney, Henry, Problem 251 – Water, Gas, and Electricity, Amusements in mathematics, Thomas Nelson, 1917 
  6. ^ Dudeney, Henry, Perplexities, with some easy puzzles for beginners, The Strand Magazine, vol. 46, 1913: 110 [2018-08-27], （原始内容存档于2016-04-09） .
  7. ^ Puzzle, Successful Farming, vol. 13, 1914: 50 ; A well and house puzzle, The Youth's Companion, vol. 90 no. 2, 1916: 392 .
  8. ^ 32. The fountain puzzle, The Magician's Own Book, Or, The Whole Art of Conjuring, New York: Dick & Fitzgerald: 276, 1857 [2018-08-27], （原始内容存档于2019-08-13） .
  9. ^ Henneberg, L., Die graphische Statik der starren Körper, Encyklopädie der Mathematischen Wissenschaften 4.1: 345–434, 1908 . As cited by Coxeter (1950). See in particular p. 403.
  10. ^ Kuratowski, Kazimierz, Sur le problème des courbes gauches en topologie (PDF), Fund. Math., 1930, 15: 271–283 [2018-09-04], （原始内容 (PDF)存档于2018-07-23） （法语） .
  11. ^ Trudeau, Richard J., Introduction to Graph Theory Corrected, enlarged republication., New York: Dover Pub.: 68–70, 1993 [2012-08-08], ISBN 978-0-486-67870-2, （原始内容存档于2019-05-05） 
  12. ^ Kappraff, Jay, Connections: The Geometric Bridge Between Art and Science, K & E Series on Knots and Everything 25, World Scientific: 128, 2001 [2018-09-04], ISBN 9789810245863, （原始内容存档于2018-09-10） .
  13. ^ Pach, János; Sharir, Micha, 5.1 Crossings—the Brick Factory Problem, Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs 152, American Mathematical Society: 126–127, 2009 .
  14. ^ Campbell, S. R.; Ellingham, M. N.; Royle, Gordon F., A characterisation of well-covered cubic graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, 1993, 13: 193–212, MR 1220613 .

外部链接