최소 스패닝 트리

평면 그래프 및 해당 최소 신장 트리. 각 가장자리에는 무게 라벨이 붙어 있는데, 여기서 무게는 대략 길이에 비례한다.

최소 스패닝 트리(MST) 또는 최소 중량 스패닝 트리는 모든 정점을 사이클 없이 가능한 최소 총 에지 중량으로 함께 연결하는 연결된 에지 가중치 비방향 그래프의 가장자리 부분 집합이다.^[1] 즉, 가장자리 무게의 합이 가능한 한 작은 신장 나무다.^[2] 보다 일반적으로, 모든 에지 가중치 비방향 그래프(필수적으로 연결된 것은 아님)는 최소 스패닝 포리스트를 가지고 있는데, 이는 연결된 구성 요소에 대한 최소 스패닝 트리의 조합이다.

최소 스패닝 트리에는 많은 사용 사례가 있다. 한 예로 통신 회사가 새로운 지역에 케이블을 설치하려고 애쓰는 것이 있다. 케이블이 특정 경로(예: 도로)를 따라만 매립하도록 제한되는 경우, 해당 경로로 연결된 지점(예: 집)을 포함하는 그래프가 있을 것이다. 일부 경로는 더 길거나 케이블을 더 깊이 묻어야 하기 때문에 더 비쌀 수 있다. 이러한 경로는 더 큰 중량을 가진 가장자리로 표현될 수 있다. 통화는 가장자리 무게에 대해 허용되는 단위로서 삼각형 불평등과 같은 일반적인 기하학적 규칙을 준수하는 가장자리 길이가 필요하지 않다. 그 그래프의 스패닝 트리는 사이클은 없지만 여전히 모든 집을 연결하는 그러한 경로의 하위 집합일 것이다. 가능한 스패닝 트리가 여러 개 있을 수 있다. 최소 스패닝 트리는 최소 총 비용이 가장 낮은 트리로, 케이블을 놓기 위한 가장 저렴한 경로를 나타낸다.

특성.

가능한 다중성

그래프에 정점이 $없으면$ 각 스패닝 트리에는 $가장자리$ 가 n - $1개$ 있다.

이 그림은 그래프에 최소 하나 이상의 스패닝 트리가 있을 수 있음을 보여준다. 그림에서 그래프 아래의 두 트리는 주어진 그래프의 최소 신장 트리의 두 가지 가능성이다.

같은 중량의 최소 스패닝 트리가 여러 개 있을 수 있다. 특히, 주어진 그래프의 모든 에지 무게가 동일하다면, 해당 그래프의 모든 스패닝 트리는 최소가 된다.

유니크함

각 가장자리의 중량이 구별되면 고유한 최소 스패닝 트리가 하나만 있을 것이다. 이는 위의 통신 회사 사례와 같이 두 경로가 정확히 동일한 비용을 가질 가능성이 낮은 많은 현실적인 상황에서 사실이다. 이것은 숲을 가로지르는 것으로도 일반화된다.

증명:

반대로 MST A와 B가 서로 다른 두 개의 MST가 있다고 가정한다.
A와 B는 같은 노드를 포함했음에도 불구하고 다르기 때문에 한 에지에 속하지만 다른 에지는 아닌 에지가 하나 이상 존재한다. 그러한 가장자리 중에서 e를₁ 가장 작은 무게로 두어라; 이 선택은 가장자리 무게가 모두 구별되기 때문에 독특하다. 일반성을 잃지 않고 e가₁ A에 있다고 가정한다.
B는 MST이므로 {e₁} $\cup$ $\cup$ 는 $\cup$ e가₁ 포함된 사이클 C를 포함해야 한다.
나무로서 A에는 주기가 없으므로 C에는 A에 없는 에지 e가₂ 있어야 한다.
정확히₁ A와 B 중 하나에 속하는 것 중에서 e가 고유한 가장 낮은 무게의 가장자리로 선택되었기 때문에 e의₂ 무게는₁ e의 무게보다 커야 한다.
e와₁ e가₂ 사이클 C의 일부인 만큼, e를₂ B에서₁ e로 대체하면 더 작은 무게의 스패닝 트리가 생성된다.
이것은 B가 MST라는 가정과 모순된다.

보다 일반적으로, 가장자리 무게가 모두 구별되지 않는 경우, 최소 신장 나무에서 (다중) 무게 집합만 고유할 것이 확실하다; 그것은 모든 최소 신장 나무에서 동일하다.^[3]

최소비용 하위그래프

만약 무게가 양수라면, 사이클을 포함하는 서브그래프는 반드시 더 많은 총중량을 가지기 때문에, 최소 스패닝 트리는 사실 모든 정점을 연결하는 최소비용 서브그래프다.^{[citation needed]}

사이클 속성

그래프에서 어떤 사이클 $C$ 의 경우, $C$ 의 에지 $e$ 의 무게가 $C$ 의 다른 모든 에지의 개별 가중치보다 크면, 이 에지는 MST에 속할 수 없다.

증거: 반대라고 가정하십시오. 즉, $e$ 가 MST $T$ 에₁ 속한다고 가정하십시오. 그런 다음 $e$ 를 삭제하면 $T$ 가₁ 서로 다른 하위 트리에서 $e$ 의 두 끝과 함께 두 하위 트리로 분할된다. $C$ 의 나머지 부분은 하위 트리를 다시 연결하므로, 다른 하위 트리로 끝나는 $C$ 의 가장자리 $f$ 가 있다. 즉, $f$ 의 무게가 $e$ 의 무게보다 작기 때문에 하위 트리를 $T$ 의₁ 무게보다 작은 트리 $T$ 에₂ 다시 연결한다.

절단 특성

이 수치는 MST의 컷 속성을 보여준다. T는 주어진 그래프의 유일한 MST이다. S = {A,B,D,E}, 따라서 V-S = {C,F}, 컷(S,V-S)에 걸쳐 가장자리의 세 가지 가능성이 있는 경우, 원래 그래프의 가장자리 BC, EC, EF가 된다. 그런 다음, e는 절단을 위한 최소 중량 에지 중 하나이므로 S ∪ {e}은(는) MST T의 일부분이다.

