社区讨论

求助有向图情况

LLice
P6178【模板】Matrix-Tree 定理参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@loc0z6y8
此快照首次捕获于
2023/10/30 06:10
2 年前
此快照最后确认于
2023/11/04 11:44
2 年前
查看原帖
如题，根据题解，有向图的拉普拉斯（基尔霍夫）矩阵：
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}
注：不要无意义回复

回复

共 3 条回复，欢迎继续交流。

正在加载回复...