도달성

그래프 이론에서 도달성은 그래프 안에서 한 꼭지점에서 다른 꼭지점으로 이동하는 능력을 가리킨다. $s$ ${\displaystyle s$ $}($ 으 $s$ )로 시작하고 t {\ $displaystyle$ s $t$ 으)로 끝나는 인접 정점(즉, 걷기)이 있는 경우 정점 $s$ ${\$ $displaystyle t}($ 으 $s$ 는 $t$ $s$ 에 $도달$ 할 수 있다.

비방향 그래프에서 모든 꼭지점 쌍 사이의 도달성은 그래프의 연결된 구성요소를 식별하여 결정할 수 있다.이러한 그래프의 정점 쌍은 동일한 연결 구성요소에 속하는 경우에만 서로 도달할 수 있으므로, $이러한$ 그래프에서 도달 가능성은 대칭(f ${\$ $displaystyle$ $t}$ 이(가 $t$ ) t ${\displaystyle$ t $}$ 에 도달하면 $t$ $t$ ${\displaystyle$ $t$ $}$ 에 $s$ 도달함)이다. $s$ 비방향 그래프의 연결된 구성요소는 선형 시간으로 식별할 수 있다.이 글의 나머지 부분은 지시된 그래프에서 쌍의 도달 가능성을 결정하는 데 있어 더 어려운 문제에 초점을 맞추고 있다(이 문제는 우발적으로 대칭이 될 필요는 없다).

정의

For a directed graph $G=(V,E)$ , with vertex set $V$ and edge set $E$ , the reachability relation of $G$ is the transitive closure of $E$ , which is to say the set of all ordered pairs ${\displaystyle (s,t)$ $}$ of vertices in $V$ for which there exists a sequence of vertices $v_{0}=s,v_{1},v_{2},...,v_{k}=t$ such that the edge $(v_{i-1},v_{i})$ is in $E$ for all ${\di$ $splaystyle 1\leq$ i $\leq k$ ^[1]

$G$ $G$ 이(가) 반복적인 $G$ 경우, 그 도달성 관계는 부분적인 순서가 된다. 예를 들어, 모든 부분 순서는 이러한 방식으로 정의될 수 있다.^[2] $t$ 서 주목할 만한 결과는 $부분$ 순서가 대칭성이므로 s ${\displaystyle$ s $}$ 이(가 $t$ $t$ $t$ 에 도달할 수 있다면 $s$ t ${\displaystyle$ $t$ $}$ 이(가) $s$ ${\$ $displaystyle$ s $}$ 에 $s$ $t$ 도달할 수 없다는 것을 우리는 $t$ 직감적으로 알고 있다 $.$ $s$ ${\displaystyle s$ 그러면 $G$ ${\displaystyle$ G $}$ 이(가) 순환이라는 것을 부정하는 주기를 포함할 것이다 $G$ . $G$ $G$ 이 $G$ (가) 방향은 맞지만 시계열(즉, 적어도 하나의 사이클을 포함)이 아닌 경우, 도달성 관계는 부분 순서가 아닌 사전 순서에 해당된다.^[3]

알고리즘

도달 가능성을 결정하기 위한 알고리즘은 사전 처리가 필요한 것과 그렇지 않은 것의 두 종류로 나뉜다.

쿼리가 하나(또는 몇 개)밖에 없는 경우, 더 복잡한 데이터 구조를 사용하지 않고 원하는 쌍의 도달 가능성을 직접 계산하는 것이 더 효율적일 수 있다.이는 너비 퍼스트 검색이나 반복 심층 퍼스트 검색과 같은 알고리즘을 사용하여 선형 시간 내에 달성될 수 있다.^[4]

많은 쿼리를 할 경우 좀 더 정교한 방법을 사용할 수 있다. 정확한 방법 선택은 분석 중인 그래프의 특성에 따라 달라진다.사전 처리 시간과 일부 추가 스토리지 공간과의 교환으로, $O(1)$ ( $O(1)$ ) $O(1)$ 시간 $O(1)$ 내에 정점 쌍에 대한 도달 가능성 쿼리에 응답할 수 있는 데이터 구조를 생성할 수 있다.세 가지 서로 다른, 점점 더 전문화된 상황에 대한 세 가지 알고리즘과 데이터 구조가 아래에 요약되어 있다.

플로이드-워셸 알고리즘

플로이드-워셸 알고리즘은^[5] 위 정의에서와 같이 도달성 관계를 발생시키는 지시된 그래프의 전이성 폐쇄를 계산하는 데 사용할 수 있다.

알고리즘에는 최악의 경우 $O(|V|^{3})$ $O(|V|^{3})$ ) ${\displaystyle$ O( $V$ ^{ $3})$ 시간 $O(|V|^{3})$ $O(|V|^{2})$ O( $O(|V|^{2})$ 2 $O(|V|^{2})$ ) ${\displaystyle O(V$ ^{ $2})$ 공간이 $O(|V|^{2})$ 필요하다.이 알고리즘은 모든 정점 쌍 사이의 최단 경로 거리도 계산하기 때문에 도달성에만 관심이 있는 것은 아니다.음의 주기를 포함하는 그래프의 경우 최단 경로가 정의되지 않을 수 있지만 쌍 간의 도달 가능성은 여전히 기록될 수 있다.

토럽 알고리즘

평면 디그래프의 경우 2004년 Mikkel Thorup이 설명한 것처럼 훨씬 빠른 방법을 사용할 수 있다.^[6] $O(n\log {n})$ 방법은 $O(n\log {n})$ $O(n\log {n})$ $O(n\log {n})$ $O(n\log {n})$ ) ${\displaystyle O(n\log {n})$ 사전 처리 $O(n\log {n})$ 시간을 소비한 후 평면 그래프의 도달 가능성 쿼리에 $O(1)$ O $($ $O(1)$ ){\ $displaystyle$ O $n$ ) ${\$ displaystystyle O(n $\$ $log {n}})$ 크기의 $O(n\log {n})$ 데이터 구조를 생성하는 데 걸리는 시간을 {n $}$ 시간으로 $O(1)$ 응답할 수 있다.이 알고리즘은 경로 정보뿐만 아니라 대략적인 최단 경로 거리도 제공할 수 있다.

전체적인 접근방식은 정점 $v$ $v$ 에서 $다른$ 정점 w $w$ 에 이르는 $v$ $모든$ 경로가v {\ $displaystyle v}$ 또는 $v$ $w$ $w$ 과(와) 관련된 최소 하나의 분리자를 통과하도록 $w$ 비교적 작은 소위 분리 경로 집합을 각 정점과 연결하는 것이다 $w$ 개요다음과 같은 도달성 관련 섹션.

그래프 $G$ $G$ 을 $G$ 를) 지정하면 알고리즘은 정점을 임의 $v_{0}$ v $v_{0}$ {\ $displaystyle$ v_{ $0}$ 부터 시작하는 계층으로 구성함으로써 시작한다 $v_{0}$ 레이어는 먼저 이전 단계( $v_{0}$ $v_{0}$ ${\$ 만으로 시작 $v_{0}$ 에서 도달할 수 있는 모든 정점과 모든 정점이 레이어에 할당될 때까지 이전 단계에 도달하는 모든 정점을 고려하여 교대로 구축된다.층의 구성에 의해 모든 꼭지점이 최대 2개 층으로 나타나며, $G$ $G$ 의 모든 방향 경로, 즉 dipath는 두 개의 인접한 $L_{i}$ L $L_{i}$ ${\$ 과 $L_i$ L + $L_{i+1}$ {\ $displaystyle L_{i+1$ } 사이에 포함된다 $G$ $L_{i+1}$ $k$ $k$ 을(를) 마지막으로 생성된 레이어, 즉 $\bigcup _{i=0}^{k}L_{i}=V$ i = $\bigcup _{i=0}^{k}L_{i}=V$ i = $\bigcup _{i=0}^{k}L_{i}=V$ {\ $displaystyle \bigcup _{i=0}^{k$ )와 $k$ $같은$ k ${\displaystystyk k}$ 에 대해 가장 낮은 값으로 설정 $k$ $}}L_{i}=V}$ .

The graph is then re-expressed as a series of digraphs $G_{0},G_{1},\ldots ,G_{k-1}$ where each $G_{i}=r_{i}\cup L_{i}\cup L_{i+1}$ and where $r_{i}$ is the contraction of all previous levels $L_{0}\ldots L_{i-1}$ $L_{0}\ldots L_{i-1}$ … $L_{0}\ldots L_{i-1}$ $L_{0}\ldots L_{i-1}$ - $L_{0}\ldots L_{i-1}$ ${\$ 하나의 $L_{0}\ldots L_{i-1}$ 꼭지점으로.모든 dipath가 최대 두 개의 연속 레이어에 나타나며, 각 $G_{i}$ ${\$ 가 두 개의 연속 레이어에 의해 형성되기 $G_{i}$ 때문에, $G$ {\ $displaystyle$ $G_{i}($ 그리고 연속된 그래프 2개 이하)의 모든 dipath가 적어도 하나의 $G_{i}$ ${\$ G $}$ 에 전체적으로 나타나기 때문이다 $G$ .

각 $G_{i}$ ${\$ 에 대해 세 개의 구분자를 식별하여 제거할 때 그래프를 각각 $1/2$ 의 정점 $1/2$ 1 / $1/2$ {\ $displaystyle 1/2}$ 을(를) 포함하는 세 개의 구성요소로 구분한다. $G_{i}$ ${\$ 는 두 개의 반대되는 dipath 층에서 제작되므로 $G_{i}$ , 각 분리기는 최대 2개의 dipath로 구성될 수 있으며, 모든 분리자에 대해 최대 6개의 dipath로 구성될 수 있다. $S$ $S$ 을(를) 이러한 이중 경로 집합으로 $S$ 두십시오.그러한 분리기들을 항상 찾을 수 있다는 증거는 립톤과 타르잔의 평면 분리기 정리(Planar Separator Organization of Lipton and Tarjan)와 관련이 있으며, 이러한 분리기들은 선형 시간에 위치할 수 있다.

각 $Q\in S$ $Q\in S$ $Q\in S$ $Q\in S$ 에 대해 $Q$ $Q$ 의 방향 특성은 경로의 시작부터 끝까지 정점의 자연 인덱싱을 제공한다 $Q$ $Q\in S$ $G_{i}$ ${\$ 의 $v$ 각 $꼭지점$ v ${\$ $displaystyle$ v $}$ 에 대해 $v$ ${\displaystyle$ $v$ $v$ 에 도달할 $Q$ 수 있는 $Q$ ${\displaystyle Q$ $}$ 의 첫 번째 꼭지점 $및$ v {\ $displaystytyle$ v}에 $Q$ $Q$ 하는 Q {\stytime}을 찾고 있다 $v$ 즉, $Q$ ${\displaysty}$ $v$ ${\displaystyle$ v $v$ 에서 얻을 수 있으며 $Q$ $Q$ 에 $Q$ 머무르고도 $v$ {\ $displaystyle v}$ 으로 돌아갈 수 있는 범위 $v$ 이 정보는 각 $v$ $v$ 과(와) 함께 저장된다 $v$ 그런 다음 정점 $u$ ${\displaystyle$ $u$ $}$ 과 $u$ w ${\displaystyle$ w $}$ 의 쌍에 대해, $w$ $u$ $u$ 이(가) $Q$ $Q$ 에서 $Q$ $w$ ${\displaystystyle u}$ 을( $Q$ ) 연결한 $Q$ $경우$ Q ${\$ $displaystystystyp$ )를 통해 $w$ $w}$ 에 도달할 수 있다 $u$ $Q$

$G_{0}\ldots ,G_{k}$ 꼭지점은 G $G_{0}\ldots ,G_{k}$ … $G_{0}\ldots ,G_{k}$ , $G_{0}\ldots ,G_{k}$ $G_{0}\ldots ,G_{k}$ ${\$ 을(를) 구축하는 재귀의 각 단계에 대해 위와 같이 라벨을 붙인다 $G_{0}\ldots ,G_{k}$ 이 재귀에는 로그 깊이가 있기 때문에 정점당 총 $O(\log {n})$ log $){\displaystystyle O(\log {n})$ 의 추가 정보가 $O(\log {n})$ 저장된다.이 시점부터, 도달 가능성에 대한 로그 시간 질의가 공통적이고 적절한 Q $Q$ 에 대한 각 라벨 쌍을 훑어보는 것만큼 간단하다 $Q$ 그러면 원본 용지는 조회 시간을 $O(1)$ ( $O(1)$ ) $O(1)$ 까지 조정하는 작업을 한다 $O(1)$

이 방법의 분석을 요약할 때, 우선 계층화 접근법이 정점을 분할하여 각 $O(1)$ 이 $O(1)$ O ( $){\displaystyle O$ (1)만 $O(1)$ 간주되도록 한다는 점을 고려한다.알고리즘의 분리기 단계는 그래프를 원래 그래프 크기의 1/ $[\displaystyle$ 1/ $2]$ 의 $1/2$ 구성 요소로 분할하여 로그 재귀 깊이를 산출한다.각 반복 수준에서 정점 사이의 연결은 물론 분리기를 식별하기 위한 선형 작업만 필요하다.전체 결과는 $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ ) ${\displaystyle O(n\log$ n $)}$ 사전 처리 $O(n\log n)$ 시간으로, 각 정점에 대해 저장된 O $O(\log {n})$ ) ${\displaystyle O(\log {n})$ 추가 $O(\log {n})$ 정보만 저장된다.

카메다의 알고리즘

s

s

및

t

s

t

이(가) 추가된

t

Kameda의 방법에 적합한 디그라프.

각 정점에 대한 DFS 레이블을 표시하는 Kameda 알고리즘이 실행된 후 위와 동일한 그래프

An even faster method for pre-processing, due to T. Kameda in 1975,^[7] can be used if the graph is planar, acyclic, and also exhibits the following additional properties: all 0-indegree and all 0-outdegree vertices appear on the same face (often assumed to be the outer face), and it is possible to partition the boundary of that face into two parts such 모든 0-높은 정점이 한 부분에 나타나고, 모든 0-outdo 정점이 다른 부분에 나타난다(즉, 두 가지 유형의 정점이 번갈아 나타나지 않음).

If $G$ exhibits these properties, then we can preprocess the graph in only $O(n)$ time, and store only $O(\log {n})$ extra bits per vertex, answering reachability queries for any pair of vertices in $O(1)$ time with a simple com패리슨

사전 처리가 다음 단계를 수행하십시오.각 0-인덱스 정점에 에지가 $s$ 있는 새 $정점$ s {\ $displaystyle s}$ 과(와) 각 0-도 정점으로부터 에지가 있는 $t$ 새로운 정점 $t$ ${\displaystyt$ t}을 $($ 를) 추가한다. $G$ $G$ 의 속성은 평면성을 유지하면서 그렇게 할 수 $G$ 있다는 점에 유의하십시오. 즉, 이러한 추가 후에도 에지 교차가 없을 것이다.각 꼭지점에 대해 그래프의 평면성(예: 그래프의 내장 관련 시계 방향) 순서대로 보조성(아웃-에지) 목록을 저장한다.그런 다음 카운터 $i=n+1$ = $i=n+1$ + $i=n+1$ ${\displaystyle i=n+1$ }을 $($ 를) 초기화하고 $i=n+1$ s $s$ 에서 Depth-First Traversal을 시작한다 $s$ 이 트래버설 동안 각 꼭지점의 인접 목록이 필요에 따라 왼쪽에서 오른쪽으로 방문된다.통과 스택에서 정점이 튀어나오면 $i$ ${\displaystyle$ i $}$ 값이 $표시$ 된 다음 $i$ i $i$ 이(가) 감소한다 $i$ . $t$ $t$ 은 $t$ (는) $n+1$ n $n+1$ + 1 $n+1$ 값으로 $s$ 을 $n+1$ 표시하며 s $s$ 은(는) 항상 $0$ $0$ 으로 라벨을 표시한다는 $s$ 점에 유의하십시오 $0$ 그런 다음 깊이 첫 번째 횡단을 반복하지만, 이번에는 각 정점의 인접 목록을 오른쪽에서 왼쪽으로 방문한다.

완료되면 $s$ $s$ 및 $s$ $t$ $t$ 및 해당 입사 모서리가 제거된다.Each remaining vertex stores a 2-dimensional label with values from $1$ to $n$ . Given two vertices $u$ and $v$ , and their labels $L(u)=(a_{1},a_{2})$ and ${\displ$ Aystyle L(v)=(b_{1},b_{2})}, 우리는 나는<(u), 나는(v){\displaystyle L(u)<, L(v)}만일 1≤ b1{\displaystyle a_{1}\leq b_{1}}2≤ b2{\displaystyle a_{2}\leq b_{2}}, 적어도 한 요소 1{\displaystyle a_{1}}또는 2{\displaystyle a_{2}}존재한다고 말한다.which는 각각 b $b_{1}$ ${\$ 또는 $b_{1}$ $b_{2}$ $b_{2}$ ${\$ }}개 미만이다 $b_{2}$

$O(1)$ 방법의 주요 결과는 $O(1)$ ( $O(1)$ $L(u)<L(v)$ ) < $L(u)<L(v)$ ( $L(u)<L(v)$ $displaystyle$ u $}$ ${\displaystyle$ L( $u){\displaystyle$ $O(1)$ 시간 $O(1)$ 단위로 쉽게 $L(u)<L(v)$ 계산되는 경우에만 $u$ $v$ $u$ 에서 v {\ $displaystystyle$ u $}$ 에 도달할 수 있다고 $v$ 명시한다.

참고 항목

참조

^ Skiena, Steven S. (2011), "15.5 Transitive Closure and Reduction", The Algorithm Design Manual (2nd ed.), Springer, pp. 495–497, ISBN 9781848000698.
^ Cohn, Paul Moritz (2003), Basic Algebra: Groups, Rings, and Fields, Springer, p. 17, ISBN 9781852335878.
^ Schmidt, Gunther (2010), Relational Mathematics, Encyclopedia of Mathematics and Its Applications, vol. 132, Cambridge University Press, p. 77, ISBN 9780521762687.
^ Gersting, Judith L. (2006), Mathematical Structures for Computer Science (6th ed.), Macmillan, p. 519, ISBN 9780716768647.
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Transitive closure of a directed graph", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 632–634, ISBN 0-262-03293-7.
^ Thorup, Mikkel (2004), "Compact oracles for reachability and approximate distances in planar digraphs", Journal of the ACM, 51 (6): 993–1024, doi:10.1145/1039488.1039493, MR 2145261, S2CID 18864647.
^ Kameda, T (1975), "On the vector representation of the reachability in planar directed graphs", Information Processing Letters, 3 (3): 75–77, doi:10.1016/0020-0190(75)90019-8.
^ Demetrescu, Camil; Thorup, Mikkel; Chowdhury, Rezaul Alam; Ramachandran, Vijaya (2008), "Oracles for distances avoiding a failed node or link", SIAM Journal on Computing, 37 (5): 1299–1318, CiteSeerX 10.1.1.329.5435, doi:10.1137/S0097539705429847, MR 2386269.
^ Halftermeyer, Pierre, Connectivity in Networks and Compact Labeling Schemes for Emergency Planning, Universite de Bordeaux.

[skiena-1] Skiena, Steven S. (2011), "15.5 Transitive Closure and Reduction", The Algorithm Design Manual (2nd ed.), Springer, pp. 495–497, ISBN 9781848000698.

[2] Cohn, Paul Moritz (2003), Basic Algebra: Groups, Rings, and Fields, Springer, p. 17, ISBN 9781852335878.

[3] Schmidt, Gunther (2010), Relational Mathematics, Encyclopedia of Mathematics and Its Applications, vol. 132, Cambridge University Press, p. 77, ISBN 9780521762687.

[4] Gersting, Judith L. (2006), Mathematical Structures for Computer Science (6th ed.), Macmillan, p. 519, ISBN 9780716768647.

[5] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Transitive closure of a directed graph", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 632–634, ISBN 0-262-03293-7.

[6] Thorup, Mikkel (2004), "Compact oracles for reachability and approximate distances in planar digraphs", Journal of the ACM, 51 (6): 993–1024, doi:10.1145/1039488.1039493, MR 2145261, S2CID 18864647.

[7] Kameda, T (1975), "On the vector representation of the reachability in planar directed graphs", Information Processing Letters, 3 (3): 75–77, doi:10.1016/0020-0190(75)90019-8.

[8] Demetrescu, Camil; Thorup, Mikkel; Chowdhury, Rezaul Alam; Ramachandran, Vijaya (2008), "Oracles for distances avoiding a failed node or link", SIAM Journal on Computing, 37 (5): 1299–1318, CiteSeerX 10.1.1.329.5435, doi:10.1137/S0097539705429847, MR 2386269.

[9] Halftermeyer, Pierre, Connectivity in Networks and Compact Labeling Schemes for Emergency Planning, Universite de Bordeaux.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Search

도달성

네임스페이스

더

목차

정의

알고리즘

플로이드-워셸 알고리즘

토럽 알고리즘

카메다의 알고리즘

관련 문제

참고 항목

참조