전이감소

Transitive reduction

수학에서 방향 그래프 D의 타전적 감소는 가능한 한 정점이 같고 가장자리가 적은 또 다른 방향 그래프로서, 모든 정점 v 쌍에 대해, 그러한 경로가 감소에 존재하는 경우에만 D에서 v에서 w까지 (방향) 경로가 존재한다.타동성 감소는 아호, 개리 & 울먼(1972)이 도입했는데, 그는 그것들을 구성하는 계산 복잡성에 엄격한 한계를 제공했다.

좀 더 기술적으로, 감소는 D와 동일한 도달 가능성 관계를 갖는 방향 그래프다.동등하게, D와 그 타동성 감소는 서로 동일한 타동성 폐쇄성을 가져야 하며, D의 타동성 감소는 그 특성을 가진 모든 그래프 중에서 가능한 한 적은 에지를 가져야 한다.

유한 방향의 아세클릭 그래프(방향 사이클이 없는 방향 그래프)의 전이적 감소는 고유하며 주어진 그래프의 하위 그래프다.그러나 (방향) 사이클이 있는 그래프의 경우 고유성이 실패하고 무한 그래프의 경우 존재조차 보장되지 않는다.

최소 등가 그래프의 밀접하게 연관된 개념은 D의 하위 그래프로서 가능한 한 도달성 관계가 같고 가장자리가 거의 없다.[1]차이점은 전이적 감소가 D의 하위 그래프일 필요는 없다는 것이다.유한 방향의 시계열 그래프의 경우 최소 등가 그래프는 전이성 감소와 동일하다.단, 주기가 포함될 수 있는 그래프의 경우 최소 등가 그래프를 구성하기 어려운 반면, 타원적 감소는 다항 시간 내에 구성할 수 있다.

관계 쌍을 지시된 그래프에서 호로 해석하여 집합의 추상적인 이항 관계에 대해 transitive 감소를 정의할 수 있다.

반복적으로 지시된 그래프

유한 지시 그래프 G의 타동성 감소는 원래 그래프와 동일한 도달성 관계를 갖는 가능한 가장자리가 가장 적은 그래프다.즉, 그래프 G에 꼭지점 x에서 꼭지점 y까지의 경로가 있는 경우 G의 transitive 감소에도 x에서 y까지의 경로가 있어야 하며, 그 반대의 경우도 있어야 한다.다음 이미지는 비전이성 이항 관계(왼쪽)와 그 전이성 감소(오른쪽)에 해당하는 그래프의 도면을 보여준다.

Tred-G.svg Tred-Gprime.svg

유한 방향의 아세클릭 그래프 G의 전이성 감소는 고유하며, 끝점 사이의 유일한 경로를 형성하는 G의 가장자리로 구성된다.특히 항상 주어진 그래프의 서브그래프다.이러한 이유로, 전이적 감소는 이 경우 최소 등가 그래프와 일치한다.

이항 관계의 수학적 이론에서, 세트 X의 어떤 관계 R은 세트 X를 그것의 꼭지점 집합으로 하고 R과 관련된 모든 정렬된 원소 쌍에 대해 호 Xy를 갖는 지시된 그래프로 생각할 수 있다.특히 이 방법은 부분순서의 원소 쌍 사이에 순서관계 x < y가 있을 때마다 그래프에 호 xy가 있는 지시된 아세클릭 그래프로 부분순서의 세트가 재해석되도록 한다.이러한 방식으로 구성된 방향의 아세클릭 그래프에 타동감소 연산을 적용하면 부분순서의 피복 관계가 생성되는데, 하세 다이어그램을 통해 시각적 표현이 자주 주어진다.

네트워크 간의 구조적 차이를 드러내기 위해 지시된 반복 그래프(예: 인용 그래프 또는 인용 네트워크)로 나타낼 수 있는 네트워크에 타동성 감소가 사용되어 왔다.[2]

주기가 있는 그래프

주기가 있는 유한 그래프에서 전이성 감소는 고유하지 않을 수 있다. 동일한 꼭지점 집합에 최소 에지 수가 있고 주어진 그래프와 동일한 도달성 관계를 갖는 그래프가 둘 이상 있을 수 있다.또한 이러한 최소 그래프가 주어진 그래프의 하위 그래프가 아닌 경우도 있을 수 있다.그럼에도 불구하고, 주어진 그래프 G와 동일한 도달 가능성 관계를 가진 최소 그래프를 특징짓는 것은 간단하다.[3] 만약 G가 임의로 지시된 그래프이고, H가 G와 동일한 도달 가능성 관계를 가진 가능한 최소 개수의 가장자리를 가진 그래프라면, H는 다음과 같이 구성된다.

  • G의 각 강하게 연결된 구성 요소에 대한 지시된 사이클로, 이 구성 요소의 꼭지점들을 함께 연결한다.
  • G의 응축의 전이성 감소의 각 가장자리 XY에 대한 가장자리 Xy. 여기서 X와 Y는 응축의 가장자리로 연결된 G의 두 개의 강하게 연결된 구성요소, x는 성분 X의 어떤 꼭지점, y는 성분 Y의 어떤 꼭지점이다.G의 응축은 G의 모든 강하게 연결된 구성 요소에 대한 정점과 G의 가장자리로 연결된 두 구성 요소에 대한 가장자리가 있는 방향의 Acyclic 그래프다.특히, 그것은 반복적이기 때문에, 그것의 전이적 감소는 앞의 절과 같이 정의될 수 있다.

이러한 유형의 전이적 감소에서 총 에지 수는 응축의 전이적 감소에서 에지 수와 더불어 서로 강하게 연결된 구성 요소(정점 수가 둘 이상인 구성 요소)의 정점 수와 동일하다.

