그래프 이론 공부할 때 배웠던 개념들인데 매번 헷갈린다.
오랜만에 다시 정리해본다. 정리 과정이 기억에 도움 되길 바라며.
Walk는 그래프를 어떤 방식으로든 돌아다니는 길이다.
Trail은 edge 중복 없는 walk이다.
Path는 vertex 중복 없는 walk인데, 모든 path는 trail일 수밖에 없다. edge가 중복되면 vertex도 무조건 중복되기 때문이다.
즉 Walk이 Trail을, Trail이 Path를 포함하는 개념이다.
Trail이 닫혀 있으면 Circuit이라고 하고 Path가 닫혀 있으면 Cycle이라고 한다.
Eulerian Trail/Circuit은 모든 edge를 한 번씩만 지나가는 길이다.
Vertex 중복은 허용하기 때문에, Eulerian Path는 틀린 용어라고 볼 수 있다.
Hamiltonian Path/Cycle은 모든 vertex를 한 번씩만 지나가는 길이다.
당연히 이 길은 Trail의 성격도 갖고 있고, 따라서 edge가 중복되는 일은 없다.
PREVIOUS POST