그래프에 관한 다음 설명 중 옳은 문장의 개수는 몇 개인가?ㄱ. 무방향… | [7급 국가직 자료구조론] 09년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 09년 1회차
그래프에 관한 다음 설명 중 옳은 문장의 개수는 몇 개인가?ㄱ. 무방향 그래프를 인접행렬로 표현하면 항상 대칭인 행렬이 된다.
ㄴ. 무방향 그래프에서 모든 정점의 차수(degree)의 합은 간선의 수와 같다.
ㄷ. 정점이 v개인 무방향 완전그래프의 간선의 수는 개이다.
ㄹ. 정점이 v개, 간선이 e개인 그래프를 인접행렬로 표현하면 필요한 메모리는 O(v + e)이다.
ㅁ. 인접행렬로 표현된 정점이 v개, 간선이 e개인 무방향 그래프에서 너비우선탐색의 수행시간은 O()이다.
1
1 개
2
2 개
3
3 개
4
4 개
해설
옳은 문장은 ㄱ, ㅁ의 두 개이다.
무방향 그래프는 간선 (i, j)와 (j, i)가 같으므로 인접행렬이 대칭이다. 인접행렬 기반 너비우선탐색은 정점마다 행 하나(v칸)를 모두 훑으므로 이다.
- 차수의 합: 간선 하나가 양 끝 정점의 차수를 하나씩 올리므로 간선 수의 2배()이다.
- 완전그래프의 간선 수: 서로 다른 두 정점 쌍의 수인 개이다.
- 인접행렬의 메모리: 간선 수와 무관하게 행렬이 필요하므로 이며, O(v + e)는 인접리스트의 공간이다.
오류나 개정된 내용이 보이면 알려주세요