三間小屋問題

三間小屋問題（three cottages problem）也稱為水、天然氣及電力問題（water, gas and electricity）或Three utilities problem，是經典的數學謎題，描述如下：

三間小屋問題無解，無法在平面上畫出讓這些連接線不交錯的圖形。

三間小屋問題是抽象數學問題，是數學領域中拓扑图论的問題，拓扑图论是研究曲面上图的嵌入。若用正式的圖論術語，此問題在問完全二分图K3,3是否是平面图，可以讓中間的線沒有交叉. 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".。此圖形也常稱為utility graphUtility Graph  from mathworld.wolfram.com，也稱為湯瑪森圖（Thomsen graph）.。

歷史
美國數學家大衛·庫爾曼（David E. Kullman）曾經回顧過三間小屋問題的歷史。他提到大部份有提到此問題的出版資料，都認為此問題是很早就有的。在庫爾曼找到最早的文獻中，亨利·杜德耐在1917年將此問題命名為「water, gas and electricity」，不過杜德耐也提到「這個問題和山一樣古老，比電燈要早很多，甚至比煤气還要早。」杜德耐之前也曾在1913年的《》中刊過同一個問題.。

此問題另一個早期的版本是讓三個房屋和三個井都連接; .。另一個不同的版本（而且可以解的）是和三個房屋和三個水泉有關，謎題仍然是找到不互相交叉的路徑，不過只需要讓三個房屋分別各和一個水泉連接即可，就像遊戲的規則一様
.。

在數學上，此問題可以表示為完全二分图K3,3的圖形繪製。此圖曾在亨內貝格爾1908年的論文中出現過. As cited by . See in particular p. 403.。這個圖有六個頂點，分為二組，每組三個頂點，有九個邊，分別對應從一組的任意點連到另一組的任意點的九種組合。此問題就是問這個圖是否是平面图，可以在平面上繪製，而各邊不會交叉。

解法

若將湯瑪森圖畫在二維空間中，就無法避免交叉，三間小屋問題的答案是「不行」。沒有辦法畫出這九條線而彼此又沒有交叉。
換句話說，K3,3圖不是平面圖。卡齐米日·库拉托夫斯基在1930年提出K3,3圖不是平面圖的概念.，因此三間小屋問題沒有解。不過庫爾曼曾提到：「很特別的是，库拉托夫斯基沒有發表[ K3,3是]非平面的細部證明」。

有一個證明無法將K3,3嵌入平面圖中的證明，其中用到了有關若尔当曲线定理的案例分析。在此作法中會檢查圖中所有的四頂點圈中，頂點各種可能的位置，證明全部都和平面圖不相容。

另一種作法，也可以證明所有有個頂點，個邊的無橋二分平面圖，會滿足，證明方式是結合欧拉示性数 （其中是平面嵌入的面數）以及觀察其面的個數最多只有邊的一半（每一個面邊上的頂點，都會照著小屋-公共資源的順序輪流出現，因此每一個面會有四個邊，每一邊會屬於二個面）。在K3,3圖中，且，違反了上述的不等式，因此湯瑪森圖不是平面圖.。

推廣
平面圖有二個重要特徵：库拉托夫斯基定理提到平面圖就是無法分割出K3,3或是完全圖K5的圖，而瓦格納定理提到平面圖就是其次圖中沒有K3,3或K5的圖，這二個定理都用到湯瑪森圖K3,3圖的非平面特性。

K3,3是，在環面可以畫出K3,3，不會有線段彼此交叉的問題。以三間小屋問題來說，也就是若將平面（或是球面）上挖兩個洞，且在平面（或是球面）下使這二個洞連通，這就改變表面的，而三間小屋問題即可有解。另一種等效的說法是K3,3圖的圖虧數為1，因此無法嵌入亏格小於一的曲面。亏格為一的曲和環面是等效的。嵌入環面中的K3,3可以用如上所述，用挖洞連通的方式代替交叉而得，在交叉二條線中選擇一條，在交叉的二側挖洞連通，讓這條線經過挖好連通的洞，就沒有交叉問題了。另一個解法是允許線通過其他的小屋或是其他的公共資源，所增加的自由度即可使三間小屋問題有解答。

匈牙利數學家圖蘭·帕爾的問了更廣泛的問題，要找出二個集合的頂點數分別是a個及b個的完全二分图Ka,b，其交叉數的公式。像K3,3可以在有一個交叉的情形下畫出，但無法在沒有交叉的情形下畫出，因此其交叉數為1.。

有關湯瑪森圖的其他特性
湯瑪森圖K3,3是，也是（每一個頂點和三個頂點相連，其中的最小環有四個邊），最小的三次图。湯瑪森圖類似其他完全二分图，是，意思是所有的大小都相同。圖中只有二個最大獨立集，分別是完全二分图二側的端點，這二組集合的大小相同。
三次良好覆蓋圖共有七個，K3,3是其中的一個.。

K3,3也是，若在平面上排列（允許交叉）的話可以形成最簡，K3,3也是非平面Laman圖中最小的例子之一，K5的頂點數量比K3,3要少，也是最簡非平面圖，但無法形成剛體結構。

參考資料

外部連結
 3 Utilities Puzzle at Cut-the-knot
 The Utilities Puzzle explained and "solved" at Archimedes-lab.org



Category:拓扑图论
Category:智力游戏
Category:数学问题