예상 선형 시간 MST 알고리즘

예상되는 선형 시간 MST 알고리즘은 분리된 정점이 없는 가중 그래프의 최소 스패닝 포레스트를 계산하기 위한 랜덤화 알고리즘입니다.그것은 데이비드 카거, 필립 클라인, 그리고 로버트 타잔에 ^[1]의해 개발되었다.이 알고리즘은 선형 ^[2]^[3]시간 내에 최소 스패닝트리를 검증하는 알고리즘과 함께 Bor'vka 알고리즘의 기술에 의존합니다.분할 및 정복 알고리즘, 탐욕 알고리즘 및 랜덤화 알고리즘의 설계 패러다임을 결합하여 기대되는 선형 성능을 달성합니다.

최소 스패닝 트리를 찾는 결정론적 알고리즘에는 Prim 알고리즘, Kruskal 알고리즘, 역삭제 알고리즘 및 Borvvka 알고리즘이 있습니다.

개요

알고리즘의 주요 통찰력은 랜덤 샘플링 단계로, 각 서브그래프에 포함할 가장자리를 랜덤하게 선택하여 그래프를 두 개의 서브그래프로 분할합니다.이 알고리즘은 첫 번째 서브문제의 최소 스패닝포레스트를 재귀적으로 찾아 선형 시간 검증 알고리즘과 함께 솔루션을 사용하여 최소 스패닝트리에 포함되지 않는 그래프 내의 에지를 폐기합니다.각 재귀 시 그래프의 크기를 줄이기 위해 Borvvka 알고리즘에서 가져온 절차도 사용됩니다.

Borkavka

알고리즘의 각 반복은 Borvvka 스텝이라고 불리는 Borvvka 알고리즘의 적응에 의존합니다.

입력: 격리된 정점이 없는 그래프 G 각 정점 v'에 대해 v2에서 가장 가벼운 가장자리를 선택합니다. 1단계에서 선택한 가장자리에 의해 연결된 G의 각 구성요소를 단일 정점 3으로 대체하여 축소된 그래프 G'를 만듭니다. 모든 격리된 정점, 셀프 루프 및 최소가 아닌 반복 가장자리를 G' 출력에서 제거합니다.1단계에서 선택한 모서리와 축소 그래프 G'

Borvvka 스텝은 Bor)vka 알고리즘의 내부 루프와 동등합니다.이 알고리즘은 O(m) 시간으로 실행됩니다.m은 G의 에지 수입니다.또한 각 가장자리는 최대 2회(각 입사 정점별로 1회) 선택할 수 있으므로 1단계 이후 절단된 구성요소의 최대 수는 정점 수의 절반과 같습니다.따라서 Borůvka 스텝은 그래프 내의 정점 수를 2배 이상 줄이고 n/2개 이상의 에지를 삭제합니다.여기서 n은 G의 정점 수입니다.

Borvvka 스텝의 실행 예

이미지	묘사
	각 정점의 가장 가벼운 모서리 인시던트는 녹색으로 강조 표시됩니다.
	그래프가 축소되고 1단계에서 선택한 모서리로 연결된 각 구성요소가 단일 정점으로 대체됩니다.이것에 의해, 2개의 슈퍼 노드가 작성됩니다.원래 그래프의 모든 모서리가 유지됩니다.
	슈퍼노드에 대한 셀프루프를 형성하는 에지는 삭제됩니다.
	슈퍼노드 간의 최소가 아닌 용장 에지가 삭제됩니다.
	샘플 그래프에서 하나의 Borůvka Step의 결과는 두 개의 슈퍼노드가 단일 에지로 연결된 그래프입니다.

F-Heavy 및 F-Light 가장자리

각 반복에서 알고리즘은 최소 스패닝트리에서 제외되는 특정 속성을 가진 에지를 삭제합니다.이를 F-헤비 에지라고 하며 다음과 같이 정의됩니다.F를 그래프 H의 포레스트로 합니다.F-heavy edge는 F의 u에서 v로의 경로에서 가장 무거운 edge의 무게보다 무게가 엄밀하게 큰 꼭지점 u,v를 연결하는 edge e입니다(F에 경로가 존재하지 않으면 무한 가중치를 갖는 것으로 간주됩니다).F-Heavy가 아닌 엣지는 F-라이트입니다.F가 G의 서브그래프일 경우 G의 F-heavy edge는 사이클 특성에 의해 G의 최소 스패닝 트리에 포함될 수 없습니다.포레스트를 지정하면 최소 스패닝트리 검증 알고리즘을 사용하여 F 헤비 ^[2]^[3]에지를 선형 시간으로 계산할 수 있습니다.

