Kruskal의 알고리즘으로 그래프에서 최소 절단을 찾는 것?

Question

우리는 이미 스패닝 트리와 상처가 밀접하게 관련되어 있음을 확인했습니다. 다음은 또 다른 연결입니다. Kruskal 알고리즘이 스패닝 트리에 추가하는 마지막 에지를 제거해 보겠습니다. 이것은 트리를 두 개의 구성 요소로 분리하여 그래프에서 컷 (S, S)을 정의합니다. 이 상처에 대해 우리가 뭐라 할 수 있을까요? 우리가 작업하고있는 그래프가 가중치가 없으며, 그 가장자리가 Kruskal의 알고리즘을 처리하기 위해 무작위로 일정하게 정렬되었다고 가정 해 봅시다. 확률이 적어도 1/n^2 일 때, (S, S)는 그래프의 최소 컷이며, 여기에서 컷 (S, S)의 크기는 S와 S 사이를 횡단하는 엣지의 수입니다 이것은 프로세스 O (n^2) 번을 반복하고 가장 작은 컷을 출력하면 가중치가없는 최소 컷에 대해 O (mn^2 log n) 알고리즘 인 G에서 최소 확률을 얻을 수 있음을 의미합니다. 이 중요한 문제에 대해 가장 빨리 알려진 알고리즘 인 David Karger에 의해 발명 된 O (n^2 log n) 최소 컷 알고리즘이 추가 튜닝됩니다.

• 이 크루스 칼의 알고리즘을 통해 그래프를 처리하는이 독특한 방법은 N^있다는 사실에 의존하지 않는다? 만있는 경우 Kruskal의 알고리즘이 10 개의 노드로 그래프를 처리하는 3 가지 고유 한 방법으로 n^2 번 과정을 반복하면 n^2 개의 고유 한 "마지막 가장자리"가 생성되지 않습니다. n^2 개의 고유 최종 컷 (n^2 고유의 "마지막 엣지"보다 작음)보다 적은 수의 시나리오에서 어떻게 작동합니까?

• 총 n^2 개 미만인 경우? 예를 들어, 알고리즘을 반복하는 횟수에 관계없이 n^2 개의 고유 한 "마지막 모서리"가없는 9 개의 모서리 만있는 10 개의 노드로 연결된 그래프를 가질 수 있습니다. 이 상황에서 어떻게 작동할까요?

• 모든 가장자리를 반복하여 가장자리가 최소 자르기인지 확인하는 것이 더 쉽지 않을까요? n 개의 노드 그래프에서 유일한 고유 에지의 최대 수는 n + 2보다 작은 n + n-1 + n-2 ... + 1 에지입니다. 그리고 n^2가 n^2 log n보다 작다는 것을 고려하면, 왜 이것이 더 빠르기 때문에 모든 에지를 반복하지 않는가?

Answer 1

알고리즘의 작동 방식을 잘못 해석 한 것 같습니다. 알고리즘은 마지막 에지가 추가 될 때까지 Kruskal 알고리즘을 실행 한 다음 바로 그 전에 중지합니다. 알고리즘은 이러한 "마지막 가장자리"컬렉션을 구축하려고하지 않습니다. 대신에, O (n) 개의 가능한 반복을 반복적으로 실행하여 O (n) 가능한 컷을 빌드합니다. 이 후보 삭감들 중에서 가장 낮은 삭감을 취하는 것은 높은 확률로 최소 삭감을 준다. 즉, O (n) 개보다 적은 수의 에지가 있는지 여부는 중요하지 않습니다. 중요한 것은 마지막에 남은 상처이며 마지막으로 고려해야 할 경계는 아닙니다.

희망이 도움이됩니다.