동적 연결

컴퓨팅과 그래프 이론에서 동적 연결 구조는 그래프의 연결된 구성요소에 대한 정보를 동적으로 유지하는 데이터 구조다.

그래프의 정점 V는 고정되어 있지만, 에지의 설정 E는 변할 수 있다.세 가지 경우는 난이도 순으로 다음과 같다.

가장자리는 그래프에만 추가된다(증분 연결이라고 할 수 있음).
가장자리는 그래프에서만 삭제된다(이를 노쇠 연결이라고 할 수 있다).
가장자리는 추가하거나 삭제할 수 있다(완전한 동적 연결이라고 할 수 있다).

에지의 추가/삭제 후, 동적 연결 구조는 "x와 y 사이에 경로가 있는가?"(동일하게: "정점 x와 y가 동일한 연결 구성요소에 속하는가?") 형식의 질의에 빠른 답변을 제공할 수 있도록 스스로 적응해야 한다.

증분 연결

가장자리만 추가할 수 있는 경우 동적 연결 문제는 Dissjoint 설정 데이터 구조로 해결할 수 있다.각 집합은 연결된 구성요소를 나타내며, 동일한 집합에 속하는 경우에만 x와 y 사이에 경로가 있다.연산당 상각된 $\Theta (\alpha (n))$ 은 $\Theta (\alpha (n))$ ( $\Theta (\alpha (n))$ ( $\Theta (\alpha (n))$ ) $\Teta (\alpha (n)$ 인데 $\Theta (\alpha (n))$ 여기서 n은 정점의 수이고 α는 역 Ackermann 함수다.^[1]^[2]

노쇠 연결성

가장자리만 삭제할 수 있는 경우는 시몬 이븐과 요시 쉴로치가 해결했다.^[3]

구조는 각 꼭지점에 대해 자신이 속한 성분의 이름을 지정하는 표를 사용한다.따라서 연결 조회는 일정한 시간이 걸린다.엣지가 삭제될 때 테이블을 업데이트하는 것이 과제다.

반복 그래프(포리스트)

숲에서 엣지 u-v가 삭제되면, 그 가장자리가 포함된 트리는 두 개의 나무로 부러진다. 하나는 u를 포함하고 다른 하나는 v를 포함한다.표는 다음과 같은 방법으로 업데이트된다.

u부터 트리를 스캔하십시오(DFS와 같은 트리 스캔 알고리즘 사용).
v에서 시작하는 트리를 스캔하십시오.
위의 두 절차를 병렬로 수행하십시오. 즉, 두 개의 병렬 프로세스를 사용하거나 단계를 상호 전환하십시오(첫 번째 스캔, 두 번째 스캔, 첫 번째 스캔 단계, 첫 번째 스캔 단계 등).
종료되는 첫 번째 스캔이 u의 스캔이라고 가정합시다(그래서 우리는 u가 포함된 트리가 더 작다는 것을 알고 있다).u의 하위 트리에 있는 모든 노드에 새 구성 요소 이름을 할당하십시오.

항상 작은 하위 구성 요소의 이름을 변경하므로 삭제 작업에 대한 상각 시간은 $O(\log(n))$ 로그 $O(\log(n))$ ( $O(\log(n))$ ) ${\displaystyle$ O $(\log(n)}$ 입니다 $O(\log(n))$

일반 그래프

일반 그래프에서 가장자리가 삭제되면 그 성분이 단일 성분(다른 가장자리로 연결)으로 남아 있는지, 두 성분으로 깨져 있는지 알 수 없다.그래서 우리는 병렬(또는 인터리브 방식으로 실행되는)프로세스 A는 에지 삭제가 구성요소를 파괴하는지 여부를 점검하고, 그렇게 되면 두 프로세스가 모두 중단된다.프로세스 B는 에지 삭제가 해당 에지 삭제가 해당 에지가 속한 구성요소를 파손하지 않는지 여부를 점검하고, 그렇지 않은 경우 다시 두 프로세스가 모두 중단된다.

프로세스 A: Acyclick-graph 사례와 유사하다: 삭제된 가장자리의 양쪽 끝에서 스캔하는 두 개의 하위 프로그램이 있다.하위 프로세스 중 하나가 다른 끝에 도달하기 전에 완료되는 경우, 이는 구성요소가 두 개의 하위 구성 요소로 분할되고 더 작은 하위 구성 요소의 이름이 이전과 같이 업데이트됨을 의미한다.따라서 삭제 작업에 대해 상각된 시간은 다시 $O(\log(n))$ $O(\log(n))$ $O(\log(n))$ ( n $O(\log(n))$ ${\displaystyle$ O $(\log(n)}$ 입니다 $O(\log(n))$

프로세스 B: 폭 우선 구조(BFS)를 사용하여 다음과 같이 초기화한다.정점 r이 선택되고 BFS가 그것으로부터 시작된다.레벨 0의 유일한 꼭지점은 r이다.뿌리로부터 거리 i의 모든 정점은 레벨 i에 있다.G가 연결되지 않은 경우, 새 스캔이 시작되며, v가 레벨 1에 배치되고, 인공 에지가 v를 루트 r에 연결하며, v에서 거리 i의 모든 정점이 레벨 i+1에 위치한다.인공 가장자리는 연결된 모든 구성요소를 하나의 BFS 구조로 유지하기 위해 도입되며, 이러한 목적으로만 사용된다.분명히 인공 가장자리는 공정 B에서만 사용된다.

그 구조는 다음과 같은 특성을 가지고 있다.수준에 나는, i> 꼭지점 v;0, 가장자리 중 오직 3종류:그것i−1( 있는 인공 수 있는 최소 하나의 가장자리,)단계를 연결하는 후방 가장자리, 이것은 다른 가장자리로 수준에서 나는, 또는 가장자리로 수준i+1(에는 0이상의 이러한 가장자리가)에 장치를 연결할 앞으로 가장자리(에는 0이상의 이러한 가장자리가)를 연결할 지역 가장자리를 가지고 있다..따라서 각 꼭지점 v에 대해 우리는 세 개의 가장자리(뒤로, 로컬 및 앞으로)를 유지한다.

엣지 u-v를 삭제하면 u와 v가 같은 레벨이거나 숫자가 1로 다른 레벨의 두 가지 옵션이 있다.

사례 1: u와 v는 같은 레벨이다.이 경우 가장자리 삭제는 구성요소를 변경할 수 없다.u와 v의 로컬 가장자리 집합에서 가장자리가 간단히 삭제되고, 프로세스 B가 중지된다(따라서 프로세스 A도 중단된다).우리의 BFS 구조는 여전히 유효하다.

사례 2

u와 v는 레벨이 다르다.일반성을 잃지 않고 u가 레벨 i-1이고 v가 레벨 i라고 가정하십시오. 따라서 에지는 전방(u)에서, 후방(v)에서 제거해야 한다.

사례 2.1: 새 후진(v)이 비어 있지 않으면 구성 요소가 변경되지 않은 경우, v를 후진으로 연결하는 다른 가장자리가 있다.프로세스 B가 중지됨(그리고 프로세스 A도 중지됨).
케이스 2.2: 새 후진(v)이 비어 있으면 v가 더 이상 레벨 i-1에 연결되지 않으므로 루트와의 거리는 더 이상 i가 아니며, 적어도 i+1이어야 한다.또한 삭제의 결과로 루트와의 거리가 증가하는 v에 연결된 다른 정점이 있을 수 있다.업데이트된 거리를 계산하기 위해 처음에는 꼭지점 v만 포함하는 큐 Q를 사용한다.

Q가 비어 있지 않은 경우:

w := dequeue(Q)
w를 그 레벨(say, j)에서 제거하고 다음 레벨(j+1)에 넣는다.
로컬 인접 업데이트:
- local(w)의 각 엣지 w-x에 대해 local(x)에서 뗀 후 앞으로(x)에 넣는다.
- 역행 :=로컬(w)
정방향 인접 항목 업데이트:
- 앞쪽(w)의 각 에지 w-x에 대해 뒤로(x)에서 제거하고 로컬(x)에 넣으십시오. 새 뒤로(x)가 비어 있으면 Q에 x를 입력하십시오.
- local(w) := forward(w)
- 포워드(w) :=빈 세트
새 후진(w)이 비어 있는 경우 Q에 다시 w를 대기하십시오.

가장자리 삭제로 인해 어떤 구성요소도 파손되지 않고 2.2의 경우라면, 결국 절차가 중단될 것이다.이 경우 BFS 구조가 올바르게 유지되고 있음을 쉽게 알 수 있다.만약 그것의 삭제로 구성요소가 파괴된다면, 그 절차는 저절로 멈추지 않을 것이다.그러나 A 공정은 단절을 인식하여 중단되고, 두 공정 모두 중단된다.이 경우 BFS 구조의 모든 변경은 무시되며 삭제된 가장자리가 이제 인공 가장자리로 대체된다는 점을 제외하면 삭제 직전에 있었던 BFS 구조로 돌아간다.분명히, 이 경우 v는 이제 새로운 구성 요소와 아마도 다른 인공 가장자리를 통해 추가 구성 요소를 포함하는 트리의 뿌리가 된다.또한 인공 에지 $u-v$ - $u-v$ $u-v$ 을(를) 제외하고 $v$ 의 하위 에지가 $아닌$ 정점과 v의 하위 에지를 연결하는 에지는 없다 $u-v$ ^[4]

절차에서 가장자리가 처리될 때마다 가장자리의 끝점 중 하나가 한 단계씩 떨어진다.프로세스 B에 의해 종료된 실행에서 정점에 도달할 수 있는 최저 레벨은 $|V|-1$ - 1 ${\displaystyle$ V $-1}$ 이기 때문에 에지당 비용은 $2|V|$ $displaystyle 2V }$ 로 제한된다 $2|V|$ 따라서 삭제당 상각된 시간은 O $O(n)$ ( $O(n)$ ) ${\displaystyle$ O $(n)}$ 이다 $O(n)$

완전 동적 연결

반복 그래프(포리스트)

숲은 링크컷 나무나 오일러 관광 나무의 컬렉션을 사용하여 나타낼 수 있다.그러면 FindRoot(x)=FindRoot(y)가 아닌 경우에만 두 개의 노드 x,y,x가 y에 연결되는 것처럼 동적 연결 문제를 쉽게 해결할 수 있다.상각된 업데이트 시간과 쿼리 시간은 모두 O(log(n)이다.

일반 그래프

일반 그래프는 그래프의 연결된 모든 구성요소에 대해 트리를 포함하는 스패닝 포리스트로 나타낼 수 있다.우리는 이것을 F라고 부른다.F 그 자체는 오일러 관광 나무의 숲으로 대표될 수 있다.

Query and Insert 연산은 F를 나타내는 ET 트리에서 해당 연산을 사용하여 구현된다.어려운 작업은 Delete이며, 특히 F의 스패닝 트리 중 하나에 포함된 가장자리를 삭제하는 작업이다.이것은 신장 트리를 두 개의 나무로 쪼개지만, 그들을 연결하는 또 다른 가장자리가 있을 수 있다.과제는 그러한 대체적 우위성이 존재한다면 신속하게 찾아내는 것이다.이것은 좀 더 복잡한 데이터 구조를 필요로 한다.그러한 몇 가지 구조는 아래에 설명되어 있다.

레벨 구조

그래프의 각 가장자리에는 레벨이 할당된다.L=lg n으로 하자.그래프에 삽입된 각 에지의 레벨은 L로 초기화되며, 삭제 작업 중에 0으로 감소할 수 있다.

0과 L 사이의 각 i에 대해 Gi를 레벨 i 이하인 가장자리와 Fi의 스패닝 숲으로 구성된 하위 그래프로 정의한다.예전부터의 우리 숲 F는 지금 FL이라고 불린다.우리는 숲의 감소된 순서를 유지할 것이다. FL ⊇ ...⊇ F0. ^[5]^[6]

운영

쿼리 및 삽입 작업은 가장 큰 포리스트 FL만 사용한다.더 작은 서브그래프는 삭제 작업 중에만 참조되며, 특히 FL의 스패닝 트리 중 하나에 포함된 가장자리를 삭제한다.

이러한 에지 e = x-y가 삭제되면 먼저 FL 및 해당 에지가 속한 모든 작은 스패닝 포리스트(즉, i i 레벨(e)의 모든 Fi에서 제거된다.그럼 대체 엣지를 찾아보자.

fi with i = level(e)을 포함하는 가장 작은 스패닝 포리스트부터 시작하십시오.가장자리 e는 특정 트리 T tFi에 속한다.e를 삭제한 후 T나무는 다음과 같은 두 개의 작은 나무로 부러진다.노드 x를 포함하는 Tx와 노드 y를 포함하는 Ty.Tx의 노드와 Ty의 노드를 연결하는 경우에만 Gi의 에지가 대체 에지다.wlog가 Tx가 작은 트리라고 가정하자(즉, T의 노드가 절반 이상 포함되며, 오일러 트리에 추가된 주석을 통해 각 하위 트리의 크기를 알 수 있다).

모든 가장자리 ε과 레벨 i 및 Tx에서 최소 한 개의 노드를 반복한다.

만약 of의 다른 노드가 Ty에 있다면, 대체 에지가 발견된다!Fi 및 FL까지의 포리스트를 포함하는 모든 포리스트에 이 에지를 추가하고 마무리하십시오.스패닝 숲은 고정되어 있다.이 검색에 대한 비용을 지불하기 위해 검색 중에 방문한 가장자리 수준을 줄인다는 점에 유의하십시오.
만약 ε의 다른 노드가 Tx에 있다면, 이것은 대체 에지가 아니며, 시간을 낭비하는 것에 대해 '연쇄'하기 위해 우리는 그 레벨을 1로 줄인다.

분석

각 가장자리 수위는 최대 lg n배까지 낮아진다.왜냐고? 왜냐하면 각각의 감소와 함께, 그것은 이전 레벨에서 나무의 절반 크기인 나무로 떨어지기 때문이다.따라서 각 레벨 i에서는 연결된 각 구성 요소의 노드 수가 최대 2개ⁱ 입니다.따라서 가장자리의 수준은 항상 0 이상이다.

레벨이 감소된 각 에지는 $O(\lg n)$ $O(\lg n)$ ) $O(\lg n)$ 시간이 $O(\lg n)$ 소요된다(ET 트리 연산 사용).전체적으로 삽입된 각 에지는 삭제될 때까지 $O(\lg ^{2}n)$ $O(\lg ^{2}n)$ $O(\lg ^{2}n)$ ) $O(\lg ^{2}n)$ 시간이 $O(\lg ^{2}n)$ 소요되므로 상각된 삭제 시간은 O $O(\lg ^{2}n)$ $O(\lg ^{2}n)$ $O(\lg ^{2}n)$ ) ${\displaystyle$ O $(\lg ^{2}n)}$ 이다 $O(\lg ^{2}n)$ The remaining part of delete also takes $O(\lg ^{2}n)$ time, since we have to delete the edge from at most $O(\lg n)$ levels, and deleting from each level takes $O(\lg n)$ (again using the ET operations).

총 업데이트당 상각시간은 $O(\lg ^{2}n)$ ( $O(\lg ^{2}n)$ $O(\lg ^{2}n)$ $){\displaystyle O(\lg ^{2}n)}$ 입니다 $O(\lg ^{2}n)$ 조회당 시간은 $(lg$ $O(\lg n/\lg \lg n)$ n $O(\lg n/\lg \lg n)$ / $lg ⁡$ $O(\lg n/\lg \lg n)$ $lg$ $O(\lg n/\lg \lg n)$ )로 $개선$ 할 수 있다 $O(\lg n/\lg \lg n)$

그러나 업데이트당 최악의 시간은 $O(n)$ ) $O(n)$ 일 수 있다 $O(n)$ Cutset 구조에 의해 긍정으로 해결되기 전까지는 최악의 경우 시간을 개선할 수 있는지에 대한 문제는 공공연한 문제였다.

컷셋 구조

그래프 G(V,E)와 부분집합 TvV가 주어진 경우, 컷셋(T)을 V\T와 연결하는 에지 집합으로 정의한다.컷셋 구조는 전체 그래프를 메모리에 저장하지 않고, 그러한 에지가 존재할 경우 컷셋에서 엣지를 빠르게 찾을 수 있는 데이터 구조다.^[7]

각 꼭지점에 숫자를 주는 것부터 시작해라.정점이 없다고 가정하면, 각 정점은 lg(n)비트를 가진 숫자로 나타낼 수 있다.다음으로, 각 에지에 숫자를 부여하십시오. 에지는 정점의 숫자인 2lg(n) 비트를 가진 숫자의 결합이다.

각 꼭지점 v에 대해 인접한 모든 가장자리 숫자의 xor인 xor(v)를 계산하여 유지하십시오.

이제 각 부분집합 TvV에 대해, xor(T) = T에 있는 모든 정점 값의 xor를 계산할 수 있다.에지 e = T의 내부 에지인 u-v(u와 v 모두 T에 있음)를 고려하십시오.e의 수는 xor(T)에 두 번 포함되며, u의 경우 한 번, v의 경우 한 번 포함되며, 모든 숫자의 xor는 0이므로 e는 사라지며 xor(T)에 영향을 미치지 않는다.따라서 xor(T)는 실제로 컷셋(T)에서 모든 가장자리의 xor이다.다음과 같은 몇 가지 옵션이 있다.

xor(T)=0이면 cutset(T)이 비어 있다고 자신 있게 답할 수 있다.
xor(T)가 실제 에지 e의 숫자라면, 아마도 cutset(T)에서 e가 유일한 에지일 것이고, 우리는 e를 반환할 수 있다.e의 끝점을 e의 수에서 가장 왼쪽 비트와 가장 오른쪽 비트로 나누어 읽을 수도 있다.
세 번째 옵션은 xor(T)가 실제 에지를 나타내지 않는 0이 아닌 숫자라는 것이다.이는 컷셋(T)에 두 개 이상의 가장자리가 있을 때만 발생할 수 있는데, 이 경우 xor(T)는 여러 가장자리 수의 xor이기 때문이다.이 경우, 절단 세트에 가장자리가 있다는 것을 알고 있지만 단일 가장자리를 식별할 수 없기 때문에 "고장"을 보고한다.^[8]

지금 우리의 목표는 이 세 번째 옵션을 다루는 것이다.

먼저 컷셋 구조의 lg(n) 수준 시퀀스를 만들어 각각의 에지가 상위 레벨에서 절반 정도(즉, 각 레벨에 대해 확률 1/2로 상위 레벨에서 각 에지를 선택한다)를 포함한다.첫 번째 레벨 xor(T)에서 컷셋(T)에 두 개 이상의 에지가 있다는 의미의 잘못된 값이 반환되는 경우, 다음 레벨에서 더 적은 에지를 포함하는 xor(T)가 하나의 에지를 포함하므로 법적 값을 반환할 가능성이 있다.xor(T)가 여전히 잘못된 값을 반환하는 경우 다음 수준으로 계속 진행하십시오.가장자리 수가 감소하고 있기 때문에 다음과 같은 두 가지 경우가 있다.

좋은 경우는 결국 컷셋(T)이 하나의 가장자리를 포함하는 수준을 찾은 다음, 그 가장자리를 되돌려 마무리하는 것이다.
나쁜 경우는 결국 컷셋(T)에 엣지가 없는 수준을 찾아낸 다음, 컷셋에 엣지가 있다는 것을 알고 있지만 단 하나의 엣지를 식별할 수 없기 때문에 "실패"를 보고한다는 것이다.

성공 확률이 적어도 9분의 1은 된다는 것을 증명할 수 있다.

다음으로, C가 상수인 레벨 구조의 C lg(n) 독립 버전의 컬렉션을 생성한다.각 버전에서 레벨에서 레벨로 에지를 독립적으로 랜덤으로 줄이십시오.각 버전 중 하나가 성공할 때까지 각 버전에 대해 각 쿼리를 시도하십시오.모든 버전이 실패할 확률은 최대 다음과 같다.

(1-1/9)^{C\lg{n}=2^{-0.17C\lg{n}=n^{-0.17C}

C를 적절히 선택함으로써 우리는 임의로 실패 확률을 0에 가깝게 만들 수 있다.

운영

동적 연결 구조에 컷셋 구조를 추가할 수 있다.

절단 세트 구조의 삽입 및 삭제 작업은 정확히 동일한 방식으로 수행되며, 삽입/삭제된 가장자리가 양쪽 끝점에 XOR로 표시된다.

동적 연결 구조에 사용되는 스패닝 포리스트에서 가장자리가 삭제되면, 컷셋 구조를 사용하여 대체 가장자리를 찾는다.

분석

단일 컷셋 구조는 오직 O(n lg n) 메모리만 필요로 한다. 단 하나의 숫자로, 각 정점에는 2 lg n 비트가 있다.우리는 스스로 가장자리를 지킬 필요가 없다.밀도가 높은 그래프의 경우 전체 그래프를 메모리에 저장하는 것보다 훨씬 저렴하다.

우리는 lg(n) 수준을 각각 포함하는 lg(n) 버전을 유지해야 한다.따라서 총 메모리 요구 사항은 $O(n\lg ^{3}n)$ ( $O(n\lg ^{3}n)$ $O(n\lg ^{3}n)$ $O(n\lg ^{3}n)$ ⁡ $O(n\lg ^{3}n)$ ) $O(n\lg ^{3}n)$ 입니다 $O(n\lg ^{3}n)$

쿼리 시간은 최악의 경우 O(폴리로그(n))이다.이는 조회시간이 O(폴리로그(n) 상각되는 레벨 구조와 대조적이지만 최악의 경우 O(n)이다.

오프라인 동적 연결

에지가 삭제되는 순서를 미리 알고 있다면 조회당 로그(n)로 동적 연결 문제를 해결할 수 있다.가장자리가 삭제 시간으로 정렬되는 최대 스패닝 포리스트를 유지할 수 있다면, 포리스트에 있는 일부 가장자리를 삭제할 때 이를 대체할 수 있는 가장자리가 없다는 것을 알 수 있다.삭제된 가장자리가 하는 것과 동일한 두 구성 요소를 연결하는 가장자리가 있다면 이 다른 가장자리는 우리가 삭제한 가장자리 대신 최대 스패닝 포리스트의 일부가 되었을 것이다.이것은 삭제 작업을 사소한 것으로 만든다: 우리는 단지 삭제할 가장자리가 포리스트의 일부인 경우 트리를 두 부분으로 나누거나, 그렇지 않은 경우 작업을 무시하면 된다.

가장자리를 추가하는 것은 약간 더 복잡하다.u에서 v로 에지 e를 추가하면 u와 v가 연결되지 않은 경우 이 에지는 최대 스패닝 포리스트의 일부가 된다.만약 그것들이 연결되어 있다면, 우리는 우리의 최대 스패닝 포리스트를 개선할 수 있다면, u->v를 우리의 숲에 추가하고 싶다.이를 위해서는 u에서 v로 가는 경로에서 어느 가장자리 제거시간이 가장 작은지 빨리 확인해야 한다. e의 제거시간이 e의 제거시간 이후라면 e는 우리의 최소 스패닝 포리스트를 개선할 수 없다.그렇지 않으면 다른 가장자리를 삭제하고 e로 교체해야 한다.

이를 위해서는 엣지 추가, 엣지 절단, 경로의 최소 엣지 쿼리 등 작업당 log(n)에 있는 링크 컷 트리로 다소 쉽게 할 수 있는 작업을 해야 한다.

참고 항목

참조

^ Tarjan, Robert Endre (1975). "Efficiency of a Good But Not Linear Set Union Algorithm". Journal of the ACM. 22 (2): 215–225. CiteSeerX 10.1.1.399.6704. doi:10.1145/321879.321884.
^ Tarjan, Robert Endre (1979). "A class of algorithms which require non-linear time to maintain disjoint sets". Journal of Computer and System Sciences. 18 (2): 110–127. doi:10.1016/0022-0000(79)90042-4.
^ Shiloach, Y.; Even, S. (1981). "An On-Line Edge-Deletion Problem". Journal of the ACM. 28: 1–4. doi:10.1145/322234.322235.
^ 전체 구조를 복사할 필요 없이 e의 삭제 전 구조로 복귀하는 것을 실현하는 한 가지 방법은 e의 삭제 이후 BFS 구조에서 일어난 모든 변경 사항을 한 무더기 쌓아두고 하나씩 되돌리는 것이다.이렇게 하면 처리 시간에 상수만 곱해진다.
^ Holm, J.; De Lichtenberg, K.; Thorup, M. (2001). "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity". Journal of the ACM. 48 (4): 723. doi:10.1145/502090.502095.
^ 동적 그래프 문제 - 고급 데이터 구조의 강의 노트에서.에릭 데메인 교수; 스크리브: 캐서린 라이.
^ Kapron, B. M.; King, V.; Mountjoy, B. (2013). Dynamic graph connectivity in polylogarithmic worst case time. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1131. doi:10.1137/1.9781611973105.81. ISBN 978-1-61197-251-1.
^ 몇 개의 다른 가장자리의 xor가 다른 가장자리의 숫자로 나타나는 결과를 초래할 가능성은 작다.이것은 잘못된 긍정으로 이어질 수 있다.이 사건의 확률을 줄이기 위해서, 우리는 정점 수의 영역을 n 대신에 n으로³ 확대할 수 있다.그렇다면, 컷셋(T)에 둘 이상의 에지가 있다면, 위에서 말한 것처럼 xor(T)는 거의 확실히 무의미한 값이 될 것이다.

참고 항목:

[tarjan1975-1] Tarjan, Robert Endre (1975). "Efficiency of a Good But Not Linear Set Union Algorithm". Journal of the ACM. 22 (2): 215–225. CiteSeerX 10.1.1.399.6704. doi:10.1145/321879.321884.

[Tarjan1979-2] Tarjan, Robert Endre (1979). "A class of algorithms which require non-linear time to maintain disjoint sets". Journal of Computer and System Sciences. 18 (2): 110–127. doi:10.1016/0022-0000(79)90042-4.

[3] Shiloach, Y.; Even, S. (1981). "An On-Line Edge-Deletion Problem". Journal of the ACM. 28: 1–4. doi:10.1145/322234.322235.

[4] 전체 구조를 복사할 필요 없이 e의 삭제 전 구조로 복귀하는 것을 실현하는 한 가지 방법은 e의 삭제 이후 BFS 구조에서 일어난 모든 변경 사항을 한 무더기 쌓아두고 하나씩 되돌리는 것이다.이렇게 하면 처리 시간에 상수만 곱해진다.

[5] Holm, J.; De Lichtenberg, K.; Thorup, M. (2001). "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity". Journal of the ACM. 48 (4): 723. doi:10.1145/502090.502095.

[6] 동적 그래프 문제 - 고급 데이터 구조의 강의 노트에서.에릭 데메인 교수; 스크리브: 캐서린 라이.

[7] Kapron, B. M.; King, V.; Mountjoy, B. (2013). Dynamic graph connectivity in polylogarithmic worst case time. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1131. doi:10.1137/1.9781611973105.81. ISBN 978-1-61197-251-1.

[8] 몇 개의 다른 가장자리의 xor가 다른 가장자리의 숫자로 나타나는 결과를 초래할 가능성은 작다.이것은 잘못된 긍정으로 이어질 수 있다.이 사건의 확률을 줄이기 위해서, 우리는 정점 수의 영역을 n 대신에 n으로³ 확대할 수 있다.그렇다면, 컷셋(T)에 둘 이상의 에지가 있다면, 위에서 말한 것처럼 xor(T)는 거의 확실히 무의미한 값이 될 것이다.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Search

동적 연결

네임스페이스

더

목차

증분 연결

노쇠 연결성

반복 그래프(포리스트)

일반 그래프

완전 동적 연결

반복 그래프(포리스트)

일반 그래프

레벨 구조

운영

분석

컷셋 구조

운영

분석

오프라인 동적 연결

참고 항목

참조