다음과 같은 방향 그래프에 대한 반사 이행적 폐쇄(reflexive t… | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 08년 1회차
다음과 같은 방향 그래프에 대한 반사 이행적 폐쇄(reflexive transitive closure) 행렬 D*를 인접 행렬로 바르게 표현한 것은?
1
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 1 | 1 | 1 |
| 3 | 0 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 0 | 0 |
2
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 1 | 1 | 1 |
| 3 | 0 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 0 | 1 |
3
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 2 | 0 | 0 | 0 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 | 0 |
| 4 | 0 | 0 | 0 | 0 | 0 |
4
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 2 | 0 | 0 | 1 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 | 0 |
| 4 | 0 | 0 | 0 | 0 | 1 |
해설
반사 이행적 폐쇄는 자기 자신을 포함해 경로로 도달 가능한 모든 정점을 1로 표시한 행렬이다.
그래프는 0→1→2→3 경로와 3→1 역방향 간선, 3→4 간선으로 이루어져 있어 1, 2, 3은 서로 순환하며 4로도 갈 수 있다. 따라서 0행은 모두 1, 1~3행은 0열만 0, 4행은 대각 원소만 1이다.
- 대각 원소 (0, 0)과 (4, 4)가 0인 행렬: 길이 0 경로를 포함하지 않은 이행적 폐쇄이다.
- 대각 원소가 0이고 직접 간선 일부만 1인 행렬: 반사성도 없고 경로를 통한 도달도 반영되지 않았다.
- 대각 원소는 1이지만 직접 간선 일부만 1인 행렬: 반사성은 있으나 경로를 통한 도달(이행성)이 반영되지 않았다.
오류나 개정된 내용이 보이면 알려주세요
