三間小屋問題

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

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

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

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

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

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

解法

若將湯瑪森圖畫在二維空間中，就無法避免交叉，三間小屋問題的答案是「不行」。沒有辦法畫出這九條線而彼此又沒有交叉。
換句話說，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
 
 

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