일부 가장자리가 고정되어있는 경우 MST에 대한 표준 Kruskal 형 접근 방식이 적용됩니까?

Question

문제 : 그래프의 최소 스패닝 트리 (예 : 그래프에서 가장자리의 집합 S가 각 꼭지점과 함께 S에서 모서리가 트리를 형성 함)를 찾아야하며, 추가적으로 그러한 모든 집합에서 S 내의 모든 에지 비용은 최소가되어야한다). 그러나 잡을 거리가 있습니다. K가 S에 포함되어야하는 고정 된 가장자리 K의 초기 세트가 주어집니다.

즉, 고정 된 가장자리의 시작 세트가 포함 된 그래프의 MST를 찾습니다.

내 접근법 : 표준 Kruskal의 알고리즘이지만 그 전에는 모든 고정 꼭지점을 고정 가장자리 세트로 가리키기 전에 다른 꼭지점을 결합해야합니다. 즉, K = {1,2}, {4,5} Kruskal의 알고리즘을 적용하면 각 개별 노드를 초기에 설정하는 대신 노드 1과 2가 같은 집합에 있고 노드 4와 노드 5가 같은 집합에 속합니다.

질문 : 작동합니까? 이것이 항상 올바른 결과를 산출한다는 증거가 있습니까? 그렇지 않다면 누군가가 반례를 제공 할 수 있습니까?

P. 이 문제는 오직 하나의 MST를 찾는 것만을 요구합니다. 모두에 관심이 없습니다.

Answer 1

예, 가장자리의 초기 집합이주기를 형성하지 않는 한 작동합니다.

고정 된 가장자리가 그래프에서 MST의 일부가 아니기 때문에 결과 트리의 무게가 최소화되지 않을 수 있습니다. 그러나 고정 가장자리가 트리의 일부라는 제약 조건을 충족하는 가장 가벼운 스패닝 트리를 얻을 수 있습니다.

어떻게 그것을 구현 :

이를 구현하려면, 당신은 단순히 당신이 수정해야 가장자리의 에지 가중치를 변경할 수 있습니다. 그래프에서 가장 낮은 가장자리 가중치 (예 : min_w)를 선택하고 1에서 빼고이 새 가중치를 지정하십시오. (min_w-1)을 수정해야하는 가장자리까지 이동합니다. 그런 다음이 그래프에서 Kruskal을 실행하십시오.이

분명히 크루스 칼 그래프에서 다른 가장자리를 따기 전에 (이 이제 가벼운을하기 때문에) 당신이 필요로하는 모든 가장자리를 선택합니다 : 그것이 작동하는 이유

. Kruskal이 끝날 때 가장자리의 결과는 G '(일부 가중치를 변경 한 그래프)의 MST입니다. 고정 된 가장자리 집합의 값만 변경했기 때문에 알고리즘은 다른 가장자리 (고정 된 집합에 포함되지 않은 가장자리)에서 다른 선택을 한 적이 없었을 것입니다.Kruskal이 고려하는 가장자리를 정렬 된 정렬 목록으로 생각하면 수정해야 할 가장자리의 값을 변경하면이 가장자리가 목록의 앞쪽으로 이동하지만 다른 가장자리의 순서는 변경되지 않습니다. 그 목록은 서로에 관한 것입니다.

참고 : 가장자리에 가장 가벼운 무게를주는 것은 기본적으로 제안한 것과 같습니다. 그러나 왜 그것이 효과가 있는지에 대해 추론하기가 더 쉽다고 생각합니다. 원하는 것을 선택하십시오.

---

이 알고리즘은 현재 연결된 구성 요소에서 점차 스패닝 트리를 확장 이후는, 프림 권하고 싶지 않다 (처음 하나는 일반적으로 단일 노드로 시작). 더 큰 구성 요소에 가입하는 경우 (고정 된 모서리가 모두 단일 구성 요소에 있지 않을 수도 있기 때문에) 별도로 처리해야합니다. 어려울 수는 없지만 처리해야합니다. OTOH Kruskal을 사용하면 어떤 알고리즘도 적용 할 필요가 없지만 일반 알고리즘을 실행하기 전에 그래프를 조금만 조작하면됩니다.

Answer 2

결과를 스패닝 트리 (남아있는 격리 된 노드 포함)에서 발생해야하는 가장자리와 정확히 일치하도록 연결된 구성 요소를 초기화 할 수 있으므로 Prim's algorithm이 더 적합합니다. . 원하는 모서리에는 싸이클을 포함 할 수 없으며, 그렇지 않은 경우 해당 싸이클을 포함하는 스패닝 트리가 없습니다.

비용이 최소화 된 방식으로 두 개의 포리스트를 연결하는 가장자리를 찾는 데 사용되는 것으로 명시되어 있으므로 분명히 Kruskal's algorithm을 사용할 수도 있습니다.

대략적으로 말해 주어진 그래프의 숲이 Matroid인데, 그리드 접근법은 시작하는 independent set에 관계없이 원하는 결과 (즉, 최소 무게 트리)를 산출합니다.