1
비평면 그래프에 최소 스패닝 트리가 있습니까? 나는 prim 알고리즘과 삼각형 부등식에 대해 읽었으며 내 그래프는 삼각형 부등식을 만족하지 못합니까?비평면 그래프에 최소 스패닝 트리가 있습니까?
A
답변
1
프리즘의 알고리즘 here을 읽었을 때, 삼각형 부등식은 한 번 사용되지 않았습니다. 그래서 prim의 알고리즘은 비 메트릭 그래프 (삼각형 부등식을 만족하지 않는 그래프)에도 유효해야합니다. 따라서 연결된 weighted undirected 그래프에 대해 MST를 찾기 위해 prim의 알고리즘을 적용 할 수 있습니다.