다음 인접 행렬로 표현되는 그래프에 대한 설명으로 옳지 않은 것은?12… | [7급 국가직 자료구조론] 11년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 11년 1회차
다음 인접 행렬로 표현되는 그래프에 대한 설명으로 옳지 않은 것은?
1234
10101
21011
31000
40100
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처럼 되돌아오는 경로가 있으므로 방향 사이클이 존재한다.

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

이어서 풀어보기

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