그래프 시성

수학의 한 분야인 그래프 이론에서 그래프 시성화는 주어진 그래프 G의 표준 형태를 찾는 문제. 표준형식은 G에 이형화된 그래프 캐논(G)으로 표기한 것으로서 G에 이형화된 모든 그래프가 G와 동일한 표준형태를 갖도록 되어 있다.따라서, 그래프 시성화 문제에 대한 해결책으로부터, 두 개의 그래프 G와 H가 이형인지 여부를 시험하고, 그들의 표준형식인 캐논(G)과 캐논(H)을 계산하며, 이 두 표준형식이 동일한지 시험하는 것 등, 그래프 이형성의 문제도 해결할 수 있을 것이다.

그래프의 표준형식은 완전한 그래프 불변성의 예로서, 두 개의 이형성 그래프는 각각 동일한 표준형식을 가지며, 두 개의 비이형성 그래프는 각각 다른 표준형식을 갖는다.^[1][2]반대로, 그래프의 모든 완전한 불변성을 표준 형태를 구성하는 데 사용할 수 있다.^[3]n-Vertex 그래프의 정점 집합은 1에서 n까지의 정수로 식별할 수 있으며, 이러한 식별을 사용하여 그래프의 표준 형식을 정점의 순열로 설명할 수도 있다.그래프의 표준 형식은 표준 라벨링이라고도 하며,^[4] 그래프 표준화는 그래프 표준화로도 알려져 있다.

계산 복잡성

분명히 그래프 시성 문제는 적어도 그래프 이형성 문제만큼 계산적으로 어렵다.실제로 그래프 이형성은 그래프 시성화를 위해 AC까지 줄일⁰ 수 있다.그러나 이 두 문제가 다항식 시간 등가인지는 아직 미지수다.^[2]

그래프 이형성에 대한 (결정론적) 다항 알고리즘의 존재는 여전히 계산 복잡성 이론에 있어 개방적인 문제인 반면, 1977년 Laszlo Babai는 최소 1 - exp(-O(n))의 확률로, 단순 정점 분류 알고리즘이 모든 집합에서 무작위로 선택한 그래프의 표준적인 라벨링을 생성한다고 보고했다.단 두 가지 미세화 단계를 거친 후 n-제곱x 그래프.작은 수정과 추가된 깊이 우선 검색 단계는 그러한 균일하게 초선 무작위 그래프를 선형 기대 시간 내에 표준 라벨로 표시한다.이 결과는 보고된 많은 그래프 이형성 알고리즘이 실제로 잘 작동하는 이유를 어느 정도 밝혀준다.^[5][6]이는 그 원고 형태로 널리 알려지게 된 확률론적 복잡성 이론의 중요한 돌파구였으며, 심포지엄에서 보고된 지 오래되어도 여전히 "발표되지 않은 원고"로 인용되었다.

일반적으로 알려진 표준 형태는 이소모르피즘 등급 내에서 사전 편찬적으로 가장 작은 그래프로, 사전 편찬적으로 가장 작은 인접 행렬을 선형 문자열로 간주하는 클래스의 그래프다.그러나 사전 편찬적으로 가장 작은 그래프의 연산은 NP-hard이다.^[7]

트리의 경우 O(n) 공간이 필요한 간결한 다항식 시성 알고리즘이 Read(1972)에 의해 제시된다.^[8]01 문자열로 각 꼭지점에 레이블을 지정하여 시작하십시오.각 비잎 x에 대해 반복적으로 x의 라벨에서 선행 0과 후행 1을 제거한 다음 x의 라벨을 사전순으로 모든 인접 잎의 라벨과 함께 정렬한다.이러한 정렬된 레이블을 연결한 후 선행 0과 후행 1을 추가하고 이를 x의 새 레이블로 만들고 인접한 리프를 삭제하십시오.정점이 두 개 남아 있는 경우 해당 라벨을 사전순으로 연결하십시오.

적용들

그래프 시성화는 많은 그래프 이형성 알고리즘의 본질이다.대표적인 도구로는 노티가 있다.^[9]

그래프 표준화의 일반적인 적용은 그래픽 데이터 마이닝, 특히 화학 데이터베이스 응용에 있다.^[10]

스마일즈나 InCchI와 같은 화학 물질에 대한 많은 식별자들은 그들의 계산에 표준화된 단계를 사용하는데, 이것은 근본적으로 분자를 나타내는 그래프의 표준화된 것이다.^{[11] [12] [13]} 이러한 식별자는 분자 정보를 인코딩하는 표준(그리고 때로는 사람이 읽을 수 있는) 방법을 제공하고 데이터베이스와 웹에서 그러한 정보를 쉽게 검색하도록 설계된다.

참조