三間小屋問題（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是]非平面的細部證明」。
另一種作法，也可以證明所有有個頂點，個邊的無橋二分平面圖，會滿足，證明方式是結合欧拉示性数 （其中是平面嵌入的面數）以及觀察其面的個數最多只有邊的一半（每一個面邊上的頂點，都會照著小屋-公共資源的順序輪流出現，因此每一個面會有四個邊，每一邊會屬於二個面）。在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也是非平面Laman圖中最小的例子之一，K5的頂點數量比K3,3要少，也是最簡非平面圖，但無法形成剛體結構。
參考資料
外部連結
- [http://www.cut-the-knot.org/do_you_know/3Utilities.shtml 3 Utilities Puzzle] at Cut-the-knot
- [http://www.archimedes-lab.org/How_to_Solve/Water_gas.html The Utilities Puzzle] explained and "solved" at Archimedes-lab.org
*
*
评论 (0)