Loading AI tools
来自维基百科,自由的百科全书
三間小屋問題(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要少,也是最簡非平面圖,但無法形成剛體結構。
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.