최소 스패닝 트리

Question

minimum product spanning tree 문제에서 트리 비용은 가중치의 합 대신 트리의 모든 에지 가중치의 결과입니다. 모든 가장자리에 양수가 있다고 가정 할 수 있습니다. 나는 다음 문제에 대한 해답을 얻고 싶다.

(1) 최소 제품 스패닝 트리가 최소 가중치 스패닝 트리와 다른 그래프를 제공하십시오.

(2) 최소의 제품 스패닝 트리를 계산하는 효율적인 알고리즘을 제공하십시오. (힌트 : 로그를 생각해 보라).

Answer 1

최소 제품 스패닝 트리의 문제는 에지 가중치의 로그를 취하여 트리를 변환 한 다음이 수정 된 트리의 MST를 찾는 것으로 해결할 수 있습니다.

대수, log(ab) = log(a) + log(b)의 속성을 기억하십시오. 따라서 최소 스패닝 트리는 최소 비용 스패닝 트리 문제로 변환 될 수 있습니다.