암시적 그래프

Implicit graph

그래프 알고리즘의 연구에서 암묵적 그래프 표현(또는 보다 단순하게 암묵적 그래프)은 정점이나 에지가 컴퓨터 메모리에서 명시적 객체로 표현되지 않고, 오히려 계산 가능한 함수 등 일부 다른 입력으로부터 알고리즘적으로 결정되는 그래프를 말한다.

근린 표현

암묵적 그래프의 개념은 그래프 측면에서 설명되는 다양한 검색 알고리즘에서 공통적이다.이 맥락에서 암묵적 그래프는 지정된 정점에 대해 모든 인접 항목을 정의하는 규칙 집합으로 정의될 수 있다.[1]이러한 유형의 암묵적 그래프 표현은 각 꼭지점의 이웃에 쉽게 접근할 수 있다는 점에서 인접 목록과 유사하다.예를 들어, 루빅 큐브와 같은 퍼즐에 대한 해결책을 찾는데 있어서, 각 꼭지점이 큐브의 가능한 상태 중 하나를 나타내고, 각 가장자리는 한 상태에서 다른 상태로의 이동을 나타내는 암묵적 그래프를 정의할 수 있다.퍼즐에서 가능한 모든 움직임을 시도하고 각각의 움직임이 도달한 상태를 결정함으로써 정점의 이웃을 생성하는 것은 간단하다. 그러나 루빅스 큐브의 상태 공간이 너무 커서 알고리즘으로 모든 상태를 나열할 수 없기 때문에 암묵적인 표현이 필요하다.[2]

계산 복잡성 이론에서, 몇 가지 복잡성 등급이 암묵적 그래프와 관련하여 정의되었으며, 위에서 정의한 것처럼 정점의 인접 부분을 나열하는 규칙이나 알고리즘에 의해 정의되었다.예를 들어 PPA는 비방향 암묵적 그래프(정점들이 n-비트 이진 문자열로, 정점들이 모든 정점의 이웃들을 나열하기 위한 다항 시간 알고리즘)를 입력하여 그래프에서 홀수도의 정점인 두 번째 정점을 찾아야 하는 문제의 등급이다.핸드셰이킹 보조정리(handshake lema)에 의해 그러한 정점이 존재한다; 그 정점을 찾는 것은 NP에는 문제가 있지만, PPA = NP의 여부를 알 수 없기 때문에 이런 식으로 정의될 수 있는 문제는 반드시 NP-완성은 아닐 수 있다. PPAD는 알고리즘 게임 이론에서 주의를 끌었던 암묵적 방향 그래프에 정의된 유사 등급이다.내시 평형 계산의 m.[3]암묵적 그래프에서 한 꼭지점에 대한 다른 꼭지점의 도달성 테스트 문제는 NL(정점이 O(log n)비트 비트스트링인 암묵적 지시 그래프에서 도달성으로 특징지어질 수 있는 문제의 등급), SL(유니어의 유사 등급)을 포함한 공간 경계 비결정적 복잡성 클래스의 특성화에도 사용될 수 있다.ected graphs) 및 PSPACE(다항 길이 비트스트링이 있는 암묵적 그래프에서 도달 가능성으로 특징지어질 수 있는 문제의 클래스).이 복잡성-이론적 맥락에서 암묵적 그래프의 정점은 비결정론적 튜링 기계의 상태를 나타낼 수 있고, 가장자리는 가능한 상태 전환을 나타낼 수 있지만 암묵적 그래프는 다른 많은 유형의 결합 구조를 나타내기 위해 사용될 수도 있다.[4]또 다른 복잡도 등급인 PLS는 암묵적 그래프에서 국소 최적점을 찾는 복잡성을 포착한다.[5]

암시적 그래프 모델은 또한 비재활성화된 모델에 대해 알려진 분리보다 더 강한 복잡성 등급 간의 분리를 증명하기 위해 상대화의 한 형태로 사용되어 왔다.예를 들어 Childs 등.양자 컴퓨터에서는 다항식으로 해결할 수 있지만 고전적인 컴퓨터에서 해결하려면 기하급수적인 시간이 필요한 그래프 통과 문제를 정의하기 위해 암묵적 그래프의 근린 표현을 사용했다.[6]

