三間小屋問題

三間小屋問題。是否可以讓每一間小屋都連接到所有公共資源，而且連接線不會交錯？

三間小屋問題（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（英语：The Strand Magazine）》中刊過同一個問題[6]。

此問題另一個早期的版本是讓三個房屋和三個井都連接[7]。另一個不同的版本（而且可以解的）是和三個房屋和三個水泉有關，謎題仍然是找到不互相交叉的路徑，不過只需要讓三個房屋分別各和一個水泉連接即可，就像Numberlink（英语：Numberlink）遊戲的規則一様 [8]。

在數學上，此問題可以表示為完全二分图K3,3的圖形繪製。此圖曾在亨內貝格爾1908年的論文中出現過[9]。這個圖有六個頂點，分為二組，每組三個頂點，有九個邊，分別對應從一組的任意點連到另一組的任意點的九種組合。此問題就是問這個圖是否是平面图，可以在平面上繪製，而各邊不會交叉[1]。

解法

utility graph，也稱為湯瑪森圖或K3,3，紅點和藍點分別是小屋和公共資源

若將湯瑪森圖畫在二維空間中，就無法避免交叉，三間小屋問題的答案是「不行」。沒有辦法畫出這九條線而彼此又沒有交叉。 換句話說，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圖

平面圖有二個重要特徵：库拉托夫斯基定理提到平面圖就是無法分割出K3,3或是完全圖K5的圖，而瓦格納定理提到平面圖就是其次圖中沒有K3,3或K5的圖，這二個定理都用到湯瑪森圖K3,3圖的非平面特性。

三間小屋問題在环面上的解

K3,3是環面圖（英语：toroidal graph），在環面可以畫出K3,3，不會有線段彼此交叉的問題。以三間小屋問題來說，也就是若將平面（或是球面）上挖兩個洞，且在平面（或是球面）下使這二個洞連通，這就改變表面的拓樸性質（英语：topological properties），而三間小屋問題即可有解。另一種等效的說法是K3,3圖的圖虧數為1，因此無法嵌入亏格小於一的曲面。亏格為一的曲和環面是等效的。嵌入環面中的K3,3可以用如上所述，用挖洞連通的方式代替交叉而得，在交叉二條線中選擇一條，在交叉的二側挖洞連通，讓這條線經過挖好連通的洞，就沒有交叉問題了。另一個解法是允許線通過其他的小屋或是其他的公共資源，所增加的自由度即可使三間小屋問題有解答。

匈牙利數學家圖蘭·帕爾的磚廠問題（英语：Turán's brick factory problem）問了更廣泛的問題，要找出二個集合的頂點數分別是a個及b個的完全二分图Ka,b，其交叉數的公式。像K3,3可以在有一個交叉的情形下畫出，但無法在沒有交叉的情形下畫出，因此其交叉數為1[13]。

有關湯瑪森圖的其他特性

湯瑪森圖K3,3是循環圖（英语：circulant graph），也是(3,4)-cage（英语：Cage (graph theory)）（每一個頂點和三個頂點相連，其中的最小環有四個邊），最小的無三角形（英语：triangle-free graph）三次图[3]。湯瑪森圖類似其他完全二分图，是良好覆蓋圖（英语：well-covered graph），意思是所有最大獨立集（英语：maximal independent set）的大小都相同。圖中只有二個最大獨立集，分別是完全二分图二側的端點，這二組集合的大小相同。 三次三連通（英语：k-vertex-connected graph）良好覆蓋圖共有七個，K3,3是其中的一個[14]。

K3,3也是Laman圖（英语：Laman graph），若在平面上排列（允許交叉）的話可以形成最簡剛體結構（英语：rigid system），K3,3也是非平面Laman圖中最小的例子之一，K5的頂點數量比K3,3要少，也是最簡非平面圖，但無法形成剛體結構。

參考資料

  1. ^ 1.0 1.1 Bóna, Miklós, A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific: 275–277, 2011, ISBN 9789814335232 . Bóna introduces the puzzle (in the form of three houses to be connected to three wells) on p. 275, and writes on p. 277 that it "is equivalent to the problem of drawing K3,3 on a plane surface without crossings".
  2. ^ Utility Graph （页面存档备份，存于互联网档案馆） from mathworld.wolfram.com
  3. ^ 3.0 3.1 Coxeter, H. S. M., Self-dual configurations and regular graphs, Bulletin of the American Mathematical Society, 1950, 56: 413–455, MR 0038078, doi:10.1090/S0002-9904-1950-09407-5 .
  4. ^ 4.0 4.1 Kullman, David, The Utilities Problem, Mathematics Magazine, 1979, 52 (5): 299–302, JSTOR 2689782. 
  5. ^ Dudeney, Henry, Problem 251 – Water, Gas, and Electricity, Amusements in mathematics, Thomas Nelson, 1917 
  6. ^ Dudeney, Henry, Perplexities, with some easy puzzles for beginners, The Strand Magazine, vol. 46, 1913: 110 [2018-08-27], （原始内容存档于2016-04-09） .
  7. ^ Puzzle, Successful Farming, vol. 13, 1914: 50 ; A well and house puzzle, The Youth's Companion, vol. 90 no. 2, 1916: 392 .
  8. ^ 32. The fountain puzzle, The Magician's Own Book, Or, The Whole Art of Conjuring, New York: Dick & Fitzgerald: 276, 1857 [2018-08-27], （原始内容存档于2019-08-13） .
  9. ^ Henneberg, L., Die graphische Statik der starren Körper, Encyklopädie der Mathematischen Wissenschaften 4.1: 345–434, 1908 . As cited by Coxeter (1950). See in particular p. 403.
  10. ^ Kuratowski, Kazimierz, Sur le problème des courbes gauches en topologie (PDF), Fund. Math., 1930, 15: 271–283 [2018-09-04], （原始内容 (PDF)存档于2018-07-23） （法语） .
  11. ^ Trudeau, Richard J., Introduction to Graph Theory Corrected, enlarged republication., New York: Dover Pub.: 68–70, 1993 [2012-08-08], ISBN 978-0-486-67870-2, （原始内容存档于2019-05-05） 
  12. ^ Kappraff, Jay, Connections: The Geometric Bridge Between Art and Science, K & E Series on Knots and Everything 25, World Scientific: 128, 2001 [2018-09-04], ISBN 9789810245863, （原始内容存档于2018-09-10） .
  13. ^ Pach, János; Sharir, Micha, 5.1 Crossings—the Brick Factory Problem, Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs 152, American Mathematical Society: 126–127, 2009 .
  14. ^ Campbell, S. R.; Ellingham, M. N.; Royle, Gordon F., A characterisation of well-covered cubic graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, 1993, 13: 193–212, MR 1220613 .

外部連結