一个有向闭路的环

在图论中,(英語:cycle,也称回路)是一条只有第一个和最后一个顶点重复的非空路径。在有向图中的环(有向环)是一条只有第一个和最后一个顶点重复的非空路径。

没有环的图称为无环图,没有环的有向图称作有向无环图(DAG)[1]。一个没有环的连通图称作

定义编辑

回路,环路编辑

  • 一个回路是一条非空的有向路径, 其中第一个顶点和最后一个顶点相同。令图 ,一个回路是一条非空路径 ,其顶点序列为 [2]
  • 一个环路简单回路是只有第一个与最后一个顶点相同的回路[2]

有向回路,有向环路编辑

  • 一个有向回路是一个非空的有向路径,其第一个与最后一个顶点相同[2]。 令有向图 ,一个回路是一条非空有向路径 ,其顶点序列为 
  • 一个有向环路,或者简单有向回路,是只有第一个与最后一个顶点重复的有向回路[2]

参考编辑

  1. ^ (希)鲁伊·米格尔·福特(Rui Miguel Forte)著. 预测分析 R语言实现. 北京:机械工业出版社. 2017.01: 162. ISBN 978-7-111-55354-0. 
  2. ^ 2.0 2.1 2.2 2.3 Bender & Williamson. 2010: 164.