모든 닫힌 홀수 walk는 홀수 cycle을 포함한다. (walk, trail, path, cycle) / Graph Theory #1

graph theory

Every closed odd walk contains an odd cycle. (모든 닫힌 홀수 walk는 홀수 cycle을 포함한다.)

위의 정리를 이해하려면 walk와 path에 대해서 알아야 한다. Graph는 vertex와 edge로 이루어져 있다. 하나의 vertex에서 다른 vertex로 edge를 통해서 이동하는 상상을 쉽게 해볼 수 있을 것이다. 이처럼 edge를 통해서 vertex를 이동하는 ‘길’을 walk라고 한다.