路与圈

一条边只给出一步相邻，游走把这些局部步骤依次拼接。允许重复时，它记录真实行程中可能发生的折返；去掉重复边得到迹，进一步去掉重复顶点才得到描述可达性所需的最简证书。

圈表示一段能够绕行后回到原处的闭合结构。圈上的任一边都有另一条沿圈连接其端点的路线，所以它体现边级冗余；树恰好把这种冗余全部排除。闭游走可能只是来回走同一条边，闭迹也可能依次绕过多个圈，因而“闭合”本身还不足以说明对象就是一个圈。

在共享一个顶点的两个三角形中，可以从共享点绕完左三角形，再绕完右三角形回到共享点。所得序列是一条闭迹，因为每条边只走一次；它不是圈，因为共享顶点在首尾之外又出现了一次。两个三角形各自才是其中的圈。

设图由顶点 $s,t$ 之间三条内部顶点互不相交的路组成，常称为 theta 图。任取其中两条路便合成一个圈，所以同一条边可能参与多个圈。这个结构说明“图含圈”并不意味着圈只有一个，也不意味着所有边都有同样的替代路线。

在简单图中，序列 $u,v,u$ 是长度为二的闭游走，却两次经过同一条无向边，因此既不是迹也不是圈。若多重图中 $u,v$ 之间有两条不同平行边，沿不同边往返可以形成长度为二的圈；模型改变后，最短圈长度也会改变。

平凡路径只含一个顶点，长度为零；它使“每个顶点都可达自身”无需另设例外。圈则至少有三条边。计算最短路时应最小化长度或权重，不能把“顶点不重复”误当成已经具有最短性。

在图公理库有限简单无向图Graph · Finite simple undirected graph · 图由有限顶点集与无序二元顶点子集组成的边集所确定的简单无向图。中，两点之间存在路定义连通性公理库图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。；所有 $u$–$v$ 路的最小长度定义无权距离。游走删环得到路的引理保证：对存在性与最短长度问题，允许绕行并不会创造新的可达点。

一条边是桥，当且仅当它不属于任何圈。若边在圈上，删去它后可沿圈其余部分绕行；若删边后端点仍可相连，那条替代路径与被删边又合成一个圈。这个短证明把桥公理库割点与桥Cut vertex and bridge删除后增加连通分量数的顶点或边。与圈的冗余图像精确对应起来。

树公理库树Tree连通且无圈的有限简单无向图，也就是任意两点之间只有一条简单路径的图。可由“连通且无圈”定义，也可由“任意两点间恰有一条路”刻画。两条不同的 $u$–$v$ 路在首次分开与再次汇合之间会产生圈；反过来，圈上的两点沿两个方向给出两条不同路径。

Euler 迹公理库欧拉迹Eulerian trail · Eulerian path恰好一次经过每条边的迹。要求每条边恰经过一次，顶点可以重复；Hamilton 路与圈公理库Hamilton 路与 Hamilton 圈Hamiltonian path · Hamiltonian cycle恰好一次访问图中每个顶点的路径，以及首尾相接的这种圈。要求覆盖每个顶点，通常不覆盖全部边。Menger 定理公理库Menger 定理Menger's theorem两点间内部顶点不交路径的最大条数等于分离两点所需删去的最少顶点数。研究多条内部不交或边不交路径与最小割的对应。三类问题使用相似的路线图像，量词与算法难度却各不相同。

在有向图中，每一步还必须顺着弧的方向；反向走同一条线不再自动合法。有向路与有向圈公理库有向图Directed graph · Digraph以顶点有序对为弧、能够保留连接方向的有限简单图结构。因而需要单独定义，尤其允许反向弧对形成长度为二的有向圈。