公佈解答：工廠配線圖
2008/01/11 00:11
瀏覽1,533
迴響2
推薦26
引用0
引用文章趣味數學：工廠配線圖
以平面繪圖，兩種能源連線完成後，我們會發現：不管如何彎曲，第三種能源頂多只能連接２間工廠，最後一條線無法完成．
其實把圖形攤開來看，就很清楚原因為何了，
因為其中必然有一間工廠在封閉區域內，使得第三種能源僅能連接另外兩間工廠，最後一條線無法完成．
同理，若是四連四的情形，兩種能源連線完成後有兩個工廠在封閉區域內，有４條線無法連接．
若是ｎ個工廠連線至ｎ個點，會有（ｎ－２）（ｎ－２）條線無法完成連線．
這是平面的情形．
當然．實際上的情形是可以的．因為是立體的．
時和前輩已然洞悉．
迴響（2） ：
2樓. 時和2008/01/12 11:59Planarity Graph 這問題在VLSI Layout 方面極為重要
維基網站介紹Planarity Graph (可平面化圖) http://en.wikipedia.org/wiki/Planar_graph
梅斯大俠介紹的 Planarity Graph (可平面化圖) 在 Computer Science 領域是非常重要的。在VLSI(超大型積體電路)佈線方面，如果能找出平面化佈置圖，成本及良率(Yield) 將改善很多。
梅斯大俠介紹的工廠配線圖是標準的 K(3,3) 圖，是最小無法平面化的圖之一，非常有意義。
前輩....老實說，我沒想那麼多ㄟ，只是想玩數學．
梅斯普雷爾 於 2008/01/12 13:21回覆-
1樓. 時和2008/01/11 10:15Confession
時和 也沒搞懂過，只是在台北(火)車站時猜想，假如得強制要求平面化，那台北車站是要如何一個亂字可以形容？
這倒也是．
梅斯普雷爾 於 2008/01/11 23:21回覆
