![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/3_utilities_problem_blank.svg/langzh-hk-640px-3_utilities_problem_blank.svg.png&w=640&q=50)
三間小屋問題
維基百科,自由的 encyclopedia
三間小屋問題(three cottages problem)也稱為水、天然氣及電力問題(water, gas and electricity)或Three utilities problem,是經典的數學謎題,描述如下:
假設在平面上(或是在球面上)有三間小屋,要連接到天然氣公司、水廠以及電力公司。若不考慮使用立體架構,也不通過任何小屋或是其他公共設備來傳送資源,是否可以用九條線連結三間小屋及三間公共設備,而且九條線完全沒有交錯?
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/3_utilities_problem_blank.svg/320px-3_utilities_problem_blank.svg.png)
三間小屋問題無解,無法在平面上畫出讓這些連接線不交錯的圖形。
三間小屋問題是抽象數學問題,是數學領域中拓撲圖論的問題,拓撲圖論是研究曲面上圖的嵌入。若用正式的圖論術語,此問題在問完全二分圖K3,3是否是平面圖,可以讓中間的線沒有交叉[1]。此圖形也常稱為utility graph[2],也稱為湯瑪森圖(Thomsen graph)[3]。