三间小屋问题
维基百科,自由的 encyclopedia
三间小屋问题(three cottages problem)也称为水、天然气及电力问题(water, gas and electricity)或Three utilities problem,是经典的数学谜题,描述如下:
假设在平面上(或是在球面上)有三间小屋,要连接到天然气公司、水厂以及电力公司。若不考虑使用立体架构,也不通过任何小屋或是其他公共设备来传送资源,是否可以用九条线连结三间小屋及三间公共设备,而且九条线完全没有交错?
三间小屋问题无解,无法在平面上画出让这些连接线不交错的图形。
三间小屋问题是抽象数学问题,是数学领域中拓扑图论的问题,拓扑图论是研究曲面上图的嵌入。若用正式的图论术语,此问题在问完全二分图K3,3是否是平面图,可以让中间的线没有交叉[1]。此图形也常称为utility graph[2],也称为汤玛森图(Thomsen graph)[3]。