387
个编辑
更改
跳到导航
跳到搜索
第72行：
第72行： − +
→基于邻接矩阵的有向无环图的判别方法
对于邻接矩阵 <math> B\in \left\{ 0, 1 \right\}^{d*d} </math>，当且仅当 <math> tr(e^B)=d</math> 时<math> B </math>是有向无环图。
对于邻接矩阵 <math> B\in \left\{ 0, 1 \right\}^{d*d} </math>，当且仅当 <math> tr(e^B)=d</math> 时<math> B </math>是有向无环图。
其中，<math> B_{ij}^k</math>是从<math> i </math>到<math> j </math>的长度为<math> k </math>的有向路径的数量,例如<math> B_{ij}^2=sum_kB_{ik}B_{kj}</math>
其中，<math> B_{ij}^k</math>是从<math> i </math>到<math> j </math>的长度为<math> k </math>的有向路径的数量,例如<math> B_{ij}^2=\sum_kB_{ik}B_{kj}</math>
=== 拓扑排序和识别 ===
=== 拓扑排序和识别 ===