역삭제 알고리즘

Reverse-delete algorithm
그래프 및 트리쉬
알고리즘
목록
관련 항목

역삭제 알고리즘은 주어진 연결된 에지 가중 그래프에서 최소 스패닝 트리를 얻기 위해 사용되는 그래프 이론의 알고리즘이다.크루스칼(1956년)에 처음 등장했지만 같은 논문에 등장하는 크루스칼의 알고리즘과 혼동해서는 안 된다.그래프가 분리되면 이 알고리즘은 그래프의 각 분리된 부분에 대한 최소 스패닝 트리를 찾을 것이다.이러한 최소 신장 트리의 집합을 최소 신장 포리스트라고 하는데, 이 포리스트는 그래프에 있는 모든 꼭지점을 포함하고 있다.

이 알고리즘은 탐욕스러운 알고리즘으로 어떤 상황에서든 최선의 선택을 한다.최소한의 스패닝 트리를 찾는 또 다른 욕심 많은 알고리즘인 크러스칼 알고리즘의 역행이다.Kruskal의 알고리즘은 빈 그래프에서 시작하여 에지를 추가하고 Reverse-Delete 알고리즘은 원래 그래프에서 시작하여 에지를 삭제한다.알고리즘은 다음과 같이 동작한다.

  • 가장자리 E 목록을 포함하는 그래프 G로 시작하십시오.
  • 가장자리 무게의 감소 순서로 E를 통과하십시오.
  • 각 에지에 대해 에지를 삭제하면 그래프가 추가로 분리되는지 확인하십시오.
  • 추가 연결을 끊지 않는 삭제 작업을 수행하십시오.

가성음

함수 ReverseDelete(edge[] E)는 감소 순서에 따라 E 정렬됨 색인 i ← 0을 정의하고 i < 크기(E) do 에지 E[i] Delete E[i] delete E[i] 그래프를 연결하지 않으면 E[i] ← 에지 i + 1 반환 에지[] E]를 정의한다.

위 그래프에서 각 에지가 중량을 포함하고 정점이 v1과 v2로 연결된 에지 E의 집합이다.

예

다음 예에서 녹색 가장자리는 알고리즘에 의해 평가되고 있으며 빨간색 가장자리는 삭제되었다.

Reverse Delete 0.svg 이것은 우리의 원본 그래프 입니다.가장자리 근처의 숫자는 가장자리 무게를 나타낸다.
Reverse Delete 1.svg 알고리즘은 최대 가중 에지로 시작되며, 이 경우 에지 중량이 15인 DE이다.엣지 DE를 삭제해도 그래프가 더 이상 분리되지 않기 때문에 삭제된다.
Reverse Delete 2.svg 다음으로 가장 큰 에지는 FG이므로 알고리즘이 이 에지를 삭제하면 그래프가 추가로 분리되는지 여부를 확인할 것이다.가장자리를 삭제해도 그래프가 더 이상 분리되지 않으므로 가장자리는 삭제된다.
Reverse Delete 3.svg 다음으로 가장 큰 에지는 에지 BD이므로 알고리즘이 이 에지를 확인하고 에지를 삭제한다.
Reverse Delete 4.svg 다음 확인할 에지는 에지 EG로, 그래프에서 노드 G를 분리하므로 삭제되지 않는다.따라서 삭제할 다음 에지는 에지 BC이다.
Reverse Delete 5.svg 다음으로 가장 큰 에지는 에지 EF이므로 알고리즘이 이 에지를 확인하고 에지를 삭제한다.
Reverse Delete 6.svg 그런 다음 알고리즘은 나머지 가장자리를 검색하고 삭제할 다른 가장자리를 찾지 못하므로, 이 그래프는 알고리즘에 의해 반환된 최종 그래프다.

러닝타임

