グラフ理論の紛らわしい言葉

歩道とか経路とか小道とか紛らわしい用語の整理。こういう学術的な専門用語は日本語で覚えるより英語で覚えた方がいいと思っているので（英語で覚えると世界中のエンジニアと会話ができるから）、英語で書きます。

まず、walkというのが大きな集合としてあります。walkとは、接点と枝の列です。そしてwalkには、特に重要な以下の4つを形があります。

• trail
• path
• circuit
• cycle

まず、始点と終点が同一か否かで、trail, pathとcircuit、cycleに分かれます。問題は、trailとpathの違い、circuitとcycleの違いです。

まず、trailとpathの違いについて。trailは、含まれる枝がdistinctなものです。pathは含まれる接点がdistinctなものです。

上の図だと、1->2->3->4->2はtrailです。しかし、2の節点を2度通っているため、pathではありません。1->2->3はpathです。

　ここで思い浮かぶのは、shortest pathという言葉です。あれは、pathですよね？ダイクストラをやるときに、一度通った点はもう通らないというような処理をしているかと思います。また、Euler trailという言葉があります。あれは、同じ接点を複数回通るのでpathじゃなくて、trailなんです。同様に、Hamiltonian pathとう言葉があります。あれは、trailじゃなくて、pathですよね。

次に、始点と終点が同一になる、circuitとcycleについて。この2つも同様の基準でカテゴライズされています。circuitは含まれている枝がdistinctであるもの、cycleは含まれている節点がdistinctであるものを指します。ループが一つだけのもの（始点と終点だけ）がcycle、他にもループを持っているものをcircuitと呼ぶと考えればいいです。

以上から、集合論上は、以下の関係が成り立つかと思います。

path ⊂ trail ⊂ walk

cycle ⊂ circuit ⊂ walk