연결된 무방향 그래프가 주어졌을 때,이 그래프의 최소 신장 트리(Minimum Spanning Tree, 이하 MST) 가 유일한지를 판별하시오.

신장 트리는 다음과 같이 정의한다

- 연결된, 무방향그래프 G = (V, E)가 있다. 여기서 V는 모든 정점의 집합, E는 모든 간선의 집합을 뜻한다. - G의 신장 트리는 G의 부분그래프로서, 다음과 같은 특성을 따르는 T = (V', E')라 칭한다.

1. V' = V. 2. T는 연결되어 있고 싸이클이 없다.

MST는 다음과 같이 정의한다.

간선의 가중치가 있는 연결된 무방향그래프 G = (V, E)를 생각해보자.

G의 최소 스패닝 트리 T = (V, E')는 가중치의 합이 가장 작은 스패닝트리이다.

T의 가중치의 합이란 모든 간선 E'의 가중치를 더한 값을 의미한다.

uniqueMST timer 1s memory 256MB

uniqueMST 1s 256MB