三间小屋问题

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

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

三间小屋问题。是否可以让每一间小屋都连接到所有公共资源，而且连接线不会交错？

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

三间小屋问题是抽象数学问题，是数学领域中拓扑图论的问题，拓扑图论是研究曲面上图的嵌入。若用正式的图论术语，此问题在问完全二分图K_3,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]。

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

解法

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

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

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

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

推广

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

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

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

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

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

有关汤玛森图的其他特性

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

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