假設我們先對 Km,n 中那 m 個互斥的點編號完, 再對另外 n 個互斥的點作編號, 然後考慮此 Km,n 的 Laplacian matrix L, L 上面 m 列的左邊 m 行會形成 n*I, 右邊 n 行的每個entry都是 -1; 同理, L 的左下方nxm的submatrix都是填 -1, 右下方是 m*I
若再仔細觀察一下 L, 大致就可以猜測出以下的結果: rank(L-nI) = n+1, rank(L-mI) = m+1, 則 nullity(L-nI)=m+n-n-1=m-1, nullity(L-mI)=m+n-m-1=n-1, 所以 L 共有 m-1 個 eigenvalue n 還有 n-1 個 eigenvalue m, 另外因為 L 一定具有 eigenvalue 0, 再利用trace即可算出剩下的最後一個 eigenvalue 為 m+n
2 則留言:
我想是把Kmn拆成矩陣看
共有m個點的degree是n
n個點的degree是m
排成矩陣後 求其cofactor
可是我不太確定要怎麼拆 真不好意思QAQ
這也是matrix-tree theorem的推廣, 不過稍為複雜一點; matrix-tree除了老師上課提的算cofactor之外, 還有一個等價的敘述就是, #SP=(λ_1...λ_(n-1))/n, 其中這些相乘的λ_i 就是在去掉 0 之外後剩下的那 n-1 個 Laplacian matrix L (L=D-A) 的 eigenvalue, 用這個敘述我覺得比較好推 (若是算cofactor, 簡單的例子可參考p7-38範例5)
假設我們先對 Km,n 中那 m 個互斥的點編號完, 再對另外 n 個互斥的點作編號, 然後考慮此 Km,n 的 Laplacian matrix L, L 上面 m 列的左邊 m 行會形成 n*I, 右邊 n 行的每個entry都是 -1; 同理, L 的左下方nxm的submatrix都是填 -1, 右下方是 m*I
若再仔細觀察一下 L, 大致就可以猜測出以下的結果: rank(L-nI) = n+1, rank(L-mI) = m+1, 則 nullity(L-nI)=m+n-n-1=m-1, nullity(L-mI)=m+n-m-1=n-1, 所以 L 共有 m-1 個 eigenvalue n 還有 n-1 個 eigenvalue m, 另外因為 L 一定具有 eigenvalue 0, 再利用trace即可算出剩下的最後一個 eigenvalue 為 m+n
所以, #SP = (λ_1...λ_(n-1))/n
= [(n^(m-1))*(m^(n-1))*(m+n)]/(m+n)
= (n^(m-1))*(m^(n-1))
張貼留言