다음 인접행렬이 표현하는 그래프의 부분 그래프 중에서 간선(edge)이… | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 17년 1회차
다음 인접행렬이 표현하는 그래프의 부분 그래프 중에서 간선(edge)이 최소한 1개 이상인 연결 그래프의 개수는?
| [0] | [1] | [2] | [3] | |
|---|---|---|---|---|
| [0] | 0 | 1 | 1 | 1 |
| [1] | 1 | 0 | 1 | 0 |
| [2] | 1 | 1 | 0 | 0 |
| [3] | 1 | 0 | 0 | 0 |
1
12
2
13
3
14
4
15
해설
간선이 1개 이상인 연결 부분 그래프는 14개이다.
인접행렬에서 간선은 (0,1), (0,2), (0,3), (1,2)의 4개이다. 부분 그래프가 연결이려면 고른 간선들이 하나로 이어져 있어야 하므로 간선 수별로 센다.
- 간선 1개: 4가지 모두 연결이다.
- 간선 2개: 6가지 중 공통 정점이 없는 (0,3)과 (1,2) 조합만 끊어져 5가지이다.
- 간선 3개: 4가지 모두 연결이다.
- 간선 4개: 1가지이다.
합계는 4+5+4+1=14이다.
오류나 개정된 내용이 보이면 알려주세요
이어서 풀어보기
[7급 국가직 자료구조론] 17년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요비슷한 기출
- n개의노드로구성된무방향그래프의최대간선수는? {"answer":3,"content":[{"content":"n-1","url":""},{"content"20년-4회차-정보처리기사-필기
- 도면에서기울기를표현하는방법으로옳지않은것은? {"answer":1,"content":[{"content":"1/n:수평거리1에대하여높이n로나눈것\n","21년-3회차-산림기사-필기
- 산업재해통계중재해발생건수(100만배)를총연인원의근로시간수로나누어산정하는것으로재해발생의정도를표현하는것은? {"answer":2,"content":[{"c21년-3회차-산업위생관리기사-필기