2010-11-02

離散---關於用補圖來判定同構

這是離散課本上冊5-91頁的題目


老師上課時提到:G1與G2同構 <=> G1的補圖與G2的補圖同構
但在這題裡面,G2的補圖與G3的補圖看起來似乎是同構的(補圖我有畫在最右邊),但根據答案它們又不是同構...
請問我這樣根據補圖判斷的方法是否有哪裡不對呢?

1 則留言:

線代離散助教(wynne) 提到...

判斷的方法沒問題, 只是你畫的補圖有少邊
G2的補圖會長得像是一個六芒星
G3的補圖則是同構於cycle C6

在畫補圖時候可以稍微檢查一下每個點的degree,
這樣比較不會出錯