[7급 국가직 자료구조론 2019년 11번]

ㄱ. 무방향 그래프(undirected graph)를 인접행렬(adjacency matrix)로 표현하면 주대각선을 중심으로 상위 행렬과 하위 행렬이 대칭이 된다.

ㄴ. 사이클이 없고 n － 1개의 간선(edge)을 갖는 연결 그래프(connected graph)를 트리(tree)라고 한다.

ㄷ. n개의 정점(vertex)을 가진 방향 그래프의 최대 간선 수는 $\frac{n(n+1)}{2}$ 개이다.

ㄹ. 경로를 구성하는 간선의 수를 길이라고 할 때, 방향 그래프에서 사이클(cycle)의 길이는 항상 3 이상이다.