text: 三間小屋問題或Three utilities problem，是經典的數學謎題，描述如下：三間小屋問題無解，無法在平面上畫出讓這些連線線不交錯的圖形。三間小屋問題是抽象數學問題，是數學領域中的問題，拓撲圖論是研究曲面上圖的嵌入。若用正式的圖論術語，此問題在問完全二分圖"K"3,3是否是平面圖，可以讓中間的線沒有交叉。此圖形也常稱為utility graph，也稱為湯瑪森圖。歷史.美國數學家大衛·庫爾曼曾經回顧過三間小屋問題的歷史。他提到大部份有提到此問題的出版資料，都認為此問題是很早就有的。在庫爾曼找到最早的，亨利·杜德耐在1917年將此問題命名為「water, gas and electricity」，不過杜德耐也提到「這個問題和山一樣古老，比電燈要早很多，甚至比煤氣還要早。」杜德耐之前也曾在1913年的《》中刊過同一個問題。此問題另一個早期的版本是讓三個房屋和三個井都連線。另一個不同的版本是和三個房屋和三個水泉有關，謎題仍然是找到不互相交叉的路徑，不過只需要讓三個房屋分別各和一個水泉連線即可，就像遊戲的規則一様在數學上，此問題可以表示為完全二分圖"K"3,3的圖形繪製。此圖曾在亨內貝格爾1908年的論文中出現過。這個圖有六個頂點，分為二組，每組三個頂點，有九個邊，分別對應從一組的任意點連到另一組的任意點的九種組合。此問題就是問這個圖是否是平面圖，可以在平面上繪製，而各邊不會交叉。解法.若將湯瑪森圖畫在二維空間中，就無法避免交叉，三間小屋問題的答案是「不行」。沒有辦法畫出這九條線而彼此又沒有交叉。換句話說，"K"3,3圖不是平面圖。卡齊米日·庫拉托夫斯基在1930年提出"K"3,3圖不是平面圖的概念，因此三間小屋問題沒有解。不過庫爾曼曾提到：「很特別的是，庫拉托夫斯基沒有發表[ "K"3,3是]非平面的細部證明」。有一個證明無法將"K"3,3嵌入平面圖中的證明，其中用到了有關若爾當曲線定理的案例分析。在此作法中會檢查圖中所有的四頂點圈中，頂點各種可能的位置，證明全部都和平面圖不相容。另一種作法，也可以證明所有有2"V" − 4 = 8，違反了上述的不等式，因此湯瑪森圖不是平面圖。推廣.平面圖有二個重要特徵：庫拉托夫斯基定理提到平面圖就是無法分割出"K"3,3或是完全圖"K"5的圖，而瓦格納定理提到平面圖就是其次圖中沒有"K"3,3或"K"5的圖，這二個定理都用到湯瑪森圖"K"3,3圖的非平面特性。K3,3是，在環面可以畫出K3,3，不會有線段彼此交叉的問題。以三間小屋問題來說，也就是若將平面下使這二個洞連通，這就改變表面的，而三間小屋問題即可有解。另一種等效的說法是"K"3,3圖的圖虧數為1，因此無法嵌入虧格小於一的曲面。虧格為一的曲和環面是等效的。嵌入環面中的"K"3,3可以用如上所述，用挖洞連通的方式代替交叉而得，在交叉二條線中選擇一條，在交叉的二側挖洞連通，讓這條線經過挖好連通的洞，就沒有交叉問題了。另一個解法是允許線透過其他的小屋或是其他的公共資源，所增加的自由度即可使三間小屋問題有解答。匈牙利數學家圖蘭·帕爾的問了更廣泛的問題，要找出二個集合的頂點數分別是"a"個及"b"個的完全二分圖"K""a","b"，其交叉數的公式。像"K"3,3可以在有一個交叉的情形下畫出，但無法在沒有交叉的情形下畫出，因此其交叉數為1。有關湯瑪森圖的其他特性.湯瑪森圖"K"3,3是，也是，最小的三次圖。湯瑪森圖類似其他完全二分圖，是，意思是所有的大小都相同。圖中只有二個最大獨立集，分別是完全二分圖二側的端點，這二組集合的大小相同。三次良好覆蓋圖共有七個，"K"3,3是其中的一個。"K"3,3也是，若在平面上排列的話可以形成最簡，"K"3,3也是非平面Laman圖中最小的例子之一，"K"5的頂點數量比"K"3,3要少，也是最簡非平面圖，但無法形成剛體結構。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 三間小屋問題
metadata: https://zh.wikipedia.org/wiki?curid=6273214