그래프 이론에서 순회 가능한 그래프란 무엇입니까?

그래프 이론에서 순회 가능한 그래프는 모든 정점과 간선을 순회할 수 있는 그래프입니다. 즉, 모든 정점을 정확히 한 번씩 방문하고 시작 정점으로 돌아갈 수 있게 해주는 그래프이다.

모든 정점이 서로 연결되어 있는 그래프이기 때문에 순회 가능한 그래프(traversable graph)라고도 한다. .

예를 들어, A와 B 사이에 간선, B와 C 사이에 간선, A와 C 사이에 간선이 있는 세 개의 정점 A, B, C가 있는 간단한 그래프를 생각해 보세요. 이 그래프는 다음을 수행할 수 있기 때문에 순회할 수 있습니다. 정점 A에서 시작하여 가장자리를 따라 B, C로 이동하고 A로 돌아갑니다. 반면에 두 개의 개별 그래프와 같이 두 개의 연결이 끊긴 구성 요소가 있는 그래프는 모든 정점을 방문할 수 없기 때문에 순회할 수 없습니다. 정확히 한 번만 실행하고 시작 정점으로 돌아갑니다.