網路城邦
上一篇 回創作列表 下一篇   字體:
公佈解答:工廠配線圖
2008/01/11 00:11:00瀏覽1374|回應2|推薦26

引用文章趣味數學:工廠配線圖

以平面繪圖,兩種能源連線完成後,我們會發現:不管如何彎曲,第三種能源頂多只能連接2間工廠,最後一條線無法完成.

其實把圖形攤開來看,就很清楚原因為何了,

因為其中必然有一間工廠在封閉區域使得第三種能源僅能連接另外兩間工廠,最後一條線無法完成.

同理,若是四連四的情形,兩種能源連線完成後有兩個工廠在封閉區域內,有4條線無法連接.

若是n個工廠連線至n個點,會有(n-2)(n-2)條線無法完成連線.

這是平面的情形.

當然.實際上的情形是可以的.因為是立體的.

時和前輩已然洞悉.

( 心情隨筆其他 )
回應 推薦文章 列印 加入我的文摘
上一篇 回創作列表 下一篇

引用
引用網址:https://classic-blog.udn.com/article/trackback.jsp?uid=Mathplayer&aid=1527108

 回應文章

時和
等級:8
留言加入好友
Planarity Graph 這問題在VLSI Layout 方面極為重要
2008/01/12 11:59

維基網站介紹Planarity Graph (可平面化圖) http://en.wikipedia.org/wiki/Planar_graph

梅斯大俠介紹的 Planarity Graph (可平面化圖) 在 Computer Science 領域是非常重要的。在VLSI(超大型積體電路)佈線方面,如果能找出平面化佈置圖,成本及良率(Yield) 將改善很多。

梅斯大俠介紹的工廠配線圖是標準的 K(3,3) 圖,是最小無法平面化的圖之一,非常有意義。


梅斯普雷爾(Mathplayer) 於 2008-01-12 13:21 回覆:
前輩....老實說,我沒想那麼多ㄟ,只是想玩數學.

時和
等級:8
留言加入好友
Confession
2008/01/11 10:15

時和 也沒搞懂過,只是在台北(火)車站時猜想,假如得強制要求平面化,那台北車站是要如何一個亂字可以形容?


梅斯普雷爾(Mathplayer) 於 2008-01-11 23:21 回覆:
這倒也是.