Research Space for Linear Algebra & Discrete Mathematics
還是說因為已經證明了唯一就代表也存在了??
1. 若 T1, T2 為相異的MST, 則 w(T1)=w(T2)且存在a是T1的邊, b是T2的邊, a不屬於T2, b不屬於T1, 且a,b屬於同一個cut set不失一般性令 w(a) < w(b),將T2去掉b, 再加上a, 會得到一個 T3 亦為 ST=> w(T3) = w(T2)-w(b)+w(a) < w(T2),此與 T2 為 MST 矛盾2. G: connected iff G具有ST, 要證這個不難不過這通常當作是顯然的事實, 不太需要去證它
請問不失一般性假設w(a) < w(b)是因為題目的假設邊cost 是唯一的還是因為我們從題目給的假設推論知道w(a)=w(b)刻意去矛盾才不失一般性假設
會推得w(a) < w(b)是因為題目給我們幾個訊息就是如果樹一樣的話 邊就一樣就兩棵樹要一樣卻又是不同的樹的話 就只有其中兩邊不一樣 但卻有相同的權重題目給了我們這個資訊所以我們知道w(a) = w(b)此時刻意去證w(a) < w(b)和w(a) > w(b)而導出矛盾以上是我和同學對不失一般性有些爭議
1. 設 w(a) < w(b), 是因為題目說邊的weight會唯一, 因此不可能有w(a)=w(b)的情況發生2. 樹要不一樣, 不一定會只有恰兩個邊不一樣, 但是一定會存在一點v, 它在T1中是連a這個邊, 但在T2中是連b不連a, 這也是為什麼我取在同一個cut set的邊來證, 目的是為了要確保T3會是connected, 才能說T3會是SP (當然如果T1和T2剛好只有a和b這兩邊不一樣, 其餘邊都相等, 那T3其實就是T1)3. 我導出的矛盾, 是在於存在一顆樹T3, 它的weight小於T2, 這樣違反了T2有最小tree weight的假設, 而不是對於邊的weight有所矛盾
大至上知道了~謝謝詳細的說明
張貼留言
7 則留言:
還是說因為已經證明了唯一就代表也存在了??
1. 若 T1, T2 為相異的MST, 則 w(T1)=w(T2)
且存在a是T1的邊, b是T2的邊, a不屬於T2,
b不屬於T1, 且a,b屬於同一個cut set
不失一般性令 w(a) < w(b),
將T2去掉b, 再加上a, 會得到一個 T3 亦為 ST
=> w(T3) = w(T2)-w(b)+w(a) < w(T2),
此與 T2 為 MST 矛盾
2. G: connected iff G具有ST, 要證這個不難
不過這通常當作是顯然的事實, 不太需要去證它
請問不失一般性假設w(a) < w(b)
是因為
題目的假設邊cost 是唯一的
還是因為我們從題目給的假設推論知道w(a)=w(b)
刻意去矛盾
才不失一般性假設
會推得w(a) < w(b)是因為
題目給我們幾個訊息
就是如果樹一樣的話 邊就一樣
就兩棵樹要一樣卻又是不同的樹的話 就只有其中兩邊不一樣 但卻有相同的權重
題目給了我們這個資訊
所以我們知道w(a) = w(b)
此時刻意去證w(a) < w(b)和w(a) > w(b)而導出矛盾
以上是我和同學對不失一般性有些爭議
1. 設 w(a) < w(b), 是因為題目說邊的weight會唯一, 因此不可能有w(a)=w(b)的情況發生
2. 樹要不一樣, 不一定會只有恰兩個邊不一樣, 但是一定會存在一點v, 它在T1中是連a這個邊, 但在T2中是連b不連a, 這也是為什麼我取在同一個cut set的邊來證, 目的是為了要確保T3會是connected, 才能說T3會是SP (當然如果T1和T2剛好只有a和b這兩邊不一樣, 其餘邊都相等, 那T3其實就是T1)
3. 我導出的矛盾, 是在於存在一顆樹T3, 它的weight小於T2, 這樣違反了T2有最小tree weight的假設, 而不是對於邊的weight有所矛盾
大至上知道了~
謝謝詳細的說明
張貼留言