다음 인접 행렬로 표현되는 그래프에 대한 설명으로 옳지 않은 것은?12… | [7급 국가직 자료구조론] 11년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 11년 1회차
다음 인접 행렬로 표현되는 그래프에 대한 설명으로 옳지 않은 것은?
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 |
| 2 | 1 | 0 | 1 | 1 |
| 3 | 1 | 0 | 0 | 0 |
| 4 | 0 | 1 | 0 | 0 |
1
방향 그래프(directed graph)이다.
2
간선(edge)의 개수는 7이다.
3
강력 연결 요소(strongly connected component)는 2개이다.
4
방향 사이클이 존재한다.
해설
모든 정점이 서로 도달 가능하므로 강력 연결 요소는 1개이며, 2개라는 설명이 옳지 않다.
간선은 1→2, 1→4, 2→1, 2→3, 2→4, 3→1, 4→2이다. 1→2→3→1과 1→4→2→1의 사이클로 네 정점이 모두 연결된다.
- (1,3)은 0인데 (3,1)은 1처럼 행렬이 대칭이 아니므로 방향 그래프이다.
- 행렬의 1을 모두 세면 7이므로 간선은 7개이다.
- 1→2→1처럼 되돌아오는 경로가 있으므로 방향 사이클이 존재한다.
오류나 개정된 내용이 보이면 알려주세요