여기에 두 개의 연결된 무향 그래프 이 동일한 꼭지점 V에 있습니다. 그리고 E1과 E2의 가장자리가 서로 다른 색상을 가지고 있다고 가정합니다.다른 집합에서 최소 스패닝 트리를 찾습니다.
w (e)를 모서리의 너비로합시다. e ∈ E1 ∪ E2.
각 E1 및 E2 집합에 적어도 하나의 가장자리가있는 스패닝 트리 중에서 최소 가중치 스패닝 트리 (MSF)를 찾고 싶습니다. 이 조건에서이 알고리즘을 찾는 방법은 무엇입니까? 나는 여기 밤새 붙어있어.
두 에지 E1 ∈ E1, E2 ∈ E2을 고려한다. 그들은 V에서 2와 4 개의 다른 꼭지점을 연결합니다. 3 개 또는 4 개의 꼭지점을 연결하는 경우 e1이 연결되고 (Kruskal's algorithm의 각 단계와 동일) e2이 연결되는 꼭지점을 계약 한 다음 결과 그래프에서 minimum spanning tree algorithm을 실행한다고 가정합니다. 그 결과는 e1 및 e2을 포함하는 MST입니다.
모든 E1 ∈ E1, E2 (정확히 같은 두 정점을 연결하지 마십시오) ∈ E2에 걸쳐 반복하고 가벼운 솔루션을 찾아 총 MST를 찾을 수 있습니다 다음과 같습니다. 정확성의 증거는 Kruskal's algorithm에서 쉽게 수정할 수 있습니다. E1의 가장 밝은 가장자리 또는 E2의 가장 밝은 가장자리 중 일부 MST에 사용되어야하기 때문에
는 사실,하지만 당신은이보다 효율적으로 할 수 있습니다. E1에서 가장 가벼운 가장자리 e'1이 사용 하지라고하고, e'1에 동의 상처를 고려한다고 가정하자. MST에는 절단 부분을 연결하는 e ≠ e'1이 들어 있어야합니다. 분명히 e ∈ E1 일 경우 e 대신 e'1을 사용할 수 있습니다. 사용할 수없는 전자하지만 ∈ E2, 및 전자 경우, 전자는보다 가벼운 e'1입니다. 이 경우 E2에 대한 인수를 반복하면 E2의 가장 밝은 가장자리가 MST의 일부가 될 수 있습니다. 따라서, 어느 에지 E2 또는 E1의 모든 에지를 따라 E2에서 가장 밝은 에지에 따라 E1의 밝은 에지가 처음 두 수축이 고려되어야
위에서 언급.복잡하다 Θ F는 MST 알고리즘의 복잡성 (| | E1 + E2 F (V, E1 + E2)).