The assumption is that G is connected and planar. If G is not connected, then you can apply this to each component, say e_i <= 3n_i -6. Summing up obtains |E(G)| <= |V(G)| - 6k, where k is the number of components. But since n-6k is bounded above by n-6, you still have e <= 3n-6.
5 則留言:
The assumption is that G is connected and planar. If G is not connected, then you can apply this to each component, say
e_i <= 3n_i -6. Summing up obtains |E(G)| <= |V(G)| - 6k, where k is the number of components. But since n-6k is bounded above by n-6, you still have e <= 3n-6.
應是|E(G)| <= 3|V(G)| - 6k
由此bounded在|V(G)|>=2，題目點數11以上，但是對一個component來說，假設v=1,e=0，e<=3v-6不合，課本推廣7的先決條件是給e>=2時e<=3v-6，所以不能直接用在任意component。
阿凱的意思是說, 當不是connected時邊數只會更少, 因為是upper bound, 所以不等式仍然成立, 這一題是用矛盾證法, 假設G為connected planar, 則e <= 3v - 6, 再一次, 當G不為connected時, 它的邊數比connected時少, 所以e <= 3v - 6仍成立, 同理G^c也是如此, 我想這樣子講應該有比較清楚一些了
再把每個component的e_i <= 3n_i -6加成
|E(G)| <= |V(G)| - 6k前e_i <= 3n_i -6未必成立，反例就是n_i=1,e_i=0
並不需要討論每個component, 只需想成當connected時e <= 3v - 6, 若graph並不為conneced, 它的邊數並不會比connected多即可, 例可可以在二個componet之間多加一個邊就會變成connected, 但不會影響到planar graph的特性
張貼留言