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개다.

노드가 nn개인 트리는 간선이 n−1n-1개이므로, 트리 kk개로 된 숲의 간선 수는 노드 수 − 트리 수가 된다.

21−3=1821-3=18

  • 간선 19개: 트리가 2개인 숲일 때의 값이다.
  • 간선 20개: 전체가 하나의 트리(연결 그래프)일 때의 값이다.
  • 간선 21개: 간선 수가 노드 수와 같으면 반드시 사이클이 생기므로 숲이 될 수 없다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기