Loading AI tools
来自维基百科，自由的百科全书
三间小屋问题（three cottages problem）也称为水、天然气及电力问题（water, gas and electricity）或Three utilities problem，是经典的数学谜题，描述如下：
假设在平面上（或是在球面上）有三间小屋，要连接到天然气公司、水厂以及电力公司。若不考虑使用立体架构，也不通过任何小屋或是其他公共设备来传送资源，是否可以用九条线连结三间小屋及三间公共设备，而且九条线完全没有交错？
三间小屋问题无解，无法在平面上画出让这些连接线不交错的图形。
三间小屋问题是抽象数学问题，是数学领域中拓扑图论的问题，拓扑图论是研究曲面上图的嵌入。若用正式的图论术语，此问题在问完全二分图K3,3是否是平面图，可以让中间的线没有交叉[1]。此图形也常称为utility graph[2]，也称为汤玛森图（Thomsen graph）[3]。
美国数学家大卫·库尔曼（David E. Kullman）曾经回顾过三间小屋问题的历史。他提到大部分有提到此问题的出版资料，都认为此问题是很早就有的[4]。在库尔曼找到最早的文献中，亨利·杜德耐在1917年将此问题命名为“water, gas and electricity”，不过杜德耐也提到“这个问题和山一样古老，比电灯要早很多，甚至比煤气还要早。[5]”杜德耐之前也曾在1913年的《The Strand Magazine》中刊过同一个问题[6]。
此问题另一个早期的版本是让三个房屋和三个井都连接[7]。另一个不同的版本（而且可以解的）是和三个房屋和三个水泉有关，谜题仍然是找到不互相交叉的路径，不过只需要让三个房屋分别各和一个水泉连接即可，就像Numberlink游戏的规则一様 [8]。
在数学上，此问题可以表示为完全二分图K3,3的图形绘制。此图曾在亨内贝格尔1908年的论文中出现过[9]。这个图有六个顶点，分为二组，每组三个顶点，有九个边，分别对应从一组的任意点连到另一组的任意点的九种组合。此问题就是问这个图是否是平面图，可以在平面上绘制，而各边不会交叉[1]。
若将汤玛森图画在二维空间中，就无法避免交叉，三间小屋问题的答案是“不行”。没有办法画出这九条线而彼此又没有交叉。 换句话说，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或是完全图K5的图，而瓦格纳定理提到平面图就是其次图中没有K3,3或K5的图，这二个定理都用到汤玛森图K3,3图的非平面特性。
K3,3是环面图，在环面可以画出K3,3，不会有线段彼此交叉的问题。以三间小屋问题来说，也就是若将平面（或是球面）上挖两个洞，且在平面（或是球面）下使这二个洞连通，这就改变表面的拓朴性质，而三间小屋问题即可有解。另一种等效的说法是K3,3图的图亏数为1，因此无法嵌入亏格小于一的曲面。亏格为一的曲和环面是等效的。嵌入环面中的K3,3可以用如上所述，用挖洞连通的方式代替交叉而得，在交叉二条线中选择一条，在交叉的二侧挖洞连通，让这条线经过挖好连通的洞，就没有交叉问题了。另一个解法是允许线通过其他的小屋或是其他的公共资源，所增加的自由度即可使三间小屋问题有解答。
匈牙利数学家图兰·帕尔的砖厂问题问了更广泛的问题，要找出二个集合的顶点数分别是a个及b个的完全二分图Ka,b，其交叉数的公式。像K3,3可以在有一个交叉的情形下画出，但无法在没有交叉的情形下画出，因此其交叉数为1[13]。
汤玛森图K3,3是循环图，也是(3,4)-cage（每一个顶点和三个顶点相连，其中的最小环有四个边），最小的无三角形三次图[3]。汤玛森图类似其他完全二分图，是良好覆盖图，意思是所有最大独立集的大小都相同。图中只有二个最大独立集，分别是完全二分图二侧的端点，这二组集合的大小相同。 三次三连通良好覆盖图共有七个，K3,3是其中的一个[14]。
K3,3也是Laman图，若在平面上排列（允许交叉）的话可以形成最简刚体结构，K3,3也是非平面Laman图中最小的例子之一，K5的顶点数量比K3,3要少，也是最简非平面图，但无法形成刚体结构。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
