정보처리기사
연도별 풀이 오답노트 별표문제
  1. 홈
    2. ›
  2. 정보처리기사
    3. ›
  3. 2020년09월26일
    4. ›
  4. 33번

2020년09월26일 33번

[소프트웨어 개발] n 개의 노드로 구성된 무방향 그래프의 최대 간선수는?

  • ① n－1
  • ② n／2
  • ③ n(n－1)／2
  • ④ n(n＋1)
(정답률: 80%)

문제 해설

무방향 그래프에서 각 노드는 다른 모든 노드와 연결될 수 있으므로, 각 노드는 n-1개의 간선을 가질 수 있습니다. 따라서 n개의 노드가 모두 n-1개의 간선을 가지면, 그래프의 총 간선 수는 n(n-1)이 됩니다. 그러나 이 간선 수는 각 간선이 두 번씩 계산되었으므로, 최종적으로 총 간선 수는 n(n-1)/2가 됩니다. 따라서 정답은 "n(n－1)／2"입니다.
이전 문제 다음 문제
AppStore에서 다운로드 APK 다운로드

연도별

진행 상황

0 오답
0 정답