Re: [理工] [algo]-圖形演算法
※ 引述《CMJ0121 (請多指教!!)》之銘言：
: ※ 引述《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 為....(不知道該怎樣解釋= =)
這題是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
推
12/24 22:16, , 1F
12/24 22:16, 1F
→
12/24 22:26, , 2F
12/24 22:26, 2F
推
12/24 22:42, , 3F
12/24 22:42, 3F
→
12/24 22:58, , 4F
12/24 22:58, 4F
討論串 (同標題文章)