정점이 4개인 무방향(undirected) 완전 그래프(complete… | [7급 국가직 자료구조론] 18년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 18년 1회차
정점이 4개인 무방향(undirected) 완전 그래프(complete graph)에서 만들어질 수 있는 신장 트리(spanning tree)의 총 개수는?
1
12
2
14
3
16
4
18
해설

만들 수 있는 신장 트리의 총 개수는 16이다.

케일리 공식에 따르면 정점이 n개인 완전 그래프의 서로 다른 신장 트리 수는 nn−2n^{n-2}이다.

44−2=42=164^{4-2} = 4^2 = 16
검산: 간선 6개 중 3개를 고르는 20가지에서 사이클(삼각형)이 되는 4가지를 빼면 16이다.

  • 12: 일렬 경로 모양(12개)만 세고 한 정점에 나머지 셋이 붙는 별 모양(4개)을 빠뜨린 값이다.
  • 14: 사이클이 되는 조합은 삼각형 4가지뿐이므로 20에서 6을 뺀 이 값은 맞지 않는다.
  • 18: 사이클 조합을 2가지만 제외한 셈이 되어 맞지 않는다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 18년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기