전체 그래프의 최소 스패닝 트리 (MST) 수

Question

N 개의 꼭지점이있는 전체 그래프의 최소 스패닝 트리 (MST)의 최소 수는 얼마입니까?

Answer 1

답변은 입니다.

정확하게 하나의 MST가있는 n 개의 노드로 완전한 그래프를 구성 할 수 있습니다. 이를 위해 1, 2, 3, ..., n으로 레이블 된 n 개의 노드로 그래프를 구성하십시오. 그런 다음 1에서 2, 2에서 3, 3에서 4, ..., n - 1에서 n까지 비용 0의 가장자리를 추가하고 비용 1 인 다른 모든 노드 쌍을 연결하는 가장자리를 추가합니다. 모든 제로 - 비용 에지를 선택하면이 그래프의 스패닝 트리 하나가 가능하며 다른 스패닝 트리를 선택한 경우 비용은 최소 1이됩니다. 또한이 값은 그래프의 유일한 MST입니다 그 비용은 0입니다. 다른 세트의 에지가 선택되면 적어도 하나의 가장자리가 적어도 1 개 포함되어야하므로 총 MST는 적어도 1이되어야합니다.

희망이 있습니다.