그래프의 모든 절단 C에 대해, C의 절단 세트에 있는 에지 e의 무게가 C의 절단 세트에 있는 다른 모든 에지의 무게보다 엄격히 작다면, 이 에지는 그래프의 모든 MST에 속한다.

증명: e를 포함하지 않는 MST T가 있다고 가정한다. T에 e를 추가하면 e에서 한 번 절단을 교차하고 다른 가장자리 e'에서 다시 교차하는 사이클이 생성된다. e'를 삭제하면 T보다 완전히 작은 중량의 스패닝 트리 T∖{e'}∪{e}를 얻게 된다. 이것은 T가 MST였다는 가정과 모순된다.

유사한 논거에 의해, 둘 이상의 가장자리가 절단된 부분 전체에 걸쳐 최소 무게인 경우, 그러한 각 가장자리는 어떤 최소 신장 트리에 포함된다.

최소 비용 에지

그래프의 최소 비용 에지 e가 고유하면 이 에지는 모든 MST에 포함된다.

증명: e가 MST에 포함되지 않은 경우, MST에 e를 추가한 후 형성된 사이클에서 (더 큰 비용) 가장자리를 제거하면 더 작은 중량의 스패닝 트리가 생성될 것이다.

수축

T가 MST 가장자리의 나무라면 수축하기 전에 수축된 그래프 플러스 T의 MST가 그래프에 MST를 주는 불변성을 유지하면서 T를 하나의 꼭지점으로 수축시킬 수 있다.^[4]

알고리즘

아래의 모든 알고리즘에서 m은 그래프에서 가장자리 수, n은 꼭지점 수입니다.

고전 알고리즘

최소 신장 트리를 찾기 위한 첫 번째 알고리즘은 1926년 체코 과학자 오타카르 보르체브카에 의해 개발되었다(보르체브카의 알고리즘 참조). 그것의 목적은 모라비아의 효율적인 전기 커버리지였다. 알고리즘은 일련의 단계로 진행된다. Boruvka step이라고 불리는 각 단계에서 그래프 G의 각 꼭지점에 대한 최소 중량 에지 사건으로 구성된 F숲을 식별한 후, 다음 단계의 입력으로 $G_{1}=G\setminus F$ G $G_{1}=G\setminus F$ = $G_{1}=G\setminus F$ $G_{1}=G\setminus F$ $G_{1}=G\setminus F$ $G_{1}=G\setminus F$ 를 형성한다. 여기서 $G\setminus F$ $G\setminus F$ $G\setminus F$ $G\setminus F$ 는 F에서 가장자리를 수축하여 G에서 파생된 그래프를 나타낸다 $G\setminus F$ (컷 속성에 의해 이 가장자리는 MST에 속한다). 각각의 보루브카 스텝은 선형적인 시간이 걸린다. 각 단계에서 정점 수가 최소한 절반 이상 줄어들기 때문에 보루브카의 알고리즘에는 O(m log n) 시간이 걸린다.^[4]

두 번째 알고리즘은 프림의 알고리즘으로 1930년 Vojtěch Jarnik에 의해 발명되어 1957년 Prim, 1959년 Dijkstra에 의해 재발견되었다. 기본적으로 MST(T)를 한 번에 한 엣지씩 성장시킨다. 처음에 T는 임의의 꼭지점을 포함한다. 각 단계에서 T는 x가 T에 있고 y가 아직 T에 있지 않은 최소 중량 에지(x,y)로 증강된다. 컷 속성에 의해 T에 추가된 모든 에지는 MST에 있다. 런타임은 사용된 데이터 구조에 따라 O(m log n) 또는 O(m + n log n)이다.

일반적으로 사용되고 있는 세 번째 알고리즘은 크러스칼의 알고리즘으로 O(m log n) 시간도 소요된다.

일반적으로 사용되지 않는 네 번째 알고리즘은 크러스칼의 알고리즘의 역순인 역삭제 알고리즘이다. 그것의 런타임은 O(m log n (log log n)이다.³

이 네 가지 모두 탐욕스러운 알고리즘이다. 다항식 시간에 실행되기 때문에 그러한 트리를 찾는 문제는 FP에 있으며, 특정 에지가 MST에 있는지 또는 최소 총중량이 일정 값을 초과하는지 판단하는 등의 관련 의사결정 문제는 P에 있다.

더 빠른 알고리즘

몇몇 연구자들은 좀 더 계산적으로 효율적인 알고리즘을 찾으려고 노력해왔다.

가장자리 무게에 대해 허용된 유일한 연산이 쌍 비교인 비교 모델에서, 카거, 클라인 & 타르잔(1995)은 보르조프카의 알고리즘과 역삭제 알고리즘의 조합에 기초한 선형 시간 무작위화 알고리즘을 발견했다.^[5]^[6]

버나드 샤젤이 복잡성을 알고 있는 가장 빠른 무작위 비교 기반 알고리즘은 대략적인 우선 순위 대기열인 소프트 힙을 기반으로 한다.^[7]^[8] 그것의 가동 시간은 O(m α(m,n)이며, 여기서 α는 아커만 함수의 고전적인 기능 역이다. 함수 α는 매우 느리게 성장하므로, 모든 실제적인 목적에서는 4 이하의 상수로 간주될 수 있다. 따라서 샤젤의 알고리즘은 선형 시간에 매우 근접하게 걸린다.

특별한 경우 선형 시간 알고리즘

밀도 그래프

그래프가 밀도(예: m/n ≥ 로그 로그 n)인 경우 프레드만과 타르잔에 의한 결정론 알고리즘은 시간 O(m)에서 MST를 찾는다.^[9] 알고리즘은 여러 단계를 실행한다. 각 페이즈는 제한된 수의 스텝에 대해 각각 Prim의 알고리즘을 여러 번 실행한다. 각 단계의 런타임은 O(m+n)이다. 한 단계 이전의 정점 $n'$ 가 n{{\ $displaystyle$ n $'}$ 인 경우 $n'$ 한 단계 후에 남아 있는 정점 수는 최대 $n'/2^{m/n'}$ $n'/2^{m/n'}$ / $n'/2^{m/n'}$ m $n'/2^{m/n'}$ / $n'/2^{m/n'}$ $n'/2^{m/n'}$ ${\$ n $'/2^{m/n$ 이므로, 대부분의 $\log ^{*}{n}$ $\log ^{*}{n}$ $\log ^{*}{n}$ ${\$ 페이즈가 $\log ^{*}{n}$ 필요하며, 밀도 그래프의 선형 런타임이 필요하다.^[4]

밀도가 높은 그래프에서 선형적으로 작동하는 다른 알고리즘도 있다.^[7]^[10]

정수 가중치

에지 가중치가 2진수로 표현되는 정수인 경우, O(m + n) 정수 연산에서 문제를 해결하는 결정론적 알고리즘이 알려져 있다.^[11] 비교 기반 알고리즘에 의해 선형 시간 내에 일반 그래프의 결정적으로 문제를 해결할 수 있을지는 여전히 열려 있는 문제로 남아 있다.

의사결정 나무

노드와 가장자리가 고정되어 있지만 가중치를 알 수 없는 그래프 G를 사용하면 가중치의 순열에 대한 MST 계산을 위한 이진 결정 트리(DT)를 구성할 수 있다. DT의 각 내부 노드에는 두 에지 사이의 비교가 포함되어 있다. 예를 들어, "x와 y 사이의 에지 무게가 w와 z 사이의 에지 무게보다 크는가?" 노드의 두 자녀는 "예" 또는 "아니오"라는 두 가지 가능한 대답에 해당한다. DT의 각 잎에는 MST에 해당하는 G의 가장자리 목록이 있다. DT의 런타임 복잡성은 MST를 찾는 데 필요한 쿼리 중 가장 많은 수치로, 이는 DT의 깊이일 뿐이다. 그래프 G의 DT는 G에 대한 모든 정확한 DT의 가장 작은 깊이를 가질 경우 최적이라고 불린다.

모든 정수 r에 대해, brute-force 검색을 통해 r 정점의 모든 그래프에 대한 최적의 결정 트리를 찾을 수 있다. 이 검색은 두 단계로 진행된다.

A. 모든 잠재적 DT 생성

r 정점에 $2^{r \choose 2}$ ( $2^{r \choose 2}$ $){\$ \2 $}}$ 개의 다른 $2^{r \choose 2}$ 그래프가 있다.
각 그래프에 대해 MST는 항상 R(r-1) 비교를 사용하여 찾을 수 있다(예: Prim's 알고리즘).
따라서 최적 DT의 깊이는 $r^{2}$ $r^{2}$ ${\$ r $^{2}}$ 보다 작다 $r^{2}$
따라서 최적 DT에서 내부 노드 수는 $2^{r^{2}}$ 2 ${\$ 2 $^{r^{2$ }}개 미만이다 $2^{r^{2}}$
모든 내부 노드는 두 개의 가장자리를 비교한다. 가장자리 수는 최대 $r^{2}$ $r^{2}$ ${\$ r $^{2}}$ 개이므로 $r^{2}$ 서로 다른 비교 $r^{4}$ 는 최대 r $r^{4}$ ${\$ r^{ $4$ 이다.
따라서 잠재적 DT의 수는 ( ${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}$ 4 ${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}$ ) ${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}$ ( 2 ${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}$ ${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}$ ) ${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}$ = ${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}$ ${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}$ ( r ${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}$ + ${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}$ ){\ $displaystyle$ {( $r^{4}}}}^{2^{2}}}^{2}}=$ r^{2^{2}}}}= $r^{2}+2)}}}}}}}}}}}}$ 보다 적다 ${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}$

