그래프 자동형성

Graph automorphism

그래프 이론의 수학적 분야에서, 그래프의 자동형성은 가장자리-베르텍스 연결성을 유지하면서 그래프가 그 자체로 매핑되는 대칭성의 한 형태다.

형식적으로 그래프 G = (V,E)의 자동형은 정점 집합 V의 순열 is으로, 쌍( (, v)도 에지를 형성하는 경우에만 정점 쌍(u,v)이 에지를 형성한다.즉 G에서 그 자체로 그래프의 이형성이다.자동형성은 지시된 그래프와 방향되지 않은 그래프 모두에 대해 이러한 방식으로 정의될 수 있다.두 개의 자동모형의 구성은 또 다른 자동모형이며, 주어진 그래프의 자동모형의 집합은 구성 연산 하에서는 그래프의 자동모형 그룹인 그룹을 형성한다.반대로, Frucht의 정리에 의해, 모든 집단은 연결된 그래프의 자동형 집단, 즉 실로 입방형 그래프로 표현될 수 있다.[1][2]

계산 복잡성

주어진 두 개의 그래프가 정점-정점-정점-정점-에지-에지-에지-에지-에지-에지-에지-에지-에지-에지 여부를 결정하는 것은 적어도 그래프 이형성 문제를 해결하는 것만큼 (계산 복잡성 측면에서) 어렵다.G와 H는 그래프 G와 H의 분리된 결합에 의해 형성된 분리된 그래프가 두 성분을 교환하는 자동형성을 갖는 경우에만 이형성이 된다.[3]사실, 자동화를 세는 것만으로도 그래프 이형성에 해당하는 다항식 시간이다.[4]

Petersen 그래프의 이 도면은 대칭의 부분군을 표시하며, 이형화된 대칭 그룹D를5 표시하지만 그래프에는 도면에 없는 추가 대칭이 있다.예를 들어 그래프가 대칭이기 때문에 모든 에지는 동등하다.

그래프 자동형성 문제는 그래프가 비경쟁적 자동형성을 가지고 있는지 여부를 검정하는 문제다.그것은 계산 복잡성의 등급 NP에 속한다.그래프 이형성 문제와 마찬가지로 다항식 시간 알고리즘이 있는지 NP-완전인지는 알 수 없다.[5]정점도가 상수로 경계되는 그래프에 대해 그래프 자동형 문제를 해결하기 위한 다항식 시간 알고리즘이 있다.[3]그래프 자동형성 문제는 다항식 시간 다항식 다항식 다항식 다항식 이형성 문제로 환원할 수 있지만 역축소는 알 수 없다.[4][6][7]대조적으로, 경도는 자동화가 특정한 방식으로 제약될 때 알려져 있다. 예를 들어, 고정점 없는 자동형(정점을 고정하지 않는 자동형)의 존재를 결정하는 것은 NP-완전이며, 그러한 자동형을 계산하는 문제는 pP-완전이다.[5][7]

알고리즘, 소프트웨어 및 애플리케이션

일반적인 그래프 자동형성 문제에 대해 최악의 경우 다항식 알고리즘은 알려져 있지 않지만, 애플리케이션에서 발생하는 많은 큰 그래프에 대해 자동형 그룹(그리고 중복되지 않은 생성기 집합을 출력)을 찾는 것은 다소 쉽다.NOTY,[8] BLISS[9] 및 SCHY를 포함한 여러 오픈 소스 소프트웨어 도구를 이 작업에 사용할 수 있다.[10][11] 예를 들어, SCHY는 몇 백만 개의 정점이 있는 일부 그래프를 단 몇 초 만에 처리하는 스파스 그래프에 특히 효율적이다.단, BLISS와 NOTY도 Canonical Labeling을 제작할 수 있는 반면, SCASSY는 현재 Graph Automorphism을 해결하는 데 최적화되어 있다.중요한 관찰은 n 정점에 대한 그래프의 경우, 자동형성 그룹을 n-1 발전기 이상으로 지정할 수 있으며, 위의 소프트웨어 패키지는 알고리즘의 부작용으로서 이 경계를 만족시킬 것을 보장한다(최소한의 발전기 집합은 찾기가 더 어렵고 실제로도 특별히 유용하지 않다).또한 모든 생성자의 총 지원(즉, 움직이는 정점 수)이 n의 선형 함수에 의해 제한되는 것으로 나타나 이 알고리즘의 런타임 분석에 중요하다.그러나 이는 2012년 3월 현재 사실로 성립되지 않고 있다.

Graph Automorphism의 실용적인 적용은 그래프 그리기와 기타 시각화 작업을 포함하며, 공식적인 검증과 물류라는 맥락에서 발생하는 부울 만족도의 구조화된 인스턴스를 해결한다.분자 대칭은 화학적 특성을 예측하거나 설명할 수 있다.

대칭 표시

여러 그래프 그리기 연구자들은 그래프의 자동화가 도면의 대칭으로 가시화되는 방식으로 그래프를 그리기 위한 알고리즘을 연구했다.대칭 주위에 설계되지 않았지만 가능한 경우 자동으로 대칭 도면을 생성하는 방법을 사용하거나 [12]대칭을 명시적으로 식별하여 도면에서 정점 배치를 유도하는 데 사용할 수 있다.[13]그래프의 모든 대칭을 동시에 표시할 수 있는 것은 아니므로 표시할 대칭과 시각화되지 않은 상태로 둘 대칭을 선택해야 할 수도 있다.

자동화에 의해 정의된 그래프 패밀리

몇 개의 그래프 패밀리는 특정 유형의 자동화로 정의된다.

  • 비대칭 그래프는 사소한 자동형만 있는 비방향 그래프다.
  • 정점 변환 그래프는 모든 정점이 자동모형으로 다른 정점으로 매핑될 수 있는 방향성이 없는 그래프다.
  • 에지 변환 그래프는 모든 에지가 자동형성에 의해 다른 에지로 매핑될 수 있는 비방향 그래프다.
  • 대칭 그래프는 인접한 정점의 모든 쌍이 자동모형으로 인접 정점의 다른 쌍으로 매핑될 수 있는 그래프다.
  • 거리 변환 그래프는 모든 꼭지점 쌍이 자동형성에 의해 동일한 거리에 있는 다른 꼭지점 쌍으로 매핑될 수 있도록 그래프를 의미한다.
  • 반대칭 그래프는 에지 변환이지만 정점은 변환하지 않는 그래프다.
  • 반투명 그래프는 정점-변환성 및 에지-변환성이지만 대칭은 아닌 그래프다.
  • 스큐 대칭 그래프는 가장자리를 가장자리에 매핑하지만 각 가장자리의 방향을 반전시키는 정점에 순열 with과 함께 지시된 그래프다.또한 σ은 비자발성이어야 한다.

이러한 패밀리 사이의 포함 관계는 다음 표로 표시된다.

Skeleton of the dodecahedron
Arrow east.svg
Shrikhande graph
Arrow west.svg
Paley graph
거리 변환의 거리 규칙의 매우 규칙적인.
Arrow south.svg
F26A graph
Arrow west.svg
Nauru graph
대칭(대칭 변환) t-변환, t ≥ 2
Arrow south.svg
(연결된 경우)
Holt graph
Arrow east.svg
Folkman graph
Arrow east.svg
Complete bipartite graph K3,5
정점 및 에지 변환 가장자리-변환적이고 규칙적인 가장자리-변환성
Arrow south.svg
Arrow south.svg
Skeleton of the truncated tetrahedron
Arrow east.svg
Frucht graph
정점 변환의 정칙의
Arrow north.svg
Skeleton of the triangular prism
케이리 그래프

참고 항목

참조

  1. ^ Frucht, R. (1938), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe", Compositio Mathematica (in German), 6: 239–250, ISSN 0010-437X, Zbl 0020.07804.
  2. ^ Frucht, R. (1949), "Graphs of degree three with a given abstract group", Canadian Journal of Mathematics, 1 (4): 365–378, doi:10.4153/CJM-1949-033-6, ISSN 0008-414X, MR 0032987.
  3. ^ a b Luks, Eugene M. (1982), "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences, 25 (1): 42–65, doi:10.1016/0022-0000(82)90009-5.
  4. ^ a b Mathon, R. (1979). "A note on the graph isomorphism counting problem". Information Processing Letters. 8: 131–132. doi:10.1016/0020-0190(79)90004-8.
  5. ^ a b Lubiw, Anna (1981), "Some NP-complete problems similar to graph isomorphism", SIAM Journal on Computing, 10 (1): 11–21, doi:10.1137/0210002, MR 0605600.
  6. ^ Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), Graph Isomorphism Problem: The Structural Complexity, Birkhäuser Verlag, ISBN 0-8176-3680-3, OCLC 246882287
  7. ^ a b Torán, Jacobo (2004). "On the hardness of graph isomorphism" (PDF). SIAM Journal on Computing. 33: 1093–1108. doi:10.1137/S009753970241096X.
  8. ^ McKay, Brendan (1981), "Practical Graph Isomorphism" (PDF), Congressus Numerantium, 30: 45–87, retrieved 14 April 2011.
  9. ^ Junttila, Tommi; Kaski, Petteri (2007), "Engineering an efficient canonical labeling tool for large and sparse graphs" (PDF), Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX07).
  10. ^ Darga, Paul; Sakallah, Karem; Markov, Igor L. (June 2008), "Faster Symmetry Discovery using Sparsity of Symmetries" (PDF), Proceedings of the 45th Design Automation Conference: 149–154, doi:10.1145/1391469.1391509, ISBN 978-1-60558-115-6.
  11. ^ Katebi, Hadi; Sakallah, Karem; Markov, Igor L. (July 2010), "Symmetry and Satisfiability: An Update" (PDF), Proc. Satisfiability Symposium (SAT).
  12. ^ 디 바티스타, 주세페;Tamassia, 로베르토, Tollis, 요안 니스 G.(1992년),"지역 요구 사항과 평면 상승 그림의 중심이 되는 디스플레이", 이산과 해석 기하학, 7(1):381–401, doi:10.1007/BF02187850, Eades, 피터, 린, Xuemin(2000년),"봄은 알고리즘과 대칭", 이론 컴퓨터 과학, 240(2):379–405,. doi:10.1016(99)00239-X.
  13. ^ Hong, Seok-Hee (2002), "Drawing graphs symmetrically in three dimensions", Proc. 9th Int. Symp. Graph Drawing (GD 2001), Lecture Notes in Computer Science, vol. 2265, Springer-Verlag, pp. 106–108, doi:10.1007/3-540-45848-4_16, ISBN 978-3-540-43309-5.

외부 링크