목록오일러 경로 (1)

넘치게 채우기

오일러 경로와 오일러 회로(Eulerian Trail, Eulerian Circuit)

오일러 경로와 오일러 회로오일러 경로는 그래프에서의 모든 간선을 단 한번씩만 통과하는 경로이다.오일러 경로의 출발점과 종료점의 구분이 없다면, 오일러 회로이다. 오일러 경로는 다음의 특징을 가진다:무방향 그래프인 경우, 두 노드를 제외한 모든 노드가 짝수 개의 차수를 가진다. 두 노드는 홀수 개의 차수를 가진다.어디서든 순회를 시작해도 오일러 경로이다.방향 그래프인 경우, 두 노드를 제외한 모든 노드가 같은 진출차수 및 진입차수를 가진다. 두 노드는 진출차수가 하나 더 많은 노드 하나와, 진입차수가 하나 더 많은 노드로 루성된다.진출차수가 하나 더 많은 노드가 출발점이고, 진입차수가 하나 더 많은 노드가 도착점이다. 오일러 회로는 다음의 특징을 가진다:무방향 그래프인 경우, 모든 정점의 차수가 짝수이다...
컴퓨터과학/알고리즘 2024. 10. 16. 10:26
이전 Prev 1 Next 다음