강한 연결 요소 - 위키백과, 우리 모두의 백과사전 강한 연결 요소 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 그래프에 강한 연결 요소를 표시한 모습 유향 그래프에서 모든 정점이 모든 다른 정점에 대해 도달 가능한 경우, 그래프는 강하게 연결되었다 또는 상호연결되었다라고 한다. 강한 연결 요소 또는 상호연결요소는 부분 그래프의 모든 정점이 강하게 연결된 임의의 유향그래프의 분할이다. 그래프가 강하게 연결 되었는지와 그래프에서 강한 연결 요소를 찾는것은 선형 시간 ( [UNK] ( VE ) ( VE ) ) 에 가능하다. 목차 1 정의 2 알고리즘 2. 1 DFS 기반 선형 시간 알고리즘 2. 2 도달 가능성 기반 알고리즘 3 강한 연결요소의 활용 4 관련된 결과들 5 같이 보기 6 각주 7 외부 링크 정의 [ 편집 ] 유향 그래프에서
3 강한 연결요소의 활용 4 관련된 결과들 5 같이 보기 6 각주 7 외부 링크 정의 [ 편집 ] 유향 그래프에서 그래프 상의 각 정점 쌍에 사이에 경로가 존재하는 경우 그래프는 강하게 연결되었다라고 한다. 이것은 한쌍의 정점 중 첫번째 정점에서 두번째 정점으로의 경로가 존재하고, 두번째 정점에서 첫번째 정점으로 가는 다른 경로가 존재한다는 것이다. 유향 그래프 G 가 강하게 연결되지 않은 경우에도 한 쌍의 정점 u 와 v 에 대해 그들 사이에 서로에게 가는 경로가 있으면 정점 u 와 v 는 강하게 연결되었다고 할 수 있다. 강하게 연결된 정점 쌍에서 경로의 존재에 대한 이항관계는 동치 관계이며, 동치류의 유도된 부분 그래프를 강한 연결 요소라고 부른다. 다르게 표현하면, 유향 그래프 G 의 강한 연결
순환 유향 그래프이며, 이를 G 의 응축이라고 한다. 유향 그래프는 강하게 연결된 부분 그래프가 없을 때만 순환이 없을 수 있는데, 왜냐하면 유향 순환은 강하게 연결되어있고 모든 강한 연결 요소는 적어도 하나의 유향 순환을 포함하기 때문이다. 알고리즘 [ 편집 ] DFS 기반 선형 시간 알고리즘 [ 편집 ] 깊이 우선 탐색을 기반으로 하는 몇가지 알고리즘들은 선형 시간에 강한 연결 요소들을 계산할 수 있다. 코사라주의 알고리즘은 두번의 깊이 우선 탐색을 거친다. 첫번째 탐색은 원본 그래프에서 두번째 깊이 우선 탐색의 외부 루프에서 방문된 점들을 테스트하고 방문되지 않은 점들을 재귀적으로 방문하는 정점의 순서를 정하는데 사용된다. 두 번째 깊이 우선 탐색은 원본 그래프의 역방향 그래프에서 진행되며, 재귀적 탐색으로 새로운 강한
강한 연결 요소가 부분 집합중 하나에 포함되어에 함을 보일 수 있다. 각 검색들을 통해 도출한 정점 부분 집합은 강한 연결 요소를 형성하고, 알고리즘은 다른 3개의 부분집합에 대해서 재귀적으로 해를 구하게 된다. 예상되는 이 알고리즘의 순차 실행 시간은 기존의 알고리즘에 O ( log n ) 의 요소가 추가된 O ( n log n ) 이다. 그러나 도달 가능성 쿼리는 병렬화 되기가 더 쉬우며 ( 예를 들어 너비 우선 탐색를 통하여, 그리고 그래프의 지름이 작으면 빨라질 수 있다는 점에서 ), 분할 정복 과정에서 부분 문제들 간의 독립성에 의해 이 알고리즘은 병렬성을 갖게 된다. 이 알고리즘을 실세계 ( real - world ) 그래프에서 잘 수행된다. [ 6 ] 그러나 병렬성으로 인한 이론적인 이득은 없다 ( 그래프에 간선이 없는 경우
그래프에서 잘 수행된다. [ 6 ] 그러나 병렬성으로 인한 이론적인 이득은 없다 ( 그래프에 간선이 없는 경우를 고려해 보면, 알고리즘은 O ( n ) ( n ) 단계의 재귀를 필요로 한다 ). Blelloch 등은 [ 7 ] 2016년에 무작위적인 순서의 도달 가능성 쿼리는 여전히 O ( n log n ) 의 비용을 갖는다는것을 보였다. 또한, 접두사 두배의 방식의 ( 즉, 1, 2, 4, 8 쿼리 ) 쿼리들이 일괄처리될 수 있고, 한 라운드에서 동시에 실행된다. 이 알고리즘의 총 범위는 log2 n 개의 연결 쿼리들인데, 이것은 도달 가능성 기반 접근법을 사용하여 달성 할 수있는 최적의 병렬 처리 일 것이다. 강한 연결요소의 활용 [ 편집 ] 강한 연결 요소를 찾기 위한 알고리즘은 2
있는 최적의 병렬 처리 일 것이다. 강한 연결요소의 활용 [ 편집 ] 강한 연결 요소를 찾기 위한 알고리즘은 2 - 충족 가능성 ( 변수 쌍의 값에 대한 제약 조건이있는 부울 변수의 시스템 ) 문제를 해결하는데 사용될 수 있다. Aspvall, Plass & Tarjan ( 1979 ) 은 v와 v의 대칭 요소가 인스턴스의 함축 그래프의 같은 강한 연결 요소에 포함된 변수 v가 존재할 때만 2 - 충족 가능성 인스턴스가 충족 가능하지 않다는 것을 밝혀내었다. [ 8 ] 강하게 연결된 요소들은 또한 둘메이지 - 멘델슨 분해를 계산하는데 사용될 수 있는데, 이분 그래프의 간선들의 분류는, 그래프에서 그들이 완벽 부합의 부분이 될 수 있는지에 따르기 때문이다. [ 9 ] 관련된 결과들 [ 편집 ] 유향 그래프
gly connected components in parallel. IPDPS 2000. ↑ Hong, Sungpack ; Rodia, Nicole C ; and Olukotun, Kunle. On fast parallel detection of strongly connected components ( SCC ) in small - world graphs Archived 2017년 8월 8일 - 웨이백 머신. SC 2013. ↑ Blelloch, Guy ; Gu, Yan ; Shun, Julian ; and Sun, Yihan. Parallelism in Randomized Incremental Algorithms. SPAA 2016. doi : 10. 1145 / 2935764. 2935766. ↑ Aspvall, Bengt ; Plass, Michael F. ; Tarjan,
and Mathematics with Applications 7 ( 1 ) : 67 - 72, 1981. ↑ Tarjan, R. E. ( 1972 ), " Depth - first search and linear graph algorithms ", 《 SIAM Journal on Computing 》 1 ( 2 ) : 146 - 160, doi : 10. 1137 / 0201010 ↑ Dijkstra, Edsger ( 1976 ), 《 A Discipline of Programming 》, NJ : Prentice Hall, Ch. 25. ↑ Fleischer, Lisa K ; Hendrickson, Bruce ; and Pinar, Ali. On identifying strongly connected components in parallel. IPDPS 2000. ↑ Hong, Sungpack ;
4, doi : 10. 4153 / cjm - 1958 - 052 - 0. ↑ Robbins, H. E. ( 1939 ), " A theorem on graphs, with an application to a problem on traffic control ", 《 American Mathematical Monthly 》 46 : 281 - 283, JSTOR 2303897, doi : 10. 2307 / 2303897. 외부 링크 [ 편집 ] Java 를 통한 강한 연결 구성 요소의 계산 구현, jBPT 라이브러리로 구현함 ( StronglyConnectedComponents 클래스 ). C을 통한 강한 연결 구성 요소의 구현 원본 주소 " " 분류 : 알고리즘컴퓨터 과학 둘러보기 메뉴 개인 도구 로그인하지 않음토론기여계정 만들기로그인 이름공간 문서토론 변수 보기 읽기편
의 탐색을 필요로 한다. 도달 가능성 기반 알고리즘 [ 편집 ] 이전 선형 시간 알고리즘들은 일반적으로 병렬화하기 어려운 깊이 우선 탐색을 기반으로 한다. 피셔 등은 [ 5 ] 2000년에 도달 가능성 쿼리를 기반으로 한 분할 정복 접근 방식을 제안하였고, 이러한 알고리즘은 일반적으로 도달 가능성 기반 강한 연결 요소 알고리즘으로 불리게 되었다. 이러한 접근의 아이디어는 무작위적으로 피봇 정점을 뽑고, 이 정점에 대해 앞뒤 방향으로 도달 가능성 쿼리를 적용하는 것이다. 두개의 쿼리는 정점들의 집합을 서로에게 도달 가능한 것, 한 방향으로만 도달 가능한것 ( 2개 ), 도달 가능하지 않은 것의 4개의 부분 집합으로 분할한다. 이렇게 강한 연결 요소가 부분 집합중 하나에 포함되어에 함을 보일 수 있다. 각 검색들을 통해 도출한 정점 부분 집합
유향 그래프에서 모든 정점이 모든 다른 정점에 대해 도달 가능한 경우, 그래프는 강하게 연결되었다 또는 상호연결되었다라고 한다. 강한 연결 요소 또는 상호연결요소는 부분 그래프의 모든 정점이 강하게 연결된 임의의 유향그래프의 분할이다. 그래프가 강하게 연결되었는지와 그래프에서 강한 연결 요소를 찾는것은 선형 시간(Θ(VE)(VE))에 가능하다 .