인접 레이블 지정 방식

그래프를 효율적으로 표현하는 맥락에서 J. H. Muller는 G의 각 꼭지점에 O(log n) 비트 식별자를 할당하는 그래프 F의 특정 패밀리 G에 대한 로컬 구조 또는 인접 라벨링 체계를 정의했으며, 이 알고리즘은 (F에 의존할 수 있지만 개별 그래프 G에 독립적일 수 있음)과 함께 G의 각 정점에 대한 O(log n) 비트 식별자를 할당했다.ut 두 정점 식별자를 사용하여 그것들이 G에서 가장자리의 끝점인지 여부를 결정한다.즉, 이러한 유형의 암묵적 표현은 인접 행렬과 유사하다. 두 꼭지점이 인접해 있는지 확인하는 것은 간단하지만 정점을 찾는 것은 모든 정점을 루핑하고 어떤 정점이 이웃인지 테스트하는 것을 포함할 수 있다.[7]

인접 레이블 구조를 가진 그래프 패밀리는 다음을 포함한다.

경계 도 그래프
G의 모든 꼭지점에 최대 d 이웃이 있는 경우, 1에서 n까지의 정점에 번호를 매기고 정점에 대한 식별자를 자신의 (d + 1)-투플과 그 이웃의 숫자가 되도록 할 수 있다.두 꼭지점은 식별자의 첫 번째 숫자가 다른 꼭지점의 식별자에 나중에 나타날 때 인접해 있다.보다 일반적으로, 동일한 접근법을 사용하여 평면 그래프와 마이너 폐쇄 그래프 계열의 그래프를 포함하여 경계가 있는 수목성 또는 경계가 있는 퇴행성을 가진 그래프를 암시적으로 나타낼 수 있다.[8][9]
교차로 그래프
구간 그래프는 실제 선에 있는 선 세그먼트 집합을 교차 그래프로 나타낸 것이다.선 세그먼트의 끝점인 점들이 1에서 2n까지 번호가 매겨지고 그래프의 각 꼭지점이 해당 구간의 두 끝점 수로 표시되는 인접 라벨링 체계가 주어질 수 있다.이 표현을 사용하면 정점을 나타내는 숫자를 비교하고 이 숫자가 겹치는 구간을 정의하는지 확인함으로써 두 정점이 인접해 있는지 여부를 확인할 수 있다.동일한 접근방식은 경계 상자성 그래프와 원 그래프 및 거리 계통 그래프와 같은 이러한 패밀리의 하위 패밀리를 포함한 다른 기하학적 교차로 그래프에도 적용된다.[8][10]그러나 기하학적 교차 그래프 표현은 각 기하학적 객체를 지정하기 위해 로그 수 이상의 비트가 필요할 수 있기 때문에 인접 라벨링 체계의 존재를 항상 의미하지는 않는다.예를 들어, 그래프를 단위 디스크 그래프로 나타내려면 디스크 센터의 좌표에 기하급수적으로 많은 비트가 필요할 수 있다.[11]
저차원 비교가능성 그래프
부분 순서의 집합에 대한 비교가능성 그래프는 각 세트 요소에 대한 정점과 부분 순서와 관련된 두 세트 요소 사이의 가장자리를 가지고 있다.부분 순서의 순서 치수는 주어진 부분 순서가 교차하는 선형 순서의 최소 수입니다.부분 순서가 경계 주문 치수를 갖는 경우, 비교가능성 그래프에서 정점에 대한 인접 라벨링 체계는 각 정점에 정의되는 선형 순서의 위치를 지정하고, 각 정점에 해당하는 숫자의 쌍이 동일한 순서 상대성을 갖는 경우 두 정점이 인접한 것으로 결정함으로써 정의할 수 있다.n이 서로 짝을 이루듯이.특히 이것은 최대 4개의 치수의 부분적인 순서에서 오는 화음 비교가능성 그래프의 인접성 표기를 허용한다.[12][13]

