정점이 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개인 완전 그래프의 서로 다른 신장 트리 수는 이다.
검산: 간선 6개 중 3개를 고르는 20가지에서 사이클(삼각형)이 되는 4가지를 빼면 16이다.
- 12: 일렬 경로 모양(12개)만 세고 한 정점에 나머지 셋이 붙는 별 모양(4개)을 빠뜨린 값이다.
- 14: 사이클이 되는 조합은 삼각형 4가지뿐이므로 20에서 6을 뺀 이 값은 맞지 않는다.
- 18: 사이클 조합을 2가지만 제외한 셈이 되어 맞지 않는다.
오류나 개정된 내용이 보이면 알려주세요