정점의 개수가 n인 단순 그래프가 트리이기 위한 필요충분조건으로 옳지 … | [7급 국가직 자료구조론] 26년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 26년 1회차
정점의 개수가 n인 단순 그래프가 트리이기 위한 필요충분조건으로 옳지 않은 것은? (단, n은 3 이상의 정수이다)
1
사이클이 없고 연결요소의 개수가 1이다.
2
임의의 두 정점 사이에 존재하는 경로의 개수는 1이다.
3
간선의 개수가 n－1이고, 차수가 1인 정점의 개수가 2 이상이다.
4
사이클이 없지만, 인접하지 않은 임의의 두 정점 사이에 간선을 추가하면 사이클의 개수가 1이 된다.
해설
옳지 않은 것은 “간선 n−1개이고 차수 1인 정점이 2개 이상”이라는 조건이다.
간선 수가 n−1이어도 연결성이나 비순환성이 보장되지 않으면 트리가 아니다. 예를 들어 정점 5개 중 3개로 삼각형(간선 3)을 만들고 나머지 2개를 간선 하나로 이으면 간선 4개, 차수 1인 정점 2개지만 사이클이 있고 연결되어 있지 않다.
- 사이클이 없고 연결요소가 하나라는 것은 트리의 정의 그 자체다.
- 임의의 두 정점 사이 경로가 정확히 하나라는 것도 트리의 동치 조건이다.
- 사이클이 없으면서 간선을 하나만 더해도 사이클이 생긴다는 것은 극대 비순환 그래프, 곧 트리의 동치 조건이다.
오류나 개정된 내용이 보이면 알려주세요