암묵적 그래프 추측

수학의 미해결 문제:

천천히 성장하는 모든 유전적 그래프 집단은 암묵적 표현을 가지고 있는가?

(수학에서 더 풀리지 않은 문제)

모든 그래프 패밀리가 로컬 구조를 갖는 것은 아니다.일부 패밀리의 경우, 간단한 카운트 인수는 인접 라벨링 체계가 존재하지 않는다는 것을 증명한다. 즉, O(n log n) 비트만 전체 그래프를 나타내기 위해 사용할 수 있으므로, 주어진 패밀리의 n-vertex 그래프 수가 최대 2개일O(n log n) 때에만 이 유형의 표시가 존재할 수 있다.초당적 그래프나 삼각형이 없는 그래프와 같이 이것보다 더 많은 수의 그래프를 갖는 그래프 패밀리는 인접 레이블링 체계를 가지고 있지 않다.[8][10]기 때문 더 큰 그래프로 이 파음으로 어떤 주어진 그래프 변화시킬 수 있다. 하지만, 이 그래프의 가족들의 수 작다 그래프의 심지어 가정. 예를 들면, 더 적은 가장자리에 그래프 vertices보다 가족이 인접 계획 표지를 가지고 있지 않2O(nlogn)n-vertex 그래프가 있는 경우 바이러스 인접 표지 계획을 가지고 있지 않습니다amily에 의해레이블성을 변경하지 않고 각 모서리에 대해 새 절연 정점 추가.[7][10]Kannan 외 연구진은 금지된 서브그래프 특성화와 최대O(n log n) 2개의 n-Vertex 그래프가 인접 표지 계획의 존재를 보장할 수 있을 만큼 충분히 함께 있는지 질문했다; Spinrad가 추측으로 다시 밝힌 이 질문은 여전히 열려 있다.[8][10]추측 조건을 만족하고 알려진 인접 라벨링 체계가 없는 그래프 패밀리 중에는 디스크 그래프와 선 세그먼트 교차 그래프 패밀리가 있다.

레이블 지정 방식 및 유도 범용 그래프