알고리즘.

입력: 분리된 정점이 없는 그래프 G

G가 비어 있으면 빈 포리스트를 반환합니다.
G에서 두 개의 연속된 Borvvka 단계를 실행하여 축소 그래프 G'를 만듭니다.
G'의 각 모서리를 1/2 확률로 선택하여 하위 그래프 H를 만듭니다.알고리즘을 H에 재귀적으로 적용하여 최소 스패닝 포레스트 F를 얻습니다.
선형 시간 최소 스패닝 트리 검증 ^[2]^[3]알고리즘을 사용하여 G'(여기서 F는 3단계 포레스트)에서 F-헤비 에지를 모두 제거합니다.
알고리즘을 G'에 재귀적으로 적용하여 최소 스패닝 포리스트를 얻습니다.

출력: G'의 최소 스패닝 포레스트와 Borvvka 스텝의 축소 에지

정확성

그래프의 꼭지점 수에 대한 유도로 정확성을 입증합니다.그 근거는 확실히 사실이다.T*를 G의 최소 스패닝 트리로 합니다.Borvvka 스텝에서 선택한 모든 에지는 절단 속성에 의해 T*에 있으며 축소 그래프를 형성하기 위해 제거된 에지는 절단 속성(용장 에지) 및 사이클 속성(셀프 루프)에 의해 T*에 없습니다.스텝 2에서 선택되지 않은 T*의 나머지 가장자리는 절단 특성에 의해 축소된 그래프의 최소 스패닝 트리를 형성합니다(각 절단은 슈퍼노드로 합니다).삭제되는 F 헤비 엣지는 사이클 속성에 의해 최소 스패닝트리에 포함되지 않습니다.마지막으로 F'는 유도 가설에 의한 축소 그래프의 최소 스패닝 트리이다.따라서 F'와 Borvvka 스텝에서 수축된 가장자리는 최소 스패닝 트리를 형성합니다.

성능

예상되는 성능은 랜덤 샘플링 단계의 결과입니다.랜덤 샘플링 단계의 효과는 G의 F-라이트 에지 수에 경계를 설정하여 두 번째 하위 문제의 크기를 제한하는 다음과 같은 약어로 설명된다.

랜덤 샘플링 규칙

Lema- H를 확률 p로 G의 각 모서리를 독립적으로 포함시켜 형성된 G의 서브그래프로 하고 F를 H의 최소 스패닝 포레스트로 한다.G에서 예상되는 F-라이트 에지 수는 최대 np입니다. 여기서 n은 G의 정점 수입니다.

보조항목을 증명하기 위해 H에 추가되는 G의 가장자리를 조사합니다.G의 F-라이트 엣지 수는 H의 최소 스패닝 포레스트가 모든 선택 순서에서 동일하기 때문에 H의 엣지가 선택되는 순서와는 무관합니다.증빙을 위해 가장 가벼운 것부터 무거운 것 순으로 G의 가장자리를 한 번에 하나씩 취함으로써 H의 가장자리를 선택하는 것을 고려합니다.e를 고려 중인 전류 에지로 합니다.e의 끝점이 두 개의 분리된 H 구성요소에 있는 경우, e는 이러한 구성요소를 연결하는 가장 가벼운 가장자리이며, H에 추가되면 절단 특성에 의해 F가 됩니다.이는 또한 e가 H에 추가되는지 여부에 관계없이 F-라이트임을 의미하며, 이는 이후에 더 무거운 가장자리만 고려되기 때문이다.e의 양쪽 끝점이 H의 동일한 성분 내에 있는 경우, e는 사이클 특성에 의해 F-heavy(그리고 항상 F-heavy)입니다.그런 다음 에지 e를 확률 p로 H에 추가합니다.

