Research Space for Linear Algebra & Discrete Mathematics
simple = a,b 之間最多一邊相連planar = 可以畫成所有的邊只有在點上會相交的圖所以 simple planar graph 就可以想成一般的地圖。像在中國大陸上走，不管從那一省出發，都可以到達任一個省。然後平面圖只考慮連通圖的原因是。如果非連通圖有 k個 component。只要這 k 個 "連通圖" 各別都滿足 planar 的定義，則整個圖也會滿足 planar 的定義。所以只planar問題基本上只會在連通圖上討論。有錯請指正囉。謝謝。
了解~如果是非連通,在個別討論分量圖是否連通,所以小黃老師在證明時,有個"否則"~~數學真是太漂亮了
就planar graph的定理中, 大部份都需要一個graph為connected, 這個題目因為是存在性問題, 因此當你把問題reduced到一個component來證明, 在一個component可以找到這樣的點, 那整個graph仍然有這樣的點存在, 既然是component那就一定是connected, 不用再check, 其實我更想談的重點是, 不失一般性有時不可以隨便亂用, 要看題目適不適合用
張貼留言
3 則留言:
simple = a,b 之間最多一邊相連
planar = 可以畫成所有的邊只有在點上會相交的圖
所以 simple planar graph 就可以想成
一般的地圖。像在中國大陸上走，不管從那一省出發，都可以到達任一個省。
然後平面圖只考慮連通圖的原因是。
如果非連通圖有 k個 component。
只要這 k 個 "連通圖" 各別都滿足 planar 的定義，則整個圖也會滿足 planar 的定義。所以只planar問題基本上只會在連通圖上討論。
有錯請指正囉。謝謝。
了解~如果是非連通,在個別討論分量圖是否連通,所以小黃老師在證明時,有個"否則"~~數學真是太漂亮了
就planar graph的定理中, 大部份都需要
一個graph為connected, 這個題目因為是
存在性問題, 因此當你把問題reduced到一
個component來證明, 在一個component
可以找到這樣的點, 那整個graph仍然有這
樣的點存在, 既然是component那就一定是
connected, 不用再check, 其實我更想談
的重點是, 不失一般性有時不可以隨便亂用
, 要看題目適不適合用
張貼留言