다음과 같은 방향 그래프에 대한 반사 이행적 폐쇄(reflexive t… | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 08년 1회차
다음과 같은 방향 그래프에 대한 반사 이행적 폐쇄(reflexive transitive closure) 행렬 D*를 인접 행렬로 바르게 표현한 것은?
문제 이미지
1
01234
001111
101111
201111
301111
400000
2
01234
011111
101111
201111
301111
400001
3
01234
001000
100100
200010
301010
400000
4
01234
011000
101100
200110
301010
400001
해설

반사 이행적 폐쇄는 자기 자신을 포함해 경로로 도달 가능한 모든 정점을 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인 행렬: 반사성은 있으나 경로를 통한 도달(이행성)이 반영되지 않았다.

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

이어서 풀어보기

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