그래프에 대한 설명으로 가장 옳지 않은 것은? | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 자료구조론] 26년 1회차
그래프에 대한 설명으로 가장 옳지 않은 것은?
1
완전 그래프에서 정점이 nn개인 방향 그래프의 최대 간선 수는 n(n−1)n(n-1)개이다.
2
방향 그래프의 인접 행렬에서 행 ii의 합은 정점 ii의 진출 차수이다.
3
방향 그래프의 인접 리스트에서 각 정점의 헤드에 연결된 노드의 수는 정점의 진출 차수이다.
4
ee개의 간선을 가진 무방향 그래프의 인접 리스트에 저장되는 연결 노드의 총 수는 ee개이다.
해설

무방향 그래프의 인접 리스트에는 간선 하나가 양 끝 정점에 한 번씩 저장되므로 연결 노드 수는 2e2e개이다. 따라서 ee개라는 설명이 옳지 않다.

방향 그래프라면 간선 하나가 출발 정점의 리스트에만 저장되어 ee개가 된다.

  • 방향 완전 그래프는 서로 다른 두 정점 사이에 양방향 간선이 모두 있으므로 최대 n(n−1)n(n-1)개이다.
  • 인접 행렬의 행 ii는 정점 ii에서 나가는 간선을 나타내므로 행의 합은 진출 차수이다.
  • 인접 리스트에서 헤드 ii에 연결된 노드는 ii에서 나가는 간선의 도착 정점이므로 그 수는 진출 차수이다.

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

이어서 풀어보기

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