パス（グラフ理論）

• ウォークとは、頂点の列を結ぶ有限または無限のエッジの列のことである。^{[ 2 ]}

G = ( V , E , Φ )をグラフとする。有限ウォークとは、頂点の列( v 1 _, v 2 _, ... , v n )が存在し、i = 1, 2, ..., n − 1 に対して Φ ( e i ) = { v i , v i + 1 } となるようなエッジの列 ( e 1 , e 2 , ..., e n − 1 ) のこと_である_。 ( _{v 1 ,} v 2 , _... , v _n )は_{ウォークの}頂点列である。ウォークはv 1 = v nの_場合に閉じ_られ、それ_以外の場合 は開いて_いる。無限_ウォークとは、ここで説明したのと同じタイプのエッジの列であるが、最初または最後の頂点を持たないものであり、半無限ウォーク (またはレイ) は最初の頂点を持つが最後の頂点を持たない。

• トレイルとは、すべての縁がはっきりと区別できる散歩道のことである。^{[ 2 ]}
• パスとは、すべての頂点（したがってすべての辺も）が異なる経路のことである。^{[ 2 ]}

w = ( e ₁ , e ₂ , ..., e _{n − 1} )が頂点列( v ₁ , v ₂ , ..., v _n )を持つ有限ウォークである場合、wはv ₁からv _nへのウォーク であると言われます。トレイルやパスについても同様です。2 つの異なる頂点間に有限ウォークが存在する場合、それらの間には有限トレイルと有限パスも存在します。

著者によっては、パスのすべての頂点が互いに異なることを要求せず、代わりにすべての頂点が異なるパスを指すのに「単純パス」という用語を使用する。

重み付きグラフでは、グラフ内のすべてのエッジに値（重み）が割り当てられます。重み付きグラフにおける経路（または道筋）の重みは、通過したエッジの重みの合計です。重みの代わりに、コストや長さといった言葉が使われることもあります。

• 有向ウォークとは、同じ方向に向かう有限または無限のエッジの列で、一連の頂点を結びます。^{[ 2 ]}

G = ( V , E , Φ )を有向グラフとする。有限有向ウォークとは、頂点の列( v 1 _, v 2 _, ..., v _n )が存在し、i = 1, 2, ..., n − 1 に対して Φ ( e i ) = ( v i , v i + 1 ) となるようなエッジの列 ( e 1 , e 2 , ..., e n − 1 ) のことである。( _{v 1} , v 2 , _... , v _n )は_{有向ウォーク}の頂点列_である。有向ウォークはv 1 = _v nの_場合に閉じ_られ、それ 以外の場合_は開いて_いる。無限有向ウォークは_、ここで説明したのと同じタイプのエッジの列であるが、最初または最後の頂点を持たない。半無限有向ウォーク (またはレイ) は、最初の頂点は持つが最後の頂点を持たない。

• 有向トレイルとは、すべてのエッジが明確に区別できる有向ウォークのことである。^{[ 2 ]}
• 有向パスとは、すべての頂点が異なる有向経路のことである。^{[ 2 ]}

w = ( e ₁ , e ₂ , ..., e _{n − 1} )が頂点列( v ₁ , v ₂ , ..., v _n )を持つ有限有向ウォークである場合、wはv ₁からv _nへのウォークであると言われます。有向トレイルまたはパスについても同様です。2 つの異なる頂点間に有限有向ウォークが存在する場合、それらの間には有限有向トレイルと有限有向パスも存在します。

「単純有向パス」とは、すべての頂点が異なるパスのことである。

重み付き有向グラフでは、グラフ内のすべてのエッジに値（重み）が割り当てられます。重み付き有向グラフにおける有向ウォーク（またはトレイル、パス）の重みは、通過したエッジの重みの合計です。重みの代わりに、コストや長さといった用語が使われることもあります。