B. 올바른 DT 식별 DT가 올바른지 확인하려면 가장자리 웨이트의 가능한 모든 순열을 확인해야 한다.

이러한 순열의 수는 최대 $(r^{2})!$ ( $(r^{2})!$ $(r^{2})!$ ${\displaystyle (r^{2})!$ $}$ .
각 순열에 대해 기존 알고리즘을 사용하여 주어진 그래프의 MST 문제를 해결하고 그 결과를 DT가 제공한 답과 비교한다.
MST 알고리즘의 실행 시간은 최대 $(r^{2})$ ( $(r^{2})$ $(r^{2})$ ) ${\displaystyle (r^{2$ 이므로 모든 순열을 확인하는 데 필요한 총 시간은 최대 $(r^{2}+1)!$ ( $(r^{2}+1)!$ $(r^{2}+1)!$ + $(r^{2}+1)!$ $(r^{2}+1)!$ 입니다 $(r^{2}+1)!$

Hence, the total time required for finding an optimal DT for all graphs with r vertices is: $2^{r \choose 2}\cdot r^{2^{(r^{2}+2)}}\cdot (r^{2}+1)!$ , which is less than: $2^{2^{r^{2}+o(r)}}$ .^[4]

최적 알고리즘

세스 페티와 Vijaya Ramachandran은 입증 가능한 최적의 결정론적 비교 기반 최소 스패닝 트리 알고리즘을 발견했다.^[4] 다음은 알고리즘에 대한 간략한 설명이다.

let $r=\log \log \log n$ = $r=\log \log \log n$ log 로그 $r=\log \log \log n$ 로그 $r=\log \log \log n$ ${\displaystyle r=\log \log \log n$ 여기서 n은 정점의 수입니다. 모든 최적의 결정 트리를 r 정점에서 찾으십시오. 이 작업은 시간 O(n)에 수행할 수 있다(위의 의사결정 트리 참조).
그래프를 각 성분에 최대 r 정점이 있는 성분에 맞게 분할하십시오. 이 파티션은 부드러운 힙을 사용하며, 이것은 그래프의 가장자리 일부를 "파손"한다.
각 구성 요소 내에서 손상되지 않은 하위 그래프의 MST를 찾으려면 최적의 의사결정 트리를 사용하십시오.
MST에 의해 확장된 각 연결 구성요소를 단일 꼭지점에 수축시키고, O(m) 시간에 밀도 그래프에 작용하는 알고리즘을 손상되지 않은 서브그래프의 수축에 적용한다.
손상된 가장자리를 다시 포리스트에 추가하여 최소 스패닝 트리를 포함하도록 보장하고 시작 그래프보다 상수 인수로 작은 하위 그래프를 형성하십시오. 최적의 알고리즘을 이 그래프에 반복적으로 적용하십시오.

결정 트리를 사용하는 단계를 제외하고 알고리즘의 모든 단계의 런타임은 O(m)이다. 이 단계의 런타임은 알 수 없지만, 최적의 결정 트리보다 더 잘 할 수 있는 알고리즘은 없다는 것이 증명되었다. 따라서 이 알고리즘은 런타임 복잡성을 알 수 없지만 최적이란 특성을 가지고 있다.

병렬 및 분산 알고리즘

연구는 또한 최소 스패닝 트리 문제에 대한 병렬 알고리즘을 고려했다. 프로세서의 선형 개수를 사용하면 $O(\log n)$ $O(\log n)$ ) $O(\log n)$ 시간 $O(\log n)$ 내에 문제를 해결할 수 있다.^[12]^[13] Bader & Cong(2006)는 최적화된 순차 알고리즘보다 8개의 프로세서에서 5배 더 빠르게 MST를 계산할 수 있는 알고리즘을 시연한다.^[14]

다른 전문 알고리즘은 그래프의 대부분이 항상 디스크에 저장되어야 할 정도로 큰 그래프의 최소 스패닝 트리를 계산하도록 설계되었다. 예를 들어, Roman, Denteniev 외 연구진의 "외부 메모리 최소 스패닝 트리 알고리즘 엔지니어링"에서 설명한 것처럼, 이러한 외부 스토리지 알고리즘은 기존의 메모리 내 알고리즘보다 2-5배 정도 느리게 작동할 수 있다.^[15] 효율적인 외부 스토리지 정렬 알고리즘과 그래프 축소 기술에 의존하여 그래프의 크기를 효율적으로 줄인다.

그 문제는 분산된 방식으로도 접근될 수 있다. 각 노드가 컴퓨터로 간주되고 자체 연결된 링크 외에는 노드가 아무것도 모르더라도 분산 최소 스패닝 트리를 계산할 수 있다.

전체 그래프의 MST

AlanM. 프리즈, 가장자리 추로 분포 함수 F과 독립심 같은 분산된 확률 변수 F을 만족시키 ′(0)을{F\displaystyle};0{\displaystyle F'(0)>0} 다음 n접근법 +∞은 MST접근법의 예상 체중 ζ(3)/F.nvertices에 대한 완전한 주어진 그래프를 보였다′( $\zeta (3)/F'(0)$ ) ${\displaystyle \zeta$ ( $3)/F'($ 0 $\zeta (3)/F'(0)$ $\zeta$ 서 { ${\displaystyle \zeta$ }은 $\zeta$ (는) Riemann 제타 함수(더 구체적으로 $\zeta (3)$ ( $\zeta (3)$ ) $\zeta (3)$ Apéry의 $\zeta (3)$ 상수. 프리즈와 스틸은 확률에서도 융합을 증명했다. Svante Janson은 MST의 무게에 대한 중심 한계 정리를 증명했다.

$[0,1]$ $[0,1]$ , $[0,1]$ $[0,1]$ $[0,1]$ 의 균일한 무작위 가중치에 대해 최소 스패닝 트리의 정확한 예상 크기가 작은 전체 그래프에 대해 계산되었다.^[16]

정점	예상크기	대략적인 예상 크기
2	1 / 2	0.5
3	3 / 4	0.75
4	31 / 35	0.8857143
5	893 / 924	0.9664502
6	278 / 273	1.0183151
7	30739 / 29172	1.053716
8	199462271 / 184848378	1.0790588
9	126510063932 / 115228853025	1.0979027

적용들

최소 스패닝 트리는 컴퓨터 네트워크, 통신 네트워크, 운송 네트워크, 급수 네트워크, 전기 그리드(이들은 위에서 언급한 바와 같이 처음 발명되었다)를 포함한 네트워크 설계에 직접적인 응용이 있다.^[17] 그들은 서브 루틴으로 다른 문제들이 알고리즘에서, 외교 판매계원. problem,[18]은multi-terminal 최소 인하 문제로(는single-terminal 경우 최대 흐름 문제에 해당합니다)[19]고 minimum-cost를 완벽한 시합으로를 근사치로 계산은 Christofides 알고리즘을 포함하여 호출되면.ing.[20]

최소 스패닝 트리를 기반으로 한 기타 실제 애플리케이션은 다음과 같다.

분류법.^[21]
군집 분석: 평면의 군집화 점,^[22] 단일 링크 군집화(계층적 군집화 방법),^[23]^[25] 그래프-이론적 군집화 ^[24]및 군집화 유전자 표현 데이터.
컴퓨터 네트워크에서의 방송을 위한 나무들을 건설한다.^[26]
이미지 등록^[27] 및 분할^[28] – 최소 신장 트리 기반 분할을 참조하십시오.
컴퓨터 시력의 곡선형 특징 추출.^[29]
수학적 표현식의 필기 인식.^[30]
회로 설계: 유한 임펄스 응답 필터에 사용되는 효율적인 다중 상수 곱셈 구현.^[31]
사회 지리학 영역의 지역화, 동질적이고 연속적인 영역으로 영역을 그룹화.^[32]
생태독성학 데이터를 비교하는 중.^[33]
전력 시스템의 위상학적 관측 가능성.^[34]
2차원 물질의 동질성 측정.^[35]
미니맥스 공정 제어.^[36]
최소 스패닝 트리는 금융시장을 설명하는 데도 사용될 수 있다.^[37]^[38] 상관 행렬은 두 주식 사이의 상관 계수를 계산하여 만들 수 있다. 이 매트릭스는 지형학적으로 복잡한 네트워크로 표현될 수 있으며 최소 스패닝 트리를 구성하여 관계를 시각화할 수 있다.

참조

^ "scipy.sparse.csgraph.minimum_spanning_tree - SciPy v1.7.1 Manual". Numpy and Scipy Documentation — Numpy and Scipy documentation. Retrieved 2021-12-10. A minimum spanning tree is a graph consisting of the subset of edges which together connect all connected nodes, while minimizing the total sum of weights on the edges.
^ "networkx.algorithms.tree.mst.minimum_spanning_edges". NetworkX 2.6.2 documentation. Retrieved 2021-12-13. A minimum spanning tree is a subgraph of the graph (a tree) with the minimum sum of edge weights. A spanning forest is a union of the spanning trees for each connected component of the graph.
^ "Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?". cs.stackexchange.com. Retrieved 4 April 2018.
^ ^a ^b ^c ^d ^e Pettie, Seth; Ramachandran, Vijaya (2002), "An optimal minimum spanning tree algorithm" (PDF), Journal of the Association for Computing Machinery, 49 (1): 16–34, doi:10.1145/505241.505243, MR 2148431, S2CID 5362916.
^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), "A randomized linear-time algorithm to find minimum spanning trees", Journal of the Association for Computing Machinery, 42 (2): 321–328, doi:10.1145/201019.201022, MR 1409738, S2CID 832583
^ Pettie, Seth; Ramachandran, Vijaya (2002), "Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms", Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), San Francisco, California, pp. 713–722.
^ ^a ^b Chazelle, Bernard (2000), "A minimum spanning tree algorithm with inverse-Ackermann type complexity", Journal of the Association for Computing Machinery, 47 (6): 1028–1047, doi:10.1145/355541.355562, MR 1866456, S2CID 6276962.
^ Chazelle, Bernard (2000), "The soft heap: an approximate priority queue with optimal error rate" (PDF), Journal of the Association for Computing Machinery, 47 (6): 1012–1027, doi:10.1145/355541.355554, MR 1866455, S2CID 12556140.
^ Fredman, M. L.; Tarjan, R. E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the ACM. 34 (3): 596. doi:10.1145/28869.28874. S2CID 7904683.
^ Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. (1986). "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs". Combinatorica. 6 (2): 109. doi:10.1007/bf02579168. S2CID 35618095.
^ Fredman, M. L.; Willard, D. E. (1994), "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", Journal of Computer and System Sciences, 48 (3): 533–551, doi:10.1016/S0022-0000(05)80064-9, MR 1279413.
^ Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), "Concurrent threads and optimal parallel minimum spanning trees algorithm", Journal of the Association for Computing Machinery, 48 (2): 297–323, doi:10.1145/375827.375847, MR 1868718, S2CID 1778676.
^ Pettie, Seth; Ramachandran, Vijaya (2002), "A randomized time-work optimal parallel algorithm for finding a minimum spanning forest" (PDF), SIAM Journal on Computing, 31 (6): 1879–1895, doi:10.1137/S0097539700371065, MR 1954882.
^ Bader, David A.; Cong, Guojing (2006), "Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs", Journal of Parallel and Distributed Computing, 66 (11): 1366–1378, doi:10.1016/j.jpdc.2006.06.001, S2CID 2004627.
^ Dementiev, Roman; Sanders, Peter; Schultes, Dominik; Sibeyn, Jop F. (2004), "Engineering an external memory minimum spanning tree algorithm", Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004) (PDF), pp. 195–208.
^ Steele, J. Michael (2002), "Minimal spanning trees for graphs with random edge lengths", Mathematics and computer science, II (Versailles, 2002), Trends Math., Basel: Birkhäuser, pp. 223–245, MR 1940139
^ Graham, R. L.; Hell, Pavol (1985), "On the history of the minimum spanning tree problem", Annals of the History of Computing, 7 (1): 43–57, doi:10.1109/MAHC.1985.10011, MR 0783327, S2CID 10555375
^ 니코스 크리스토피데스, 1976년 CMU 산업행정대학원 보고서 388, 여행 세일즈맨 문제에 대한 새로운 휴리스틱스의 최악의 사례 분석.
^ Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. (August 1994). "The complexity of multiterminal cuts" (PDF). SIAM Journal on Computing. 23 (4): 864–894. doi:10.1137/S0097539792225297. Archived from the original (PDF) on 24 August 2004. Retrieved 17 December 2012.
^ Supowit, Kenneth J.; Plaisted, David A.; Reingold, Edward M. (1980). Heuristics for weighted perfect matching. 12th Annual ACM Symposium on Theory of Computing (STOC '80). New York, NY, USA: ACM. pp. 398–419. doi:10.1145/800141.804689.
^ Sneath, P. H. A. (1 August 1957). "The Application of Computers to Taxonomy". Journal of General Microbiology. 17 (1): 201–226. doi:10.1099/00221287-17-1-201. PMID 13475686.
^ Asano, T.; Bhattacharya, B.; Keil, M.; Yao, F. (1988). Clustering algorithms based on minimum and maximum spanning trees. Fourth Annual Symposium on Computational Geometry (SCG '88). Vol. 1. pp. 252–257. doi:10.1145/73393.73419.
^ Gower, J. C.; Ross, G. J. S. (1969). "Minimum Spanning Trees and Single Linkage Cluster Analysis". Journal of the Royal Statistical Society. C (Applied Statistics). 18 (1): 54–64. doi:10.2307/2346439. JSTOR 2346439.
^ Päivinen, Niina (1 May 2005). "Clustering with a minimum spanning tree of scale-free-like structure". Pattern Recognition Letters. 26 (7): 921–930. doi:10.1016/j.patrec.2004.09.039.
^ Xu, Y.; Olman, V.; Xu, D. (1 April 2002). "Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees". Bioinformatics. 18 (4): 536–545. doi:10.1093/bioinformatics/18.4.536. PMID 12016051.
^ Dalal, Yogen K.; Metcalfe, Robert M. (1 December 1978). "Reverse path forwarding of broadcast packets". Communications of the ACM. 21 (12): 1040–1048. doi:10.1145/359657.359665. S2CID 5638057.
^ Ma, B.; Hero, A.; Gorman, J.; Michel, O. (2000). Image registration with minimum spanning tree algorithm (PDF). International Conference on Image Processing. Vol. 1. pp. 481–484. doi:10.1109/ICIP.2000.901000.
^ P. Felzenszwalb, D. Huttenlocher: 효율적인 그래프 기반 이미지 분할. IJCV 59(2)(2004년 9월)
^ Suk, Minsoo; Song, Ohyoung (1 June 1984). "Curvilinear feature extraction using minimum spanning trees". Computer Vision, Graphics, and Image Processing. 26 (3): 400–411. doi:10.1016/0734-189X(84)90221-4.
^ Tapia, Ernesto; Rojas, Raúl (2004). "Recognition of On-line Handwritten Mathematical Expressions Using a Minimum Spanning Tree Construction and Symbol Dominance" (PDF). Graphics Recognition. Recent Advances and Perspectives. Lecture Notes in Computer Science. Vol. 3088. Berlin Heidelberg: Springer-Verlag. pp. 329–340. ISBN 978-3540224785.
^ Ohlsson, H. (2004). Implementation of low complexity FIR filters using a minimum spanning tree. 12th IEEE Mediterranean Electrotechnical Conference (MELECON 2004). Vol. 1. pp. 261–264. doi:10.1109/MELCON.2004.1346826.
^ Assunção, R. M.; M. C. Neves; G. Câmara; C. Da Costa Freitas (2006). "Efficient regionalization techniques for socio‐economic geographical units using minimum spanning trees". International Journal of Geographical Information Science. 20 (7): 797–811. doi:10.1080/13658810600665111. S2CID 2530748.
^ Devillers, J.; Dore, J.C. (1 April 1989). "Heuristic potency of the minimum spanning tree (MST) method in toxicology". Ecotoxicology and Environmental Safety. 17 (2): 227–235. doi:10.1016/0147-6513(89)90042-0. PMID 2737116.
^ Mori, H.; Tsuzuki, S. (1 May 1991). "A fast method for topological observability analysis using a minimum spanning tree technique". IEEE Transactions on Power Systems. 6 (2): 491–500. Bibcode:1991ITPSy...6..491M. doi:10.1109/59.76691.
^ Filliben, James J.; Kafadar, Karen; Shier, Douglas R. (1 January 1983). "Testing for homogeneity of two-dimensional surfaces". Mathematical Modelling. 4 (2): 167–189. doi:10.1016/0270-0255(83)90026-X.
^ Kalaba, Robert E. (1963), Graph Theory and Automatic Control (PDF)
^ R. N. Mantegna(1999년). 금융 시장의 계층 구조. 유럽 물리 저널 B-Conduated Matter and Complex Systems, 11(1), 193-197.
^ Djauhari, M, & Gan, S. (2015) 주식 시장 분석에서 네트워크 토폴로지의 최적성 문제. 물리학 A: 통계 역학과 그 응용, 419, 108-114.
^ Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5. ND12
^ Gabow, Harold N. (1977), "Two algorithms for generating weighted spanning trees in order", SIAM Journal on Computing, 6 (1): 139–150, doi:10.1137/0206011, MR 0441784.
^ Eppstein, David (1992), "Finding the k smallest spanning trees", BIT, 32 (2): 237–248, doi:10.1007/BF01994879, MR 1172188, S2CID 121160520.
^ Frederickson, Greg N. (1997), "Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees", SIAM Journal on Computing, 26 (2): 484–538, doi:10.1137/S0097539792226825, MR 1438526.
^ Jothi, Raja; Raghavachari, Balaji (2005), "Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design", ACM Trans. Algorithms, 1 (2): 265–282, doi:10.1145/1103963.1103967, S2CID 8302085
^ Hu, T. C. (1961), "The maximum capacity route problem", Operations Research, 9 (6): 898–900, doi:10.1287/opre.9.6.898, JSTOR 167055.
^ McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan (2005). "Non-projective dependency parsing using spanning tree algorithms" (PDF). Proc. HLT/EMNLP.
^ Spira, P. M.; Pan, A. (1975), "On finding and updating spanning trees and shortest paths" (PDF), SIAM Journal on Computing, 4 (3): 375–380, doi:10.1137/0204032, MR 0378466.
^ Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel (2001), "Poly-logarithmic deterministic fully dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity", Journal of the Association for Computing Machinery, 48 (4): 723–760, doi:10.1145/502090.502095, MR 2144928, S2CID 7273552.
^ Chin, F.; Houck, D. (1978), "Algorithms for updating minimal spanning trees", Journal of Computer and System Sciences, 16 (3): 333–344, doi:10.1016/0022-0000(78)90022-3.
^ Chang, R.S.; Leu, S.J. (1997), "The minimum labeling spanning trees", Information Processing Letters, 63 (5): 277–282, doi:10.1016/s0020-0190(97)00127-0.
^ "Everything about Bottleneck Spanning Tree". flashing-thoughts.blogspot.ru. Retrieved 4 April 2018.
^ http://pages.cpsc.ucalgary.ca/~dcalin/413/t4.pdf

추가 읽기

최소 스패닝 트리 문제에 관한 오타카 보루브카(Otakar Boruvka on Minimum Spanning Tree)(1926년 논문, 논평, 역사 모두 번역)(2000년) 야로슬라프 네셰틸, 에바 밀코바, 헬레나 네세트릴로바(제7절)는 프림과 크루스칼의 교차처럼 보이는 그의 알고리즘을 제시한다.
토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, Clifford Stein. 알고리즘 소개, Second Edition. MIT 프레스 앤 맥그로우 힐, 2001. ISBN 0-262-03293-7 23장: 최소 스패닝 트리, 페이지 561~579.
아이즈너, 제이슨(1997년). 최소 스패닝 트리에 대한 최신 알고리즘: 튜토리얼 토론. 원고, 펜실베니아 대학, 4월 78 페이지.
크롬코프스키, 존 데이비드 "이 모든 해가 지난 후에도 여전히 녹지 않음" (연간판, 인종 및 민족 관계), 17/e (2009 McGraw Hill) (미국 전역의 민족 다양성에 대한 인구통계학적 분석 방법으로 최소 스패닝 트리 사용)

외부 링크

[Numpy_and_Scipy_Documentation_—_Numpy_and_Scipy_documentation-1] "scipy.sparse.csgraph.minimum_spanning_tree - SciPy v1.7.1 Manual". Numpy and Scipy Documentation — Numpy and Scipy documentation. Retrieved 2021-12-10. A minimum spanning tree is a graph consisting of the subset of edges which together connect all connected nodes, while minimizing the total sum of weights on the edges.

[NetworkX_2.6.2_documentation-2] "networkx.algorithms.tree.mst.minimum_spanning_edges". NetworkX 2.6.2 documentation. Retrieved 2021-12-13. A minimum spanning tree is a subgraph of the graph (a tree) with the minimum sum of edge weights. A spanning forest is a union of the spanning trees for each connected component of the graph.

[3] "Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?". cs.stackexchange.com. Retrieved 4 April 2018.

[PettieRamachandran2002-4] Pettie, Seth; Ramachandran, Vijaya (2002), "An optimal minimum spanning tree algorithm" (PDF), Journal of the Association for Computing Machinery, 49 (1): 16–34, doi:10.1145/505241.505243, MR 2148431, S2CID 5362916.

[5] Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), "A randomized linear-time algorithm to find minimum spanning trees", Journal of the Association for Computing Machinery, 42 (2): 321–328, doi:10.1145/201019.201022, MR 1409738, S2CID 832583

[6] Pettie, Seth; Ramachandran, Vijaya (2002), "Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms", Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), San Francisco, California, pp. 713–722.

[Chazelle2000-7] Chazelle, Bernard (2000), "A minimum spanning tree algorithm with inverse-Ackermann type complexity", Journal of the Association for Computing Machinery, 47 (6): 1028–1047, doi:10.1145/355541.355562, MR 1866456, S2CID 6276962.

[8] Chazelle, Bernard (2000), "The soft heap: an approximate priority queue with optimal error rate" (PDF), Journal of the Association for Computing Machinery, 47 (6): 1012–1027, doi:10.1145/355541.355554, MR 1866455, S2CID 12556140.

[9] Fredman, M. L.; Tarjan, R. E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the ACM. 34 (3): 596. doi:10.1145/28869.28874. S2CID 7904683.

[10] Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. (1986). "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs". Combinatorica. 6 (2): 109. doi:10.1007/bf02579168. S2CID 35618095.

[11] Fredman, M. L.; Willard, D. E. (1994), "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", Journal of Computer and System Sciences, 48 (3): 533–551, doi:10.1016/S0022-0000(05)80064-9, MR 1279413.

[12] Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), "Concurrent threads and optimal parallel minimum spanning trees algorithm", Journal of the Association for Computing Machinery, 48 (2): 297–323, doi:10.1145/375827.375847, MR 1868718, S2CID 1778676.

[13] Pettie, Seth; Ramachandran, Vijaya (2002), "A randomized time-work optimal parallel algorithm for finding a minimum spanning forest" (PDF), SIAM Journal on Computing, 31 (6): 1879–1895, doi:10.1137/S0097539700371065, MR 1954882.

[14] Bader, David A.; Cong, Guojing (2006), "Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs", Journal of Parallel and Distributed Computing, 66 (11): 1366–1378, doi:10.1016/j.jpdc.2006.06.001, S2CID 2004627.

[15] Dementiev, Roman; Sanders, Peter; Schultes, Dominik; Sibeyn, Jop F. (2004), "Engineering an external memory minimum spanning tree algorithm", Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004) (PDF), pp. 195–208.

[16] Steele, J. Michael (2002), "Minimal spanning trees for graphs with random edge lengths", Mathematics and computer science, II (Versailles, 2002), Trends Math., Basel: Birkhäuser, pp. 223–245, MR 1940139

[17] Graham, R. L.; Hell, Pavol (1985), "On the history of the minimum spanning tree problem", Annals of the History of Computing, 7 (1): 43–57, doi:10.1109/MAHC.1985.10011, MR 0783327, S2CID 10555375

[18] 니코스 크리스토피데스, 1976년 CMU 산업행정대학원 보고서 388, 여행 세일즈맨 문제에 대한 새로운 휴리스틱스의 최악의 사례 분석.

[19] Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. (August 1994). "The complexity of multiterminal cuts" (PDF). SIAM Journal on Computing. 23 (4): 864–894. doi:10.1137/S0097539792225297. Archived from the original (PDF) on 24 August 2004. Retrieved 17 December 2012.

[20] Supowit, Kenneth J.; Plaisted, David A.; Reingold, Edward M. (1980). Heuristics for weighted perfect matching. 12th Annual ACM Symposium on Theory of Computing (STOC '80). New York, NY, USA: ACM. pp. 398–419. doi:10.1145/800141.804689.

[21] Sneath, P. H. A. (1 August 1957). "The Application of Computers to Taxonomy". Journal of General Microbiology. 17 (1): 201–226. doi:10.1099/00221287-17-1-201. PMID 13475686.

[22] Asano, T.; Bhattacharya, B.; Keil, M.; Yao, F. (1988). Clustering algorithms based on minimum and maximum spanning trees. Fourth Annual Symposium on Computational Geometry (SCG '88). Vol. 1. pp. 252–257. doi:10.1145/73393.73419.

[23] Gower, J. C.; Ross, G. J. S. (1969). "Minimum Spanning Trees and Single Linkage Cluster Analysis". Journal of the Royal Statistical Society. C (Applied Statistics). 18 (1): 54–64. doi:10.2307/2346439. JSTOR 2346439.

[24] Päivinen, Niina (1 May 2005). "Clustering with a minimum spanning tree of scale-free-like structure". Pattern Recognition Letters. 26 (7): 921–930. doi:10.1016/j.patrec.2004.09.039.

[25] Xu, Y.; Olman, V.; Xu, D. (1 April 2002). "Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees". Bioinformatics. 18 (4): 536–545. doi:10.1093/bioinformatics/18.4.536. PMID 12016051.

[26] Dalal, Yogen K.; Metcalfe, Robert M. (1 December 1978). "Reverse path forwarding of broadcast packets". Communications of the ACM. 21 (12): 1040–1048. doi:10.1145/359657.359665. S2CID 5638057.

[27] Ma, B.; Hero, A.; Gorman, J.; Michel, O. (2000). Image registration with minimum spanning tree algorithm (PDF). International Conference on Image Processing. Vol. 1. pp. 481–484. doi:10.1109/ICIP.2000.901000.

[28] P. Felzenszwalb, D. Huttenlocher: 효율적인 그래프 기반 이미지 분할. IJCV 59(2)(2004년 9월)

[29] Suk, Minsoo; Song, Ohyoung (1 June 1984). "Curvilinear feature extraction using minimum spanning trees". Computer Vision, Graphics, and Image Processing. 26 (3): 400–411. doi:10.1016/0734-189X(84)90221-4.

[30] Tapia, Ernesto; Rojas, Raúl (2004). "Recognition of On-line Handwritten Mathematical Expressions Using a Minimum Spanning Tree Construction and Symbol Dominance" (PDF). Graphics Recognition. Recent Advances and Perspectives. Lecture Notes in Computer Science. Vol. 3088. Berlin Heidelberg: Springer-Verlag. pp. 329–340. ISBN 978-3540224785.

[31] Ohlsson, H. (2004). Implementation of low complexity FIR filters using a minimum spanning tree. 12th IEEE Mediterranean Electrotechnical Conference (MELECON 2004). Vol. 1. pp. 261–264. doi:10.1109/MELCON.2004.1346826.

[32] Assunção, R. M.; M. C. Neves; G. Câmara; C. Da Costa Freitas (2006). "Efficient regionalization techniques for socio‐economic geographical units using minimum spanning trees". International Journal of Geographical Information Science. 20 (7): 797–811. doi:10.1080/13658810600665111. S2CID 2530748.

[33] Devillers, J.; Dore, J.C. (1 April 1989). "Heuristic potency of the minimum spanning tree (MST) method in toxicology". Ecotoxicology and Environmental Safety. 17 (2): 227–235. doi:10.1016/0147-6513(89)90042-0. PMID 2737116.

[34] Mori, H.; Tsuzuki, S. (1 May 1991). "A fast method for topological observability analysis using a minimum spanning tree technique". IEEE Transactions on Power Systems. 6 (2): 491–500. Bibcode:1991ITPSy...6..491M. doi:10.1109/59.76691.

[35] Filliben, James J.; Kafadar, Karen; Shier, Douglas R. (1 January 1983). "Testing for homogeneity of two-dimensional surfaces". Mathematical Modelling. 4 (2): 167–189. doi:10.1016/0270-0255(83)90026-X.

[36] Kalaba, Robert E. (1963), Graph Theory and Automatic Control (PDF)

[37] R. N. Mantegna(1999년). 금융 시장의 계층 구조. 유럽 물리 저널 B-Conduated Matter and Complex Systems, 11(1), 193-197.

[38] Djauhari, M, & Gan, S. (2015) 주식 시장 분석에서 네트워크 토폴로지의 최적성 문제. 물리학 A: 통계 역학과 그 응용, 419, 108-114.

[39] Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5. ND12

[40] Gabow, Harold N. (1977), "Two algorithms for generating weighted spanning trees in order", SIAM Journal on Computing, 6 (1): 139–150, doi:10.1137/0206011, MR 0441784.

[41] Eppstein, David (1992), "Finding the k smallest spanning trees", BIT, 32 (2): 237–248, doi:10.1007/BF01994879, MR 1172188, S2CID 121160520.

[42] Frederickson, Greg N. (1997), "Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees", SIAM Journal on Computing, 26 (2): 484–538, doi:10.1137/S0097539792226825, MR 1438526.

[43] Jothi, Raja; Raghavachari, Balaji (2005), "Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design", ACM Trans. Algorithms, 1 (2): 265–282, doi:10.1145/1103963.1103967, S2CID 8302085

[44] Hu, T. C. (1961), "The maximum capacity route problem", Operations Research, 9 (6): 898–900, doi:10.1287/opre.9.6.898, JSTOR 167055.

[45] McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan (2005). "Non-projective dependency parsing using spanning tree algorithms" (PDF). Proc. HLT/EMNLP.

[46] Spira, P. M.; Pan, A. (1975), "On finding and updating spanning trees and shortest paths" (PDF), SIAM Journal on Computing, 4 (3): 375–380, doi:10.1137/0204032, MR 0378466.

[47] Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel (2001), "Poly-logarithmic deterministic fully dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity", Journal of the Association for Computing Machinery, 48 (4): 723–760, doi:10.1145/502090.502095, MR 2144928, S2CID 7273552.

[48] Chin, F.; Houck, D. (1978), "Algorithms for updating minimal spanning trees", Journal of Computer and System Sciences, 16 (3): 333–344, doi:10.1016/0022-0000(78)90022-3.

[49] Chang, R.S.; Leu, S.J. (1997), "The minimum labeling spanning trees", Information Processing Letters, 63 (5): 277–282, doi:10.1016/s0020-0190(97)00127-0.

[50] "Everything about Bottleneck Spanning Tree". flashing-thoughts.blogspot.ru. Retrieved 4 April 2018.

[51] ttp://pages.cpsc.ucalgary.ca/~dcalin/413/t4.pdf

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[21]

[22]

[23]

[25]

[24]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

Search