그래프 계열 F가 인접 라벨링 체계를 가지고 있는 경우, F의 n-Vertex 그래프는 다항식 크기의 공통 유도 범용 그래프, 가능한 모든 정점 식별자로 구성된 그래프의 유도 하위 그래프로 나타낼 수 있다.반대로, 이러한 유형의 유도 범용 그래프를 구성할 수 있는 경우, 정점의 정체성은 인접 라벨링 방식에서 라벨로 사용될 수 있다.[8]이 암묵적 그래프 표현의 적용에 있어 라벨의 비트 수는 유도된 범용 그래프의 정점 수로 직접 번역되기 때문에 라벨이 가능한 몇 개의 비트를 사용하는 것이 중요하다.Alsturp과 Rauhe는 어떤 나무도 라벨당2 로그 n + O(log* n)비트를 갖는 인접 라벨링 체계를 가지고 있다는 것을 보여주었고, 여기서부터 수목성 k를 가진 그래프는 라벨당 k 로그 n2 + O(log* n)비트를 갖는 체계와 n2kO(log* n) 정점을 가진 범용 그래프를 갖는다는 것을 보여주었다.특히 평면 그래프는 최대 3개의 수목성을 가지기 때문에 거의 정점에 가까운 수의 범용 그래프를 가진다.[14]이 경계는 평면 그래프와 마이너 폐쇄 그래프 패밀리가 라벨당 2개의2 로그 n + O(로그 로그 n)비트를 갖는 라벨링 체계를 가지고 있으며, 경계 트리 폭의 그래프는 라벨당2 로그 n + O(로그 로그 n)비트를 갖는 라벨링 체계를 가지고 있다는 것을 보여준 Gavoille과 Labourel에 의해 개선되었다.[15]평면 그래프의 경계는 평면 그래프가 라벨당 (4/3+o(1)로그2 n비트로 라벨링 체계를 가지고 있다는 것을 보여준 Bonamy, Gavoille, Piliczuk에 의해 다시 개선되었다.[16]마지막으로 Dujmovich 등에서는 평면 그래프가 라벨당 (1+o(1)log2 n 비트로 라벨 표시 체계를 가지고 있으며, 정점이 있는1+o(1) 범용 그래프를 제공한다는 것을 보여주었다.[17]

회피성

Aanderaa-Karp-Rosenberg 추측에서는 두 정점이 인접해 있는지 여부를 결정하기 위해 블랙박스 규칙으로 라벨이 붙은 정점 집합으로 주어진 암시적 그래프를 다룬다.이 정의는 한 패밀리의 모든 그래프에 적용되는 일반 규칙이 아니라 특정 그래프에 특정될 수 있다는 점에서 인접 레이블링 방식과 다르다.이러한 차이 때문에 모든 그래프에는 암묵적인 표현이 있다.예를 들어, 규칙은 별도의 인접 행렬에서 꼭지점 쌍을 찾는 것일 수 있다.그러나 이러한 유형의 암묵적 그래프가 입력으로 주어지는 알고리즘은 시험이 구현되는 방법에 대한 참조 없이 암묵적 인접성 테스트를 통해서만 작동해야 한다.

그래프 속성은 그래프가 주어진 그래프 패밀리에 속하는지 여부에 대한 질문이다. 정점을 다시 표시해도 답은 변하지 않아야 한다.이 맥락에서 결정해야 할 문제는 주어진 암묵적 그래프에 대해 관심 속성을 참 또는 거짓으로 결정하기 전에 최악의 경우 인접성에 대해 얼마나 많은 꼭지점 쌍을 시험해야 하는가이다.Rivest와 Vuillemin은 비교 그래프 속성에 대한 결정론적 알고리즘이 정점 쌍의 2차 수를 테스트해야 한다는 것을 증명했다.[18]완전한 Aanderaa-Karp-Rosenberg 추측에 따르면 단조로운 그래프 속성에 대한 결정론적 알고리즘(특성과 함께 그래프에 더 많은 가장자리가 추가될 경우 참으로 유지되는 알고리즘)은 어떤 경우에는 가능한 모든 꼭지점 쌍을 시험해야 한다.예를 들어, 정점[19] 수가 가장 많은 그래프에 대해서는 사실인 것으로 알려져 있지만, 완전한 추정은 여전히 열려 있다.무작위화된 알고리즘과 양자 알고리즘에 대한 문제의 변형도 연구되었다.

Bender와 Ron은 회피성 추측에 사용된 동일한 모델에서 지시된 반복 그래프와 매우 멀리 떨어져 있는 그래프를 구별하는 것은 일정한 시간 내에 가능하다는 것을 보여주었다.대조적으로, 그러한 빠른 시간은 이웃 기반의 암묵적 그래프 모델에서는 불가능하다.[20]

참고 항목

참조

  1. ^ Korf, Richard E. (2008), "Linear-time disk-based implicit graph search", Journal of the ACM, 55 (6), Article 26, 40pp, doi:10.1145/1455248.1455250, MR 2477486.
  2. ^ Korf, Richard E. (2008), "Minimizing disk I/O in two-bit breadth-first search" (PDF), Proc. 23rd AAAI Conf. on Artificial Intelligence, pp. 317–324, The standard 3×3×3 Rubik's Cube contains 4.3252 × 1019 states, and is too large to search exhaustively.
  3. ^ Papadimitriou, Christos (1994), "On the complexity of the parity argument and other inefficient proofs of existence" (PDF), Journal of Computer and System Sciences, 48 (3): 498–532, doi:10.1016/S0022-0000(05)80063-7, archived from the original (PDF) on 2016-03-04, retrieved 2011-07-12
  4. ^ Immerman, Neil (1999), "Exercise 3.7 (Everything is a Graph)", Descriptive Complexity, Graduate Texts in Computer Science, Springer-Verlag, p. 48, ISBN 978-0-387-98600-5.
  5. ^ Yannakakis, Mihalis (2009), "Equilibria, fixed points, and complexity classes", Computer Science Review, 3 (2): 71–85, arXiv:0802.2831, doi:10.1016/j.cosrev.2009.03.004.
  6. ^ Childs, Andrew M.; Cleve, Richard; Deotto, Enrico; Farhi, Edward; Gutmann, Sam; Spielman, Daniel A. (2003), "Exponential algorithmic speedup by a quantum walk", Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, New York: ACM, pp. 59–68, arXiv:quant-ph/0209131, doi:10.1145/780542.780552, MR 2121062.
  7. ^ a b Muller, John Harold (1988), Local structure in graph classes, Ph.D. thesis, Georgia Institute of Technology.
  8. ^ a b c d e Kannan, Sampath; Naor, Moni; Rudich, Steven (1992), "Implicit representation of graphs", SIAM Journal on Discrete Mathematics, 5 (4): 596–603, doi:10.1137/0405049, MR 1186827.
  9. ^ Chrobak, Marek; Eppstein, David (1991), "Planar orientations with low out-degree and compaction of adjacency matrices" (PDF), Theoretical Computer Science, 86 (2): 243–266, doi:10.1016/0304-3975(91)90020-3.
  10. ^ a b c d Spinrad, Jeremy P. (2003), "2. Implicit graph representation", Efficient Graph Representations, pp. 17–30, ISBN 0-8218-2815-0.
  11. ^ Kang, Ross J.; Müller, Tobias (2011), Sphere and dot product representations of graphs (PDF), archived from the original (PDF) on 2012-03-16, retrieved 2011-07-12.
  12. ^ Ma, Tze Heng; Spinrad, Jeremy P. (1991), "Cycle-free partial orders and chordal comparability graphs", Order, 8 (1): 49–61, doi:10.1007/BF00385814, MR 1129614.
  13. ^ Curtis, Andrew R.; Izurieta, Clemente; Joeris, Benson; Lundberg, Scott; McConnell, Ross M. (2010), "An implicit representation of chordal comparability graphs in linear time", Discrete Applied Mathematics, 158 (8): 869–875, doi:10.1016/j.dam.2010.01.005, MR 2602811.
  14. ^ Alstrup, Stephen; Rauhe, Theis (2002), "Small induced-universal graphs and compact implicit graph representations" (PDF), Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 53–62, doi:10.1109/SFCS.2002.1181882, archived from the original (PDF) on 2011-09-27, retrieved 2011-07-13.
  15. ^ Arnaud, Labourel; Gavoille, Cyril (2007), "Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs" (PDF), Proceedings of the 15th annual European Symposium on Algorithms, pp. 582–593, doi:10.1007/978-3-540-75520-3_52.
  16. ^ Bonamy, Marthe; Gavoille, Cyril; Pilipczuk, Michał (2020), "Shorter Labeling Schemes for Planar Graphs", Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pp. 446–462, arXiv:1908.03341, doi:10.1007/978-3-540-75520-3_52.
  17. ^ Dujmović, Vida; Esperet, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2020), "Adjacency Labelling for Planar Graphs (and Beyond)", 61st IEEE Annual Symposium on Foundations of Computer Science]], pp. 577–588, arXiv:2003.04280, doi:10.1007/978-3-540-75520-3_52.
  18. ^ Rivest, Ronald L.; Vuillemin, Jean (1975), "A generalization and proof of the Aanderaa-Rosenberg conjecture", Proc. 7th ACM Symposium on Theory of Computing, Albuquerque, New Mexico, United States, pp. 6–11, doi:10.1145/800116.803747.
  19. ^ Kahn, Jeff; Saks, Michael; Sturtevant, Dean (1983), "A topological approach to evasiveness", Symposium on Foundations of Computer Science, Los Alamitos, CA, USA: IEEE Computer Society, pp. 31–33, doi:10.1109/SFCS.1983.4.
  20. ^ Bender, Michael A.; Ron, Dana (2000), "Testing acyclicity of directed graphs in sublinear time", Automata, languages and programming (Geneva, 2000), Lecture Notes in Comput. Sci., vol. 1853, Berlin: Springer, pp. 809–820, doi:10.1007/3-540-45022-X_68, MR 1795937.