최소 스패닝 트리에 대한 기본적인 질문

Question

이것은 숙제가 아닙니다. 나는 MST (minimum spanning tree)을 이해하기 위해 교과서에서 운동을하려고합니다.

가중치가있는 무향 그래프 G에주기가 있다고 가정합니다. 내가 알고있는 것처럼, 다음은 올바른 : C의 무거운 가장자리 G없이 MST 에 속하는

• . 즉, 해당 가장자리가 포함 된 MST가 G입니다.
• 는 C의 가벼운 가장자리 G의 일부 MST를 에 속한다. 즉, 그 가장자리를 포함하는 G의 MST가 있습니다.

이제 다음 주장이 정확한지 궁금합니다.

• 는 는 가벼운 C에 가장자리 G의 모든 MST 에 속한다. 즉, MST가 G이고 해당 가장자리가 포함되어 있지 않습니다.
• 가장 무거운 하나를 제외한 C의 모든 가장자리는 일부 MST에 속합니다. 즉, 중 가장 두꺼운을 제외한 C의 각 에지에는 해당 에지가 포함 된 MST가 있습니다.

마지막 소유권을 증명할 수 있습니까?

Answer 1

가장 가벼운 가장자리가 여러 개인 경우 첫 번째 주장 인 경우에도 MST에 모두 포함 할 필요가 없습니다.

Answer 2

귀하의 주장 중 첫 번째 주장은 항상 사실입니다. 가장 가벼운 가장자리는 모든 그래프의 MST에 있습니다.

두 번째 것은 항상 사실이 아닙니다. 전체 그래프가 주기이므로 모든 노드에 2 개의 에지가 발생하면 항상 참입니다. 총 무게보다 k에서 그들을 연결하는 노드 u와 v 사이의 경로가있을 때마다 그러나, 일반적인 경우에, 무게 k의 가장자리 (u,v)는 MST에 결코 없다.

Answer 3

귀하의 주장이 유효하다고 생각하지 않습니다. 문제는 더 큰 그래프의 사이클을 고려하고 있다는 것입니다.

예를 들어 한주기에 6 개의 노드로 구성된 그래프 G (임의의 가중치> 1)를 고려하십시오. 그래프에 대한 소유권 주장은 그래프의 중앙에 1 개의 노드를 추가하고 비용 1의 6 개의 링크로 연결합니다. 전체 그래프의 MST는 이제 6 개의 가장자리 (별을 형성 함)로만 구성됩니다.당신은 지금 당신의 주장을 보면

, 당신은 볼 수 있습니다 :

이

• 당신의주기에서 가장 가벼운 가장자리가 MST (= 스타)주기에서 가장자리의
• 아무도 없습니다에 속하지 않는 MST에서