다음의 인접행렬로 표시되는 그래프 G = (V, E)는?(단, Fals… | [7급 국가직 자료구조론] 07년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 07년 1회차
다음의 인접행렬로 표시되는 그래프 G = (V, E)는?
(단, False는 from에서 to까지의 간선이 없고, True는 from에서 to까지의 간선이 있음을 의미한다)
| to from | a | b | c | d |
|---|---|---|---|---|
| a | False | False | True | False |
| b | True | False | False | False |
| c | False | False | False | True |
| d | True | False | True | False |
1
V = {a, b, c, d}, E = {<b,a>,<a,c>,<d,b>,<b,b>,<c,d>}2
V = {a, b, c, d}, E = {<a,b>,<b,a>,<a,c>,<d,c>,<c,d>}3
V = {a, b, c, d}, E = {<b,a>,<a,c>,<d,c>,<d,a>,<c,d>}4
V = {a, b, c, d}, E = {<b,a>,<a,c>,<d,b>,<d,a>,<a,d>}해설
이 인접행렬이 나타내는 그래프는 간선 집합이 E = {<b,a>, <a,c>, <d,c>, <d,a>, <c,d>}인 방향 그래프이다.
True인 칸 (from, to)마다 간선이 하나씩 생긴다. True 칸은 a→c, b→a, c→d, d→a, d→c의 5개뿐이다.
- <d,b>와 자기 루프 <b,b>를 포함한 집합: 두 칸 모두 False이고, d→a와 d→c가 빠져 있다.
- <a,b>를 포함한 집합: a행 b열이 False이므로 간선이 아니며, d→a도 빠져 있다.
- <d,b>와 <a,d>를 포함한 집합: 두 칸 모두 False이고, c→d와 d→c가 빠져 있다.
오류나 개정된 내용이 보이면 알려주세요