H의 최소 스패닝트리가 n-1 에지를 가지기 때문에 H에 추가되는 F 라이트엣지의 최대 수는 n-1 입니다.n-1 F-라이트 에지가 H에 추가되면 이후 고려되는 에지는 사이클 특성에 의해 F-라이트 되지 않습니다.따라서 G의 F-라이트 에지 수는 실제로 N-1 F-라이트 에지가 H에 추가되기 전에 H에 대해 고려된 F-라이트 에지 수에 의해 제한된다. F-라이트 에지에는 확률 p가 추가되므로 이는 n-1 헤드가 나타날 때까지 p가 나올 확률로 동전을 뒤집는 것과 같다.코인 플립의 총 횟수는 G의 F-라이트 에지 횟수와 같다.동전 던지기 횟수의 분포는 모수 n-1과 p를 사용한 역이항 분포로 제공됩니다.이러한 모수의 경우 이 분포의 예상 값은 (n-1)/p입니다.

예상 분석

재귀 하위 문제에서 수행된 작업을 무시하면 알고리즘의 단일 호출로 수행된 작업의 총량은 입력 그래프의 에지 수에 선형입니다.스텝 1에는 일정한 시간이 걸립니다.Borvvka 스텝은 Borvvka 스텝 섹션에 기재된 에지 수로 시간 선형으로 실행할 수 있다.3단계는 모서리를 반복하여 각 모서리마다 동전을 하나씩 던져서 모서리 수를 선형으로 만듭니다.스텝 4는 변경된 선형 시간 최소 스패닝 트리 검증 ^[2]^[3]알고리즘을 사용하여 선형 시간으로 실행할 수 있습니다.알고리즘의 1회 반복에서 수행된 작업은 에지 수에 선형이기 때문에 알고리즘의 1회 완료 실행에서 수행된 작업(모든 재귀 호출 포함)은 원래 문제 및 모든 재귀 하위 문제의 총 에지 수에 곱한 상수 인수로 제한됩니다.

알고리즘의 각 호출은 최대 2개의 하위 문제를 생성하므로 하위 문제 집합은 이진 트리를 형성합니다.각 Borvvka 스텝은 정점 수를 최소 2배 감소시키기 때문에 2개의 Bor stepsvka 스텝 후에 정점 수는 4배 감소했습니다.따라서 원본 그래프에 n개의 정점과 m개의 가장자리가 있는 경우 각 하위 문제는 최대 n/4개의^d 정점의 그래프에 있습니다.또한 트리는 최대 logn₄ 수준을 가집니다.

이진 트리의 왼쪽 경로는 파란색 동그라미로 표시됩니다.

재귀 트리에 대해 추론하려면 스텝3의 재귀 콜에서 왼쪽 자녀 문제를 서브 문제로 하고 스텝5의 재귀 콜에서 오른쪽 자녀 문제를 서브 문제로 합니다.트리의 각 왼쪽 경로에 있는 에지 수를 세어 원래 문제와 모든 하위 문제의 총 에지 수를 세십시오.왼쪽 경로는 오른쪽 자식 또는 루트 중 하나에서 시작되며 왼쪽 자식 경로를 통해 도달할 수 있는 모든 노드를 포함합니다.바이너리 트리의 왼쪽 경로는 오른쪽 다이어그램에 파란색 동그라미로 표시됩니다.