알고리즘은 O(E log V (log log V)3 시간(big-O 표기법 사용)으로 실행되도록 나타낼 수 있으며, 여기서 E는 에지 수, V는 정점 수이다.이 바운드는 다음과 같이 달성된다.

  • 비교 정렬을 사용하여 가장자리를 무게로 정렬하는 데는 O(E log E) 시간이 소요되며, 가장 큰 E가 V라는2 사실을 사용하여 O(E log V)로 단순화할 수 있다.
  • 루프의 반복이 있다.
  • 에지 삭제, 결과 그래프의 연결성 확인, (분리된 경우) 에지 재삽입은 작업당 O(logV(log log V)3 시간(Thorup 2000)으로 할 수 있다.

정확성 증명

먼저 크러스칼의 알고리즘의 교정쇄를 읽는 것이 좋다.

그 증거는 두 부분으로 구성되어 있다.첫째, 알고리즘을 적용한 후 남는 가장자리가 스패닝 트리를 형성한다는 것이 증명된다.둘째, 스패닝 트리가 최소한의 무게라는 것이 증명된다.

스패닝 트리

알고리즘이 라인 7에서 그것을 확인하기 때문에 알고리즘에 의해 생성된 나머지 서브그래프(g)는 분리되지 않는다.결과 하위 그래프에는 주기가 포함될 수 없는데, 이는 가장자리를 따라 이동할 때 주기에서 최대 가장자리를 만나게 되고 우리는 그 가장자리를 삭제하게 되기 때문이다.따라서 g는 주 그래프 G의 스패닝 트리여야 한다.

미니멀리티

다음 명제 P가 유도에 의해 참임을 나타낸다.F가 while 루프 끝에 남아 있는 가장자리 집합인 경우, (가장자리)가 F의 하위 집합인 일부 최소 신장 트리가 있다.

  1. 분명히 P는 while loop의 시작 전에 잡는다. 가중 연결된 그래프는 항상 최소 스패닝 트리를 가지고 있고 F는 그래프의 모든 가장자리를 포함하므로 이 최소 스패닝 트리는 F의 하위 집합이어야 한다.
  2. 이제 일부 비최종 에지 집합 F에 대해 P가 참이라고 가정하고 T를 F에 포함된 최소 신장 트리가 되도록 한다. 알고리즘에서 에지 e를 삭제한 후 F의 하위 집합인 일부(아마도 다른) 신장 트리 T'가 존재한다는 것을 보여 주어야 한다.
    1. 다음에 삭제된 에지 e가 T에 속하지 않으면 T=T'는 F와 P hold의 하위 집합이다.
    2. 그렇지 않으면 e가 T:에 속할 경우, 먼저 알고리즘이 F.에서 분리를 일으키지 않는 가장자리만 제거하므로 e가 분리를 일으키지 않는다는 점에 유의하십시오.그러나 e를 삭제하면 트리 T에 연결이 끊긴다(T의 멤버이기 때문이다). e가 T를 하위 그래프 t1과 t2로 구분한다고 가정한다.전체 그래프는 e를 삭제한 후 연결되므로 t1과 t2(e를 제외한) 사이에 경로가 존재해야 하므로 (e를 제거하기 전에) F에 사이클 C가 존재해야 한다.이제 우리는 이 사이클에서 T에 있지 않지만 F에 있는 또 다른 에지를 가져야 한다(모든 사이클 에지가 T에 있다면 그것은 더 이상 나무가 아닐 것이기 때문이다).현재 우리는 T' = T - e + f가 F의 하위 집합인 최소 신장 트리라고 주장한다.
    3. 첫째로 우리는 T'가 스패닝 트리라는 것을 증명한다. 우리는 나무의 가장자리를 삭제하고 순환을 일으키지 않는 다른 가장자리를 추가함으로써 우리는 같은 정점을 가진 다른 나무를 얻게 된다.T는 스패닝 트리였기 때문에 T'도 스패닝 트리임에 틀림없다.f "를 추가하면 "e"가 제거되므로 어떤 사이클도 발생하지 않는다.(트리 T에는 그래프의 모든 정점이 포함되어 있다는 점에 유의하십시오.)
    4. 둘째로 우리는 T'가 최소 신장 트리라는 것을 증명한다. 우리는 가장자리 "e"와 "f "wt"에 대한 세 가지 사례가 있다. wt는 무게 함수다.
      1. wt(f ) < wt(e ) 이것은 T'의 무게가 T보다 엄격히 적기 때문에 불가능하다. T는 최소 스패닝 트리이기 때문에, 이것은 단순히 불가능하다.
      2. wt(f ) > wt(e ) 이 또한 불가능하다.그 이후로 우리가 가장자리 무게의 감소 순서에서 가장자리를 통과할 때 우리는 "f"를 먼저 보아야 한다. 왜냐하면 우리는 주기 C를 가지고 있기 때문에 "f"를 제거하면 F에서 어떤 연결이 끊어지지 않기 때문이다. 그래서 알고리즘은 F에서 그것을 더 일찍 제거했을 것이다. 따라서 "f"는 불가능한 F에 존재하지 않는다. (우리는 f가 4단계에 존재한다는 것을 증명했다.)
      3. so wt(f) = wt(e) 따라서 T'도 최소 스패닝 트리다.그래서 다시 P가 붙는다.
  3. 그래서 P는 while loop이 끝났을 때(우리가 모든 가장자리를 보았을 때), 그리고 우리는 끝에서 F가 스패닝 트리가 된다는 것을 증명했고 우리는 F가 그것의 부분집합으로 최소 스패닝 트리를 가지고 있다는 것을 안다. 그래서 F는 그 자체로 최소 스패닝 트리 그 자체여야 한다.

참고 항목

참조

  • Kleinberg, Jon; Tardos, Éva (2006), Algorithm Design, New York: Pearson Education, Inc..
  • Kruskal, Joseph B. (1956), "On the shortest spanning subtree of a graph and the traveling salesman problem", Proceedings of the American Mathematical Society, 7 (1): 48–50, doi:10.2307/2033241, JSTOR 2033241.
  • Thorup, Mikkel (2000), "Near-optimal fully-dynamic graph connectivity", Proc. 32nd ACM Symposium on Theory of Computing, pp. 343–350, doi:10.1145/335305.335345.