我想請問個離散小小的證明問題
關於證明g具有Euler circuit <==>G:connected且任給v屬於V deg(v)=even;
pf
(<=) 其中有一步 因為deg(v)=even 所以G有circuit
但我看前面的證明寫的是deg(v)=even 所以G還有cycle
可是兩個定義不是不一樣嗎 怎麼會有circuit就代表有cycle?
還有另一個是證明3/2r<=e<=3v-6
證明過程其中一段寫:每個邊至多與兩個邊相連 所以N<=2e 這個不知道原因
最後 我想問 k4是個連通平面圖 可是 因為k4每個cycle都含有4個邊 帶入e<=k/k-2(v-2)
這個公式 答案就不對了是哪邊有問題嗎 可以麻煩高手解惑嗎 @@ 謝謝
2 則留言:
circuit 是 closed trail, 就是可重複點 (邊不可), 而 cycle 是不可重複.
我不知道你 r 和 N 的定義, 所以無法回答.
我猜你這邊是在說平面圖, 這個定理的證明中看的是 face 的邊, 不是 cycle 的面, 而且 K_4 畫成平面圖應該每個面都是三條邊.
這題裡老師有提到cycle的地方是:若G中每個點的度數至少2，則G含一個cycle(p6-35的定理2)，這是為了要將G砍成components，到此cycle的任務就結束了。
照老師的說法r應是指region個數，N指所有region邊數之總和，n<=2e，指每個邊至多2個region相鄰，這應該多畫幾個圖出來，就可以領會到了。
k4畫成連通平面圖時，每個cycle至少由3個邊所圍成，k應該帶3才對。例如k2,2是由一個cycle圍成，一個cycle 4個邊，k代4也符合定理。
解釋有問題或有矛盾請指教
張貼留言