求助有向图情况
查看原帖
求助有向图情况
61430
Lice楼主2021/8/7 12:51

如题，根据题解，有向图的拉普拉斯（基尔霍夫）矩阵：

Li,j={deg⁡invii=j−cnt(vi→vj)i≠jL_{i,j}=\begin{cases} \deg_{in} v_i & i=j\\ -\text{cnt}(v_i\to v_j) & i \ne j \end{cases}

答案为 det⁡L0\det L_0。

不过讲道理应该也有 L=MMTL=MM^T，其中 M 是关联矩阵

求助这个 MM 在有向图是应该是啥样

注：无向图边任意定向后：

Mi,j={1ej是vi的入边−1ej是vi的出边0otherwise.M_{i,j} = \begin{cases} 1 & e_j \text{是} v_i \text{的入边} \\ -1 & e_j \text{是} v_i \text{的出边} \\ 0 & \textit{otherwise.} \\ \end{cases}

注：不要无意义回复

2021/8/7 12:51