21개의 노드를 가진 그래프가 3개의 트리(tree)로 이루어진 숲(f… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 알고리즘] 26년 1회차
21개의 노드를 가진 그래프가 3개의 트리(tree)로 이루어진 숲(forest)의 형태일 때, 간선(edge)의 총 개수로 가장 옳은 것은?
1
18
2
19
3
20
4
21
해설
간선의 총 개수는 18개다.
노드가 개인 트리는 간선이 개이므로, 트리 개로 된 숲의 간선 수는 노드 수 − 트리 수가 된다.
- 간선 19개: 트리가 2개인 숲일 때의 값이다.
- 간선 20개: 전체가 하나의 트리(연결 그래프)일 때의 값이다.
- 간선 21개: 간선 수가 노드 수와 같으면 반드시 사이클이 생기므로 숲이 될 수 없다.
오류나 개정된 내용이 보이면 알려주세요