그래프는 정점(vertex)의 집합 V와 간선(edge)의 집합 E로 … | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 14년 1회차
그래프는 정점(vertex)의 집합 V와 간선(edge)의 집합 E로 이루어진다. 정점이 a, b, c 세 개 존재하고 간선이 a와 b 사이에 하나, b와 c 사이에 하나 존재한다고 할 때, 정점의 집합 V는 V ={a, b, c}와 같은 형태로 표현하고, 간선의 집합 E는 E ={ (a, b), (b, c) }와 같이 나타낸다고 하자. 정점의 집합과 간선의 집합을 이용한 그래프 표현으로 옳은 것은?1
V ={ a, b, c, d, e, f }, E ={ (a, b), (b, c), (c, a) }2
V ={ a, a, c }, E ={ (a, c), (a, a), (b, b) }3
V ={ a, c }, E ={ (a, b), (a, c), (b, c) }4
V ={ a, b, c, d }, E ={ (b, a), (d, b), (e, a) }해설
옳은 표현은 V ={ a, b, c, d, e, f }, E ={ (a, b), (b, c), (c, a) }이다.
간선의 양 끝 정점은 모두 V에 속해야 하며, V와 E는 집합이므로 같은 원소를 중복해 쓰지 않는다. 간선이 없는 고립 정점 d, e, f가 있어도 그래프로 성립한다.
- V ={ a, a, c }인 표현: 정점 a가 중복되고, 간선 (b, b)의 정점 b가 V에 없으며 자기 자신으로 가는 간선도 포함한다.
- V ={ a, c }인 표현: 간선 (a, b), (b, c)의 정점 b가 V에 없다.
- V ={ a, b, c, d }인 표현: 간선 (e, a)의 정점 e가 V에 없다.
오류나 개정된 내용이 보이면 알려주세요