※ 引述《degia220 ( )》之銘言： : 標題: Re: [理工] [algo]-圖形演算法 : 時間: Thu Dec 24 21:23:26 2009 : : ※ 引述《CMJ0121 (請多指教!!)》之銘言： : : ※ 引述《assassin88 (...)》之銘言： : : : 一、怎麼證明 kruskal's algo. 是正確的？ 有 G=(V,E)，其中 |V| = n，並假設 Kruskal 找到的邊為： K1, K2.......Kn-1 令其 Tree 為 Tk K1<= K2......<=Kn-1 而最佳的 MCST 的邊： M1, M2.......Mn-1 令其 Tree 為 Tm M1<= M2......<=Mn-1 (假設 Kruskal 找到的不是 Optimal 的解，來證明矛盾，便會得到二個是相同的樹) 假定 Kruksal's 和 MCST 第一個不相等的邊在 Ki 與 Mi 也就是說 Ki 不等於 Mi (i 的值從 3~n-1，因為最小成本的兩個邊，一定在 MCST 中，也會被 Kruskal 選入) 於是有下列這兩種情形 (1) 當 Ki < Mi 時 其中 K1 ~ Ki 不會形成 Cycle (否則 Kruksal 不會選 Ki) 以及 M1 ~ Mi 不會形成 Cycle (因為他是 MCST) 考慮 Tm 如果加入 Ki 時，那麼拿掉 Mi 這個邊，便會形成 Tm' 這棵樹 會使得 Tm' 的 Cost 小於 Tm .......矛盾 (2) 當 Ki > Mi 時 Kruksal 有看到 Mi，但是放棄 Mi 了 表示 Mi 會與 K1~Ki-1 (同 M1~Mi-1) 形成 Cycle.......矛盾 也就是說找不到這樣的 Ki 不等於 Mi 的情形 --> 所以 Tk = Tm 由 (1)(2) 可知 Kruksal's Algorithm 的正確性~ ((小弟以前有po過，不過有點久遠XDDDD)) : : : 二、The incidence matrix of a directed graph G=(V,E) is a |V|*|E| matrix : : : B=(bij) such that : : : { -1, if edge j leaves vertex i : : : bij={ 1, if edge j enters vertex i : : : { 0, otherwise : : : Let matrix C=BB^T. Describe what the entries of the matrix C represent. : : : 感謝... : : 對於 C_ij而言 : : C_ii = SUM{ B_ik*B^T_ki } : : = SUM{ B_ik*B_ik } for all k in[1,n]; : : 故無論 B_ik 為何 B_ik^2 = 0 or 1 : : 故 C_ii 為 B_ii之 degree數 (leave/entere算不同degree) : : 當為 C_ij時為 SUM{ B_ik*B_jk } : : B_ik*B_jk = 1 ==> B_ij有共同 leave/entere 目標 : : B_ik*B_jk = -1 ==> B_ij為一個path : : 故 C_ij 為....(不知道該怎樣解釋= =) : : 這題是93年台大資工軟設 : : { 0 ,if i≠j且vertex i 與 vertex j 之間沒有edge : Cij={-1 ,if i≠j且vertex i 與 vertex j 之間有edge : { k ,if i=j 且vertex i 的 degree 為 k : : : 沒法接受的話 畫圖計算就容易看出來了 : : : -- :

※ 發信站: 批踢踢實業坊(ptt.cc) : ◆ From: 219.85.189.253 : 推 assassin88:請問題目的leave跟enter是什麼意思?? 12/24 22:16 : → degia220:是directed graph 指的是射出/射進 12/24 22:26 : 推 assassin88:所以degree不需要分in/out摟~如果是這樣我了解了~感謝 12/24 22:42 : → degia220:yes 12/24 22:58 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.136.11.74