다음 인접 행렬(adjacency matrix)에 의해 표현되는 그래프… | [7급 국가직 자료구조론] 20년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 20년 1회차
다음 인접 행렬(adjacency matrix)에 의해 표현되는 그래프에 대한 설명으로 옳은 것은? (단, 인접 행렬에서 [i]는 정점 i를 의미한다)
[0][1][2][3][4]
[0]01000
[1]00110
[2]00001
[3]00001
[4]01000
1
간선의 개수가 5개인 무방향 그래프(undirected graph)이다.
2
정점 0에서 정점 4까지의 단순 경로(simple path) 길이는 2이다.
3
정점 3에 도달하기 위한 경로가 없는 정점이 있다.
4
사이클(cycle)이 존재하는 방향 그래프(directed graph)이다.
해설

주어진 그래프는 사이클이 존재하는 방향 그래프이다.

행렬이 대칭이 아니므로 방향 그래프이고, 간선은 0→1, 1→2, 1→3, 2→4, 3→4, 4→1의 6개이다. 이 중 1→2→4→1(또는 1→3→4→1)이 사이클을 이룬다.

  • 간선 5개인 무방향 그래프: 행렬이 비대칭인 방향 그래프이고 간선도 6개이다.
  • 정점 0에서 정점 4까지 단순 경로 길이 2: 0→1→2→4 또는 0→1→3→4로 길이가 3이다.
  • 정점 3에 도달할 경로가 없는 정점: 0→1→3, 2→4→1→3, 4→1→3처럼 모든 정점이 정점 1을 거쳐 정점 3에 도달한다.

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

이어서 풀어보기

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