다음 그래프의 인접 행렬이 아래와 같을 때, (가)～(사)에 들어갈 값… | [7급 국가직 자료구조론] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 25년 1회차
다음 그래프의 인접 행렬이 아래와 같을 때, (가)～(사)에 들어갈 값을 모두 더한 결과는?
| a | b | c | d | e | |
|---|---|---|---|---|---|
| a | 0 | (가) | 1 | 1 | 0 |
| b | (나) | 0 | 0 | 0 | (다) |
| c | 1 | 0 | 0 | (라) | 1 |
| d | 1 | 0 | 1 | 0 | 1 |
| e | 0 | (마) | 1 | (바) | (사) |
1
4
2
5
3
6
4
7
해설
(가)~(사)의 합은 6이다.
그래프의 간선은 a-b, a-c, a-d, b-e, c-d, c-e, d-e의 7개이며, 무방향 그래프의 인접 행렬은 대칭이고 자기 자신으로의 간선이 없으면 대각 원소가 0이다.
- (가)·(나): a와 b가 연결되어 있으므로 둘 다 1이다.
- (다)·(마): b와 e가 연결되어 있으므로 둘 다 1이다.
- (라)·(바): c-d, d-e 간선이 있으므로 둘 다 1이다.
- (사): e 자신으로의 간선이 없으므로 대각 원소는 0이다.
따라서 1이 6개, 0이 1개로 합은 6이다.
오류나 개정된 내용이 보이면 알려주세요