387
个编辑
更改
跳到导航
跳到搜索
第100行：
第100行： + + + + + + + + + + +
→基于邻接矩阵判断有向图有没有环
<math>b_{ih}*b_{hj}\neq 0</math>当且仅当<math>b_{ih}\neq 0</math>和<math>b_{hj}\neq 0</math>，即从节点<math>v_i</math>到<math>v_h</math>和从<math>v_h</math>到<math>v_j</math>都有路径相通，所以<math>b_{ij}^2</math>的值表示从<math>v_i</math>出发两步到达<math>v_j</math>的路径数量。同理可知，<math>b_{ij}^k</math>表示从
<math>b_{ih}*b_{hj}\neq 0</math>当且仅当<math>b_{ih}\neq 0</math>和<math>b_{hj}\neq 0</math>，即从节点<math>v_i</math>到<math>v_h</math>和从<math>v_h</math>到<math>v_j</math>都有路径相通，所以<math>b_{ij}^2</math>的值表示从<math>v_i</math>出发两步到达<math>v_j</math>的路径数量。同理可知，<math>b_{ij}^k</math>表示从
<math>v_i</math>出发经<math>k</math>步到达<math>v_j</math>的路径数量。<math>b_{ij}^k=0</math>表示不存在这样的路径。
<math>v_i</math>出发经<math>k</math>步到达<math>v_j</math>的路径数量。<math>b_{ij}^k=0</math>表示不存在这样的路径。
'''定理'''：
对于邻接矩阵 <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>
===拓扑排序和识别===
===拓扑排序和识别===