Walk, Trail, Path, Circuit, Circle
자꾸 까먹을 때는 K-고등학교 스타일로 외워버리는 것도 좋은 방법
이것들은 대체 무엇인가?
Walk, Trail, Path, Circuit, Circle은 그래프 이론에서 다루는 기본 개념들이다. 그래프는 점들과, 그 점들을 잇는 선으로 구성된다.
점을 Vertex라고 하고, 선을 Edge라고 한다. 선에 방향이 있으면 Arc라고 하기도 한다. 참고로 Node는 수학에서 사용하는 용어는 아니다.
그래프 이론은 컴퓨터 공학에서 중요하게 활용된다고 알고 있다. 예를 들어 버전 관리가 중요한 시스템, 예를 들어 공정 관리나 전자 서명 등을 구현할 때에는 DAG(비순환그래프)를 이용해서 버전이 꼬이는 것을 막을 수 있다.
물론 프로그래머들이 이론을 깊이 공부한 후 반영할 리는 없다고 생각한다. 얕은 수준에서 알고리즘을 구현하다 보니 DAG가 되는 식일 것이라고 본다. 또는 수학을 전공한 프로그래머가 라이브러리를 만들어두었고, 나머지는 그것을 활용하는 식일 것이다.
Walk
Walk는 그래프를 어떤 방식으로든 돌아다니는 길이다.
Trail
Trail은 Edge가 중복하지 않는 Walk이다.
Path
Path는 Vertex가 중복하지 않는 Trail이다. 참고로 모든 Path는 Trail이다. Trail이 아닌데 Path인 경우는 없다. (생각해보라. Edge가 중복되면 Vertex도 무조건 중복되기 마련이다.)
Circuit
Trail의 기종점이 같으면 Circuit이다. Eulerian Circuit이 유명하다. Vertex 중복은 허용하기 때문에, Eulerian Path는 틀린 용어라고 볼 수 있다.
Cycle
Path의 기종점이 같으면 Cycle이다. Hamiltonian Cycle이 유명하다.