道 (グラフ理論)
小道(trail)は頂点の反復を可能とするが、辺は反復できない。
道の上で隣接しない頂点間に辺が存在しない道を誘導道 (induced path) と呼ぶ。
グラフの全ての頂点を含む単純閉道をハミルトン閉路と呼ぶ。
共通する内部頂点を持たない2つの道は互いに「独立」、あるいは「内部頂点が互いに素 (点素)」であるという。 また、共通する内部の辺を持たない2つの道は互いに「辺素」であるという
道を構成する辺の数を道の「長さ」と呼び、複数回出現する辺は複数回カウントする。頂点が1つでも道ということができ、その場合の長さはゼロである。
重み付きグラフは各辺に値(重み)が対応しているグラフである。この場合「道の重み」は、道に属する辺の重みの総和である。重み (weight) ではなく、コスト (cost) とか長さ (length) と呼ぶこともある。