387
个编辑
更改
跳到导航
跳到搜索
第79行：
第79行： − ===基于邻接矩阵的有向无环图的判别方法=== − '''定理'''： − 对于邻接矩阵 <math> B\in \left\{ 0, 1 \right\}^{d*d} </math>， <math> B </math>是有向无环图当且仅当 − :<math> tr(e^B)=d</math> − − 依据泰勒展开公式 <math> e^B=I+\sum_{k=1}^{\infty}\,\frac{1}{k!}B^k</math>，有 − :<math> tr(I+\sum_{k=1}^{\infty}\,\frac{1}{k!}B^k)-d=0</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>G=（V，E）</math>，构造<math>d=\mid V \mid</math>阶方阵<math>B=(b_{ij})_{d*d}</math>，其中
对于有向图<math>G=（V，E）</math>，构造<math>d=\mid V \mid</math>阶方阵<math>B=(b_{ij})_{d*d}</math>，其中