→ assassin88:所以是....?? 12/24 09:41
※ 引述《assassin88 (...)》之銘言：
: 一、怎麼證明 kruskal's algo. 是正確的？
: 二、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 為....(不知道該怎樣解釋= =)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.152.107
※ 編輯: CMJ0121 來自: 122.116.152.107 (12/24 07:54)