단순 무방향 그래프(simple undirected graph) G가 … | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 21년 1회차
단순 무방향 그래프(simple undirected graph) G가 주어졌을 때, 정점(vertex)의 중복 방문을 허용하되, 간선(edge)의 중복은 허용하지 않는 경로(path)를 트레일(trail)이라고 한다. 그래프의 모든 간선들을 단 한 번씩만 통과하되 출발점과 도착점이 일치하지 않는 것을 오일러 트레일(Euler trail)이라고 할 때, 다음 그래프 중에서 오일러 트레일이 존재하지 않는 그래프는?
1
[그림]
2
[그림]
3
[그림]
4
[그림]
해설
오일러 트레일이 없는 것은 왼쪽 세로선에 V자 두 개가 붙은 그래프이다.
연결 그래프에 출발점과 도착점이 다른 오일러 트레일이 있으려면 홀수 차수 정점이 정확히 2개여야 한다. 이 그래프는 왼쪽 위 꼭짓점(3), 왼쪽 가운데 정점(5), 왼쪽 아래 꼭짓점(3), 오른쪽 가운데 정점(3)으로 홀수 차수 정점이 4개이다.
- 바깥·안쪽 사각형 두 개를 세로선이 관통하는 그래프: 바깥 사각형 위·아래 가운데 정점만 차수 3이라 홀수 정점이 2개이다.
- 대각선이 들어간 3×3 격자 그래프: 위쪽 가운데 정점과 왼쪽 가운데 정점만 차수 5라 홀수 정점이 2개이다.
- 사각형 세 개를 세로선이 관통하는 그래프: 바깥 사각형 위·아래 가운데 정점만 차수 3이고 안쪽 교차점은 모두 차수 4라 홀수 정점이 2개이다.
오류나 개정된 내용이 보이면 알려주세요