그래프에 대한 설명으로 가장 옳지 않은 것은? | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 자료구조론] 26년 1회차
그래프에 대한 설명으로 가장 옳지 않은 것은?
1
완전 그래프에서 정점이 개인 방향 그래프의 최대 간선 수는 개이다.
2
방향 그래프의 인접 행렬에서 행 의 합은 정점 의 진출 차수이다.
3
방향 그래프의 인접 리스트에서 각 정점의 헤드에 연결된 노드의 수는 정점의 진출 차수이다.
4
개의 간선을 가진 무방향 그래프의 인접 리스트에 저장되는 연결 노드의 총 수는 개이다.
해설
무방향 그래프의 인접 리스트에는 간선 하나가 양 끝 정점에 한 번씩 저장되므로 연결 노드 수는 개이다. 따라서 개라는 설명이 옳지 않다.
방향 그래프라면 간선 하나가 출발 정점의 리스트에만 저장되어 개가 된다.
- 방향 완전 그래프는 서로 다른 두 정점 사이에 양방향 간선이 모두 있으므로 최대 개이다.
- 인접 행렬의 행 는 정점 에서 나가는 간선을 나타내므로 행의 합은 진출 차수이다.
- 인접 리스트에서 헤드 에 연결된 노드는 에서 나가는 간선의 도착 정점이므로 그 수는 진출 차수이다.
오류나 개정된 내용이 보이면 알려주세요