图论中cycle、path、walk、loop等概念

2022年10月18日 | 分类: 【编程】

视频讲解:https://video.zhihu.com/video/1484551640917663744

cycle:

cycle可以和loop一起解释。在一个有向图中,从一个顶点开始,沿着边前进,最终回到起始顶点。如果发生了这种情况,表明我们走了一个圈,我们走过的路径形成了一个环(cycle),如果这些边形成了长度为 1 的环,我们称之为自环(loop)。

path:

path得和walk, trail 三个概念一起讲。各个点可以通过一条线直接相连,也可以通过一系列线间接相连。在一个图中的这一系列线就叫做一条“线路(walk)” 。

如果线路没有重合的边,则称该线路为”轨迹(trail)“, 有可能有重复的点。

如果线路中每条线,每个点都各不相同,则称该线路为“途径(path)”

path一定是trail,trail一定是walk, 有这种不可逆的关系“Irreversible relationship”

作者:爱学习的就是我
链接:https://www.zhihu.com/question/438157292/answer/1786986570