출처 문제는 알고리즘의 소개 의 연습 문제입니다.일부주기에서 최대 가중치 에지를 포함하는 최소 스패닝 트리가 있습니까?
23.1-5 연결된 그래프 G=(V, E)의 일부주기에서 e이 최대 가중치가되도록하십시오. 최소 스패닝 트리가 G'=(V, E - {e})이고 최소 스패닝 트리가 G임을 입증 할 수 있습니다. 즉, e을 포함하지 않는 G의 최소 스패닝 트리가 있습니다. 내가 G의 모든 최소 스패닝 트리가 e이 옳다는 포함되지 않는다는 제안에게 생각 :
문제가 있다는 것입니다. e은 일부주기의 유일한 최대 가중치 에지 인입니다. 그렇지?
업데이트 : 20시 21분
2016년 10월 28일이 e 어떤주기에 하나의 최대 중량 가장자리 이라는 제한을 추가합니다.
하나의 테스트 케이스는 0..n-1이라고 표시된 노드가 있고 노드 i와 노드 (i + 1) mod n (즉, 링) 사이에만 링크가있는 경우입니다. 이 경우 링크 중 하나만 남겨서 최소 스패닝 트리를 만듭니다. e가 고유 한 최대 가중치 인 경우 고유 한 스패닝 트리에 있지 않습니다. 이는 다른 모든 링크입니다. 최대 가중치의 가장자리가 두 개 이상인 경우 최대 가중치의 가장자리가있는 것과 같이 최대 가중치의 다른 가장자리를 벗어나 다른 가중치를 유지하는 것과 같이 여러 가지 최소 스패닝 트리가 있습니다.
최대 무게의 단 하나의 가장자리가있는 경우를 고려하십시오. 누군가가 당신에게이 가장자리를 사용하는 최소 스패닝 트리를 건넨다고 가정합니다. 트리에서 삭제하여 두 개의 연결이 끊긴 구성 요소를 제공합니다. 이제 한 번에 하나씩주기의 다른 가장자리 각각을 추가하십시오. 가장자리가 두 구성 요소를 연결하지 않으면 다시 삭제하십시오. 둘 중 하나의 에지가 두 구성 요소를 연결하는 경우 이전보다 가중치가 작은 스패닝 트리가 있으므로 최소 스패닝 트리가 될 수 없습니다. 가장자리가 두 구성 요소를 연결하지 않는 경우가있을 수 있습니까? 두 구성 요소를 연결하지 않는 모서리를 추가해도 두 구성 요소에서 연결할 수있는 노드 집합이 증가하지 않으므로 두 구성 요소를 연결하는 단일 모서리가없는 경우 모두 동시에 추가하지 않아도됩니다. 그러나 이러한 모든 가장자리를 추가하면 이전 최대 무게 가장자리로 연결된 두 노드를 연결하는 경로가 추가되므로 가장자리 중 하나가 구성 요소를 연결해야합니다. 그래서 원래의 소위 말하는 최소 스패닝 트리가 아니었고 사이클에서 고유 한 최대 가중치를 가진 에지는 최소 스패닝 트리의 일부가 될 수 없었습니다.
이것은 OP의 명제가 일반적으로 사실이 아닌 이유를 보여주는 반례를 제공합니다. 'e'가 일부 사이클에서 고유하지 않은 최대 가중치 에지 인 경우 'e'가 포함 된 MST가있을 수 있습니다. – augurar
@mcdowella, 귀하의 예가 옳습니다. 나는 'e'가 유일한 최대 무게 엣지 **라는 ** 제한을 추가해야한다. 그러면 나의 제안은 옳은가? – loverszhaokai
@mcdowella, 고마워, 나와 같은 생각이야. 나는 어떤 사이클에서 하나 이상의 최대 - 무게 가장자리가있을 수 있다는 조건에주의를 기울이지 않았다. – loverszhaokai