다음 인접행렬이 표현하는 그래프의 부분 그래프 중에서 간선(edge)이… | [7급 국가직 자료구조론] 17년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 17년 1회차
다음 인접행렬이 표현하는 그래프의 부분 그래프 중에서 간선(edge)이 최소한 1개 이상인 연결 그래프의 개수는?
[0][1][2][3]
[0]0111
[1]1010
[2]1100
[3]1000
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문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기