三間小屋問題
維基百科,自由的 encyclopedia
三間小屋問題(three cottages problem)也稱為水、天然氣及電力問題(water, gas and electricity)或Three utilities problem,是經典的數學謎題,描述如下:
假設在平面上(或是在球面上)有三間小屋,要連接到天然氣公司、水廠以及電力公司。若不考慮使用立體架構,也不透過任何小屋或是其他公共設備來傳送資源,是否可以用九條線連結三間小屋及三間公共設備,而且九條線完全沒有交錯?
三間小屋問題無解,無法在平面上畫出讓這些連接線不交錯的圖形。
三間小屋問題是抽象數學問題,是數學領域中拓扑图论的問題,拓扑图论是研究曲面上图的嵌入。若用正式的圖論術語,此問題在問完全二分图K3,3是否是平面图,可以讓中間的線沒有交叉[1]。此圖形也常稱為utility graph[2],也稱為湯瑪森圖(Thomsen graph)[3]。