有向无环图 - 版本历史

13944556914：13944556914移动页面有向无环图 Directed acyclic graph至有向无环图覆盖重定向

2024-06-03T07:33:40Z

13944556914移动页面有向无环图 Directed acyclic graph至有向无环图覆盖重定向

2024年6月3日 (一) 07:32 13944556914

2024-06-03T07:32:15Z

2022年3月15日 (二) 08:05 薄荷

2022-03-15T08:05:38Z

显示更改

孙钦贵：/* 基于邻接矩阵判断有向图有没有环 */

2021-06-21T14:17:20Z

基于邻接矩阵判断有向图有没有环

孙钦贵：/* 基于邻接矩阵的有向无环图的判别方法 */

2021-06-21T14:14:08Z

基于邻接矩阵的有向无环图的判别方法

孙钦贵：/* 基于邻接矩阵判断有向图有没有环 */

2021-06-21T13:14:20Z

基于邻接矩阵判断有向图有没有环

孙钦贵：/* 基于邻接矩阵判断有向图有没有环 */

2021-06-21T12:31:17Z

基于邻接矩阵判断有向图有没有环

孙钦贵：/* 基于邻接矩阵判断有向图有没有环 */

2021-06-21T12:27:58Z

基于邻接矩阵判断有向图有没有环

孙钦贵：/* 基于邻接矩阵判断有向图有没有环 */

2021-06-21T12:27:11Z

基于邻接矩阵判断有向图有没有环

孙钦贵：/* 基于邻接矩阵判断有向图有没有环 */

2021-06-21T12:25:47Z

基于邻接矩阵判断有向图有没有环

@@ 第4行： / 第4行： @@
 }}
 [[文件:Example_of_a_directed_acyclic_graph.png|thumb|right|250px|图1：一个有向无环图的例子]]
-在图论和计算机科学中，'''有向无环图 Directed acyclic graph'''（DAG 或 dag）是一个没有定向循环的有向图。也就是说，它由 '''顶点 Vertex''' 和 '''边 Edge''' （也称为弧）组成，每条边都从一个顶点指向另一个顶点，沿着这些顶点的方向 不会形成一个闭合的 '''环 Loop''' 。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列构成 '''拓扑排序 Topologically ordered''' 。有向无环图有许多科学的和计算的应用，从生物学（进化论，家谱，流行病学）到社会学（引文网络）到计算（调度）。
+在图论和计算机科学中，'''有向无环图 (Directed acyclic graph）'''（DAG 或 dag）是一个没有定向循环的有向图。也就是说，它由 '''顶点 Vertex''' 和 '''边 Edge''' （也称为弧）组成，每条边都从一个顶点指向另一个顶点，沿着这些顶点的方向 不会形成一个闭合的 '''环 Loop''' 。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列构成 '''拓扑排序 Topologically ordered''' 。有向无环图有许多科学的和计算的应用，从生物学（进化论，家谱，流行病学）到社会学（引文网络）到计算（调度）。

@@ 第95行： / 第95行： @@
 依据泰勒展开公式 <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>
 ===拓扑排序和识别===

@@ 第79行： / 第79行： @@
 ==相关计算问题==
 ===基于邻接矩阵判断有向图有没有环===
 对于有向图<math>G=（V，E）</math>，构造<math>d=\mid V \mid</math>阶方阵<math>B=(b_{ij})_{d*d}</math>，其中

@@ 第107行： / 第107行： @@
 依据泰勒展开公式 <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>
 ===拓扑排序和识别===

@@ 第107行： / 第107行： @@
 依据泰勒展开公式 <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>
 ===拓扑排序和识别===

←上一版本	2024年6月3日 (一) 07:33的版本
（没有差异）

@@ 第92行： / 第92行： @@
 ===基于邻接矩阵判断有向图有没有环===
-对于有向图<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>，其中
 :<math>b_{ij}=\mid e_k \mid,e_k=(v_i,v_j)\in E</math>
 称矩阵<math>B</math>为有向图<math>G</math>的节点邻接矩阵。
@@ 第102行： / 第102行： @@
 '''定理'''：
-对于邻接矩阵 <math> B=（b_{ij}）_{d*d} </math>， <math> B </math>是有向无环图当且仅当
+对于邻接矩阵 <math> B=(b_{ij})_{d*d} </math>， <math> B </math>是有向无环图当且仅当
 :<math> tr(e^B)=d</math>

@@ 第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>v_i</math>出发经<math>k</math>步到达<math>v_j</math>的路径数量。<math>b_{ij}^k=0</math>表示不存在这样的路径。
 ===拓扑排序和识别===