※ 引述《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