387
个编辑
更改
跳到导航
跳到搜索
第5行：
第5行： − − 第12行：
第10行： − − − −
→定义
==定义==
==定义==
图是由顶点和连接顶点对的边组成的，顶点可以是任何一种由边成对连接的对象。在有向图中，每条边都有一个方向，从一个顶点到另一个顶点。有向图中的<font color="#ff8000">路径Path</font>是一个边序列，序列中每条边的结束顶点是序列中下一条边的起始顶点; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相同，那么它就形成了一个环。有向无环图是一个没有环的有向图[1][2][3]。
图是由顶点和连接顶点对的边组成的，顶点可以是任何一种由边成对连接的对象。在有向图中，每条边都有一个方向，从一个顶点到另一个顶点。有向图中的<font color="#ff8000">路径Path</font>是一个边序列，序列中每条边的结束顶点是序列中下一条边的起始顶点; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相同，那么它就形成了一个环。有向无环图是一个没有环的有向图[1][2][3]。
当存在一条从顶点u到顶点v的路径时，顶点v被称作是从顶点u<font color="#ff8000">可达的Reachability</font>。每个顶点都是从自身可达的（通过一条没有边的路径）。如果一个顶点可以从一条<font color="#32cd32"> 非平凡</font>路径（一条由一个或更多边组成的路径）到达自身，那么这条路径就是一个环。因此，有向无环图也可以被定义为没有顶点可以通过非平凡路径到达自身的图。[4]
当存在一条从顶点u到顶点v的路径时，顶点v被称作是从顶点u<font color="#ff8000">可达的Reachability</font>。每个顶点都是从自身可达的（通过一条没有边的路径）。如果一个顶点可以从一条<font color="#32cd32"> 非平凡</font>路径（一条由一个或更多边组成的路径）到达自身，那么这条路径就是一个环。因此，有向无环图也可以被定义为没有顶点可以通过非平凡路径到达自身的图。[4]
== 数学性质 ==
== 数学性质 ==