6-24頁的證明 倒數第二行開始 為甚麼一次微分後還要再微一次 而且為什麼n/2有最小值 (抱歉微積分不好)
Q2:
6-52的範例5可否請講解一下那個公式由來,看文字說明看不太懂
Q3:
老師上課證的尤拉迴路證明 的(<=) : 最後是沿著C依序拜訪每個Gi之EC 可得G之一EC 可是 Gi不是都是一個一個的components 阿要怎樣一一拜訪阿= =? 是邊拜訪邊把邊連起來嗎?
目前是這3個問題@@ 謝謝助教囉
訂閱：
張貼留言 (Atom)
Research Space for Linear Algebra & Discrete Mathematics
6 則留言:
關於Q2的問題：
那個公式你其實可以把它看成
degG(v)+degG_(v)=n-1
(G_代表頭上有一條線那個G，不知道該怎麼打那個字...)
也就是任一點的"degree"跟他的"補degree"的和，為所有點的數目再減1(減1是因為要減掉該點本身)
酷哦 有FREE了 = =
可是還有其他問題XD 而且公式懂了可是一大堆文字敘述都不懂
老師寫證明時 是分2個CASE 一個是包括所有點的CYCLE及得證
一個是向你說的先去掉一個CYCLE及孤立點
形成K個COMPONENT 每個COMPONENT都具EC
所以最後再把你殺掉的CYCLE連回去 再依CYCLE一一拜訪每個COMPONENT 及形成一個大EC
Q1和Q2 還是有點模糊ˊˋ
不過Q3 OK了!!
1. 這裡做微分的目的是為了要找出極大值, 簡單地說, 對一個二次函數做微分, 令 f'(x) 為零, 所解得的 x 值就會是極值所在的那個點, 做二次微分所得到的值可以用來判斷該極值是極大還是極小值 (若 f''(x)>0, 則 f(x) 具有極小值, 反之具有極大值), 這部分的觀念都是由微積分裡所談的切線、斜率所推論出來的, 若你有時間有興趣的話可以去翻翻微積分的相關書籍, 了解它背後的原理之後這些判斷的方法就都不用背了
2.
(1) 就像 Dudu 說的, 每一個點在 G 和 G 的補圖的degree和會是 n-1, 這個你應該沒問題了
(2) 因為一條邊一次就會貢獻兩個degree, 所以一個圖上的degree總和會是偶數, 那麼要使得 G 中的degree總和會是偶數, 具有奇數degree的點的個數一定要有偶數個, 那麼因為 G 中剩有 n-1 個具有奇數degree的點, 所以可知就是 n-1 一定會是偶數
然後因為偶數要加偶數才會是偶數, 同理奇數要加奇數才會是偶數, 所以由(1)的公式可知只有那一個在G中degree為偶數的點, 它在G的補圖中的degree才會是偶數
了解 3Q助教
張貼留言