例如第一題是我我會這樣寫 G=(V,E) G is tree by induction on edge e = 1, trivial 假設e <= k成立 考慮e = k+1 自G中去除一邊e=(v1,v2)'，得二subtree G1 G2 by indution hypothesis G1G2皆為2colorable
1. tree <=> no cycle <=> no even cycle & no odd cycle. 2. bipartite graph <=> no odd cycle from 1 & 2 => (the set of bipartite graph) contains (the set of tree). thus tree is bipartite.
11 則留言:
我不知道訣竅在哪,不過個人感覺,解圖論的技巧不是上過離散後就可以馬上上手的,很多觀念得靠演練以及看得更深入才能慢慢累積實力,所以老師常常上課會說"技巧"就是這個原因吧,所以有些想不通的,我就會認命的背了....XD,畢竟補習班是速成教育不可能短時間讓你真正懂數學,只能帶我們入門而已
感謝B大的意見，那請問以我這兩題，有何想法嗎？片段也可以，我可以做個思考方向的參考？
MST這題我的想法是先會找一條MST假設是T然後因為已知各邊權重相異所以如果自T中去掉一邊加入G中的其他邊必定不是MST...然後由此可知T唯一
Tree這題應該就把G中的點分兩堆就好了,假設n1
與n2有邊相連那我就把n1,n2 分在不同邊..然後
G中剩下其他點也這樣分,最後就變兩堆然後再證明
任兩堆的點必不相連,但是已知就是 tree 了 所以
應該舉個例子就好了,如 n1 n2 有邊相連n2 根 n3 又有邊相連那 n1 n2 一定在同一堆且無邊相連否則就形成 cycle 啦就不是 tree 了
其實這兩題的想法其實就是定義,以前老師講定義最重要一開始還不能體會,現在慢慢了解了..XD
圖論這章的分數真的不太好掌握,
主要也是因為我們對於這個領域太不熟悉
要證tree是bipartite, 我們可以先來想想看
要怎麼traverse tree中的點來將點集分成
兩個independent set, 再來寫出嚴謹的證明
至於要證當weight全相異時MST的唯一性,
想法上你可以先想想看在找MST的演算法中
我們會先挑選哪些邊,
再來說明那些邊是不是一定得存在於MST
還是要再提醒一下, 寫證明不能只舉例就好,
不管在圖論還是在其他範圍都一樣,
因為再怎麼舉例, 那個例子可能都只是特例而已
技巧和經驗與熟度真的有很大的關係, 這也是為什麼老師會一直強調大家一定要花很多時間自己動手做題目; 對初學者來說, 沒有一題沒有技巧, 但當我們題目看多了, 手邊的工具多了, 就會感覺那些技巧越來越不是技巧, 也更能體會很多想法不是憑空而來的, 同學們上過老師的課, 應該也都知道老師在講解每個題目時, 會盡量解釋想法的來源, 當然有些真的感覺有如神來之筆, 但也不妨說那些結論搞不好也都是前人在研究推導過程中意外發現的, 所以在缺乏已知的狀況下要解出那些問題, 本來也就不是容易的事
如果同學您在台北, 或許可以考慮最近來聽看看助教解題班, 是這個暑假臨時開的, 我每個禮拜會挑一些題目出來講解, 主要是幫大家複習老師每堂課的上課內容, 講解一些近幾年常看到同學們問的問題; 在講解時, 我會盡量把想法告訴大家, 順便提醒一些老師時常叮嚀的觀念, 線代和離散這週的進度剛好都是複習完第三章, 詳細上課時間地點您可以打電話詢問一下, 不方便來上課也沒關係, 您上來這裡問我還是都會看的
根據以往經驗，遇到tree就是對邊做induction，然後討論K的邊的時候要用扣邊的方式(然後加回來)
(這題如果你能立刻聯想到bipartite就是2colorable會比較容易)
例如第一題是我我會這樣寫
G=(V,E) G is tree
by induction on edge
e = 1, trivial
假設e <= k成立
考慮e = k+1
自G中去除一邊e=(v1,v2)'，得二subtree G1 G2
by indution hypothesis
G1G2皆為2colorable
假設v1和v2顏色不同
G = G1+G2+e, G is 2 colorable 得證
假設v1和v2顏色相同
則將G1中顏色對調, 然後上上行照抄
// ============================
不過其實我有一個比較偷懶的想法不知道可不可以
不失一般性假設存在一個3colorable的tree T=>T中有cycle -><-
tree為2colorable=>tree為bipatite
// ============================
反正圖論的證明就以下口訣
1.要畫圖輔助說明
2.tree <=> induction on edge <=>送分
3.(重要)三十秒內沒靈感就跳過去做下一題遞迴，不要硬幹
1. tree <=> no cycle <=> no even cycle & no odd cycle.
2. bipartite graph <=> no odd cycle
from 1 & 2 => (the set of bipartite graph) contains (the set of tree).
thus tree is bipartite.
張貼留言