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