MST에없는 모서리

Question

이것은 숙제 문제입니다. 나는 해결책을 원하지 않는다. 나는 내가 생각해 왔던 해결책을 제시하고 있으며, 그것이 좋은 것인지 또는 왜 결함이 있는지를 알고 싶어한다.

내 동기 부여는 가중치가 부여되지 않은 무향 그래프의 가장자리가 MST의 일부가 아닌 것을 찾는 것입니다. 이 문제는 여러 가장자리가 동일한 값을 가질 때만 의미가 있습니다. 그렇지 않으면 MST가 고유합니다.

내 생각은 모든 단계에서 S에서 T까지의 최소 에지를 추가하는 대신 (약간의 변경으로 Prim의 알고리즘에서 나온 것입니다.) - 대신 최소 에지 및을 찾습니다. S에서 최소 모서리가가는 정점으로가는 동일한 값의 더 많은 모서리. 그렇게함으로써, MST에 나타나는 모든 가장자리를 포함하는 그래프를 받게됩니다. 이것이 맞다면 MST에없는 에지를 찾기 위해 가장자리 목록을 원본 그래프 가장자리 목록과 XOR하면됩니다. 사전에

감사합니다.

Answer 1

찾을 수있는 모든 가장자리를 추가합니까 (= 동일한 무게의 가장자리)? 그렇다면 다음과 같은 몇 가지 모서리를 잃게됩니다.

동일한 가장자리 비용으로 5 각형을 고려하십시오. 1 개의 노드로 시작하여 2 개의 인접한 노드에 2 개의 가장자리를 추가합니다. 다음 단계에서는 2 개의 인접한 노드에서 2 개의 연결이 끊어진 노드로가는 2 개의 가장자리를 추가하면 완료됩니다. 그러나 모든 에지는 동일한 비용을 가지며 MST에 모두 유효합니다. 마지막 2 개 노드 사이의 가장자리는 알고리즘에 포함되지 않지만 MST의 일부일 수 있습니다.

더욱 악화됩니다. 마지막 모서리의 비용이 더 낮다고 가정합니다. 귀하의 알고리즘은 여전히 ​​그것을 포함하지 않지만 모든 MST에 존재합니다. 모든 가능성을 설명하기 위해 단계 당 여러 가장자리를 추가하고 있지만 가장자리를 추가하면 다음 단계가 변경됩니다.