응축 가장자리에 해당하는 전이성 감소의 가장자리는 항상 주어진 그래프 G의 하위그래프로 선택될 수 있다.그러나 강하게 연결된 각 구성 요소 내의 사이클은 그 구성 요소가 해밀턴 사이클을 가지고 있을 경우에만 G의 서브그래프로 선택될 수 있는데, 이 사이클은 항상 진실하지 않고 점검하기 어려운 것이다.이러한 어려움 때문에 동일한 도달 가능성(최소 등가 그래프)으로 주어진 그래프 G의 가장 작은 하위 그래프를 찾는 것은 NP-강력하다.[3]

계산 복잡성

아호 외 연구 결과에서 알 수 있듯이,[3] 그래프 알고리즘의 시간 복잡성을 가장자리 수의 함수가 아닌 그래프에 있는 정점 수의 함수로만 측정했을 때, 지시된 아세클릭 그래프의 타동성 폐쇄와 타동성 감소는 동일한 복잡성을 갖는다.n × n 크기의 부울 행렬의 전이적 폐쇄와 곱셈은 서로 동일한 복잡성을 가지고 있다는 것이 이미 증명되었으므로,[4] 이 결과는 같은 등급으로 전이적 감소를 가져왔다.2015년 현재 매트릭스 곱셈에 대한 가장 정확한 알고리즘은 O(n2.3729) 시간이 소요되며,[5] 이는 밀도 그래프에서 전이성 감소에 대한 가장 빠른 것으로 알려진 최악의 시간을 제공한다.

폐쇄를 사용하여 감소량 계산

Transitive 감소가 Transitive closure만큼 쉽다는 것을 증명하기 위해 Aho 등.부울 행렬 곱셈으로 이미 알려진 동등성에 의존한다.그들은 A를 주어진 지시된 순환 그래프의 인접 행렬이 되게 하고, B는 그 전이성 폐쇄의 인접 행렬이 되게 한다(표준 전이성 폐쇄 알고리즘을 사용하여 계산한다).그 다음 엣지 u는 행렬 u와 행렬 A의 열 v에 0이 아닌 항목이 있고 행렬 제품 AB의 동일한 위치에 0이 있는 경우에만 타전적 감소에 속한다.이 구조에서 행렬 AB의 0이 아닌 요소는 길이 2 이상의 경로로 연결된 꼭지점 쌍을 나타낸다.[3]

감소를 사용하여 폐쇄 계산

Transitive 감소가 transitive closure만큼 어렵다는 것을 증명하기 위해, Aho 등.은 G의 각 꼭지점이 3 정점의 경로로 대체되고 G의 각 가장자리는 이 경로의 해당 중간 정점을 연결하는 H의 에지에 해당하는 다른 그래프 H로부터 생성된다.또한 그래프 H에서 아호 등은 모든 경로 시작부터 모든 경로 끝에 에지를 추가한다.H의 transitive closure에서는 u의 transitive closure에 속하지 않는 경우에만 u의 path start에서 v의 path end까지의 엣지 u가 G의 transitive closure에 속하지 않는 경우에만.따라서 H의 transitive 감소를 효율적으로 계산할 수 있다면 G의 transitive closure는 그것으로부터 직접 읽어낼 수 있다.[3]

희소성 그래프의 감소 계산

정점 수 n과 지시된 반복 그래프에서 가장자리 수 m의 관점에서 모두 측정했을 때, 전이성 감소는 시간 O(nm), 즉 희소 그래프에 대한 행렬 곱셈 방법보다 더 빠를 수 있는 경계에서 찾을 수 있다.이렇게 하려면 각 시작 꼭지점 선택에 대해 지정된 주기적 그래프에 선형 시간 최장 경로 알고리즘을 적용하십시오.계산된 가장 긴 경로에서 길이 1(단일 에지)만 유지하십시오. 즉, u에서 v까지의 다른 경로가 존재하지 않는 에지(u,v)를 유지하십시오.이 O(nm) 시간 범위는 시작 정점의 모든 선택에서 도달할 수 있는 정점을 찾기 위해 깊이 첫 번째 검색 또는 너비 첫 번째 검색을 사용하여 전이 폐쇄를 구축하는 복잡성에 일치하므로, 이러한 가정과 함께 동일한 시간 내에 다시 찾을 수 있다.

메모들

  1. ^ 모일스 & 톰슨(1969년).
  2. ^ Clough 등(2015년).
  3. ^ a b c d e 아호, 개리 & 울만 (1972)
  4. ^ 아호 외는 이 결과를 1971년 출판되지 않은 이안 먼로의 원고와 M. E. Furman의 1970년 러시아어 논문으로 돌렸다.
  5. ^ 르갈(2014년).

참조

  • Aho, A. V.; Garey, M. R.; Ullman, J. D. (1972), "The transitive reduction of a directed graph", SIAM Journal on Computing, 1 (2): 131–137, doi:10.1137/0201008, MR 0306032.
  • Clough, J. R.; Gollings, J.; Loach, T. V.; Evans, T. S. (2015), "Transitive reduction of citation networks", Journal of Complex Networks, 3 (2): 189–203, arXiv:1310.8224, doi:10.1093/comnet/cnu039.
  • Moyles, Dennis M.; Thompson, Gerald L. (1969), "An Algorithm for Finding a Minimum Equivalent Graph of a Digraph", Journal of the ACM, 16 (3): 455–460, doi:10.1145/321526.321534.
  • Le Gall, François (2014), "Powers of Tensors and Fast Matrix Multiplication", Proc. 39th International Symposium on Symbolic and Algebraic Computation (ISSAC '14), pp. 296–303, doi:10.1145/2608628.2608664.

외부 링크