三間小屋問題（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要少，也是最簡非平面圖，但無法形成剛體結構。
參考資料
外部連結
Wikiwand in your browser!
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.