왼쪽 자녀 문제의 각 에지는 부모 문제의 가장자리(Borvvka 단계에서 축소된 가장자리보다 작음)에서 확률 1/2로 선택됩니다.부모 문제의 가장자리가 x개인 경우 왼쪽 자식 문제의 예상 가장자리 수는 최대 x/2개입니다.x가 랜덤 변수 X로 대체된 경우, 왼쪽 자식 문제 Y의 예상 에지 수는 E $E[Y]\leq E[X]/2$ [ $E[Y]\leq E[X]/2$ ] $E[Y]\leq E[X]/2$ E [ $E[Y]\leq E[X]/2$ / $E[Y]\leq E[X]/2$ ( \ $displaystyle$ E [ Y $E[Y]\leq E[X]/2$ ] \ $leq E$ [ X $E[Y]\leq E[X]/2$ ] / $2)$ 로 표시됩니다.따라서 경로 상단의 문제에서 예상되는 에지 수는 예상 경로 k의 합계입니다.왼쪽 경로의 b 문제는 최대 θ $\sum _{d=0}^{\infty }{\frac {k}{2^{d}}}=2k$ $\sum _{d=0}^{\infty }{\frac {k}{2^{d}}}=2k$ $\sum _{d=0}^{\infty }{\frac {k}{2^{d}}}=2k$ $\sum _{d=0}^{\infty }{\frac {k}{2^{d}}}=2k$ $\sum _{d=0}^{\infty }{\frac {k}{2^{d}}}=2k$ $\sum _{d=0}^{\infty }{\frac {k}{2^{d}}}=2k$ d $\sum _{d=0}^{\infty }{\frac {k}{2^{d}}}=2k$ $\sum _{d=0}^{\infty }{\frac {k}{2^{d}}}=2k$ k ${\displaystyle \sum$ _ ${d=0}^{\infty}{\frac {k}{2^{d$ }}}= $2k}$ 이다(기하 급수 참조).루트는 m개의 에지를 가지므로 예상되는 에지 수는 각 오른쪽 하위 문제에서 예상되는 에지 수의 2배와 같습니다.

각 오른쪽 서브문제의 예상되는 에지 수는 부모문제의 F-라이트 에지 수와 동일합니다.F는 왼쪽 서브문제의 최소 스패닝트리입니다F-라이트 에지 수가 샘플링 보조법에 의한 하위 문제의 정점 수의 두 배보다 작거나 같습니다.깊이 d에 있는 하위 문제의 정점 수는 n/4이므로^d $\sum _{d=1}^{\infty }{\frac {2^{d-1}n}{4^{d}}}=n/2$ 오른쪽 하위 문제의 정점 수는 θ d $\sum _{d=1}^{\infty }{\frac {2^{d-1}n}{4^{d}}}=n/2$ $\sum _{d=1}^{\infty }{\frac {2^{d-1}n}{4^{d}}}=n/2$ † 2 $\sum _{d=1}^{\infty }{\frac {2^{d-1}n}{4^{d}}}=n/2$ - $\sum _{d=1}^{\infty }{\frac {2^{d-1}n}{4^{d}}}=n/2$ $\sum _{d=1}^{\infty }{\frac {2^{d-1}n}{4^{d}}}=n/2$ $\sum _{d=1}^{\infty }{\frac {2^{d-1}n}{4^{d}}}=n/2$ d $n$ / $\sum _{d=1}^{\infty }{\frac {2^{d-1}n}{4^{d}}}=n/2$ ({ $displaystyle \sum$ _ { $d=1}^{\infty$ } {\ $frac {2^{d-1}{4^{d}}}}/2$ 로 지정됩니다. 따라서 기대됩니다.m+n. 고립된 정점이 없는 그래프의 경우 최대 2m이므로 알고리즘은 예상 시간 O(m)에 실행됩니다.

최악의 경우 분석

최악의 경우 런타임은 Borvvka 알고리즘 런타임과 동일합니다.이 문제는 호출할 때마다 왼쪽 또는 오른쪽 하위 문제에 모든 에지가 추가된 경우에 발생합니다.이 경우 알고리즘은 N개의 정점과 m개의 모서리를 가진 그래프에서 O(min{n², mlogn})로 실행되는 Borkavka 알고리즘과 동일합니다.

레퍼런스

^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995). "A randomized linear-time algorithm to find minimum spanning trees". Journal of the ACM. 42 (2): 321. CiteSeerX 10.1.1.39.9012. doi:10.1145/201019.201022.
^ ^a ^b ^c ^d Dixon, Brandon; Rauch, Monika; Tarjan, Robert E. (1992). "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time". SIAM Journal on Computing. 21 (6): 1184. CiteSeerX 10.1.1.49.25. doi:10.1137/0221070.
^ ^a ^b ^c ^d King, Valerie (1995). A Simpler Minimum Spanning Tree Verification Algorithm. Proceedings of the 4th International Workshop on Algorithms and Data Structures. London, UK, UK: Springer-Verlag. pp. 440–448.

추가 정보

선형 시간에서의 최소 스패닝트리 검증

[1] Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995). "A randomized linear-time algorithm to find minimum spanning trees". Journal of the ACM. 42 (2): 321. CiteSeerX 10.1.1.39.9012. doi:10.1145/201019.201022.

[MST-V1-2] Dixon, Brandon; Rauch, Monika; Tarjan, Robert E. (1992). "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time". SIAM Journal on Computing. 21 (6): 1184. CiteSeerX 10.1.1.49.25. doi:10.1137/0221070.

[MST-V2-3] King, Valerie (1995). A Simpler Minimum Spanning Tree Verification Algorithm. Proceedings of the 4th International Workshop on Algorithms and Data Structures. London, UK, UK: Springer-Verlag. pp. 440–448.

[1]

[2]

[3]

Search