作者degia220 ( )
看板Grad-ProbAsk
标题Re: [理工] [algo]-图形演算法
时间Thu Dec 24 21:23:26 2009
※ 引述《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
1F：推 assassin88:请问题目的leave跟enter是什麽意思?? 12/24 22:16
2F：→ degia220:是directed graph 指的是射出/射进 12/24 22:26
3F：推 assassin88:所以degree不需要分in/out搂~如果是这样我了解了~感谢 12/24 22:42
4F：→ degia220:yes 12/24 22:58