그래프에 대한 설명으로 옳은 것만을 모두 고르면?ㄱ. 무방향 그래프(u… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 19년 1회차
그래프에 대한 설명으로 옳은 것만을 모두 고르면?
ㄱ. 무방향 그래프(undirected graph)를 인접행렬(adjacency matrix)로 표현하면 주대각선을 중심으로 상위 행렬과 하위 행렬이 대칭이 된다.
ㄴ. 사이클이 없고 n - 1개의 간선(edge)을 갖는 연결 그래프(connected graph)를 트리(tree)라고 한다.
ㄷ. n개의 정점(vertex)을 가진 방향 그래프의 최대 간선 수는 n(n+1)2\dfrac{n(n+1)}{2} 개이다.
ㄹ. 경로를 구성하는 간선의 수를 길이라고 할 때, 방향 그래프에서 사이클(cycle)의 길이는 항상 3 이상이다.
1
ㄱ, ㄴ
2
ㄱ, ㄷ
3
ㄴ, ㄷ
4
ㄷ, ㄹ
해설

옳은 것은 ㄱ, ㄴ이다.

무방향 그래프는 간선 (u, v)와 (v, u)가 같으므로 인접행렬이 주대각선 기준으로 대칭이다. 사이클 없이 연결되고 간선이 n-1개인 그래프는 트리의 정의와 같다.

  • ㄷ: n개 정점의 방향 그래프 최대 간선 수는 n(n−1)n(n-1)이며, n(n+1)/2n(n+1)/2가 아니다.
  • ㄹ: 방향 그래프에서는 ⟨u,v⟩\langle u,v \rangle와 ⟨v,u⟩\langle v,u \rangle만으로 길이 2인 사이클이 생기므로 항상 3 이상인 것은 아니다.

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

이어서 풀어보기

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