그래프 동형 사상

1. 개요

그래프 동형 사상은 두 그래프의 정점과 변 사이의 관계를 보존하는 전단사 함수가 존재할 때, 두 그래프가 동일한 구조를 가진다고 정의하는 개념이다. 라벨 그래프의 동형 사상은 라벨을 보존하거나 동치류를 보존하는 두 가지 정의가 있으며, 휘트니 정리는 두 연결 그래프가 동형 사상인 것은 그들의 선 그래프가 동형 사상인 것과 동치임을 보여준다. 그래프 동형 사상 문제는 NP에 속하지만 P 또는 NP-완전인지 밝혀지지 않았으며, 화학 정보학, 수학 화학, 전자 설계 자동화 등 다양한 분야에 적용된다. 이 문제의 해결을 위해 알고리즘 개발, 복잡도 분석, 양자 알고리즘 연구가 활발히 진행되고 있다.

2. 정의

$G=(V,E)$, $G\text{'}=(V\text{'},\; E\text{'})$를 ((단순) 그래프)라고 하자. 여기서 $V$는 $G$의 정점 집합, $E$는 $G$의 변 집합이고, $V\text{'}$는 $G\text{'}$의 정점 집합, $E\text{'}$는 $G\text{'}$의 변 집합이다. $G$의 임의의 두 정점 $v,\; w\; \backslash in\; V$에 대해, $(v,w)\; \backslash in\; E$와 $(f(v),\; f(w))\; \backslash in\; E\text{'}$가 동치일 때를 만족하는 $V$에서 $V\text{'}$로의 전단사 사상 $f$가 존재하면, $G$와 $G\text{'}$는 그래프 동형(또는 단순히 동형)이라고 하며, $G\text{'}$는 $G$의 동형 그래프라고 한다.

예를 들어 다음과 같은 그래프가 주어졌다고 하자.

이때, 인접한 정점에 대응하는 정점은 인접해 있다. 이처럼 $G$와 $G\text{'}$가 "동일"한 정점을 가지며, 동일한 변의 연결을 하고 있을 때 그 그래프를 동형이라고 한다.

"그래프 동형 사상"의 개념을 통해 우리는 그래프 자체의 구조에 내재된 그래프 속성과 그래프 그리기, 그래프에 대한 자료 구조 등 그래프 표현과 관련된 속성을 구별할 수 있다.

2.1. 라벨 그래프의 동형사상

라벨 그래프에서 동형 사상은 두 가지 방법으로 정의할 수 있다.

첫 번째 정의에서 동형 사상은 라벨을 보존하는 변-보존 일대일 대응이다.

두 번째 정의에서 동형 사상은 라벨의 동치류를 보존하는 변-보존 일대일 대응이다. 즉, 같은 라벨을 가진 꼭짓점들은 대응되는 그래프에서의 라벨이 모두 같다.

예를 들어 첫 번째 정의에서, 각 꼭짓점이 1과 2로 번호매김된 $K\_2$ 그래프의 자기동형사상은 동일한 꼭짓점으로 사상하는 1가지 경우뿐이다. 그러나 두 번째 정의에서는 서로 다른 꼭짓점으로 사상되는 경우도 포함하여 자기동형사상은 2가지가 된다. (이 예시에서는 같은 라벨을 가지는 꼭짓점이 각각 하나뿐이다.)

두 그래프가 정점을 고유하게 식별하기 위해서만 사용되는, 그래프 정점 수인 n에 따라 일반적으로 정수 범위 1,...,n에서 가져온 고유 표지가 부여되는 특정 상황에서는 두 번째 정의가 가정된다. 이러한 경우 대응하는 기본 표지 없는 그래프가 동형 사상인 경우 두 개의 표지 그래프가 동형 사상이라고도 한다.

3. 휘트니 정리

해슬러 휘트니가 증명한 휘트니 정리에 따르면, 두 연결 그래프가 동형 사상인 것과 두 그래프의 선 그래프가 동형 사상인 것은 같다. 단, 완전 그래프 K₃과 완전 이분 그래프 K_1,3은 예외이다.

휘트니 정리는 하이퍼그래프로도 확장할 수 있다.

4. 그래프 동형사상 문제

두 유한 그래프가 동형인지 판단하는 문제를 그래프 동형사상 문제라고 한다. 이 문제는 NP에 속하지만, P 또는 NP-완전에 속하는지는 아직 밝혀지지 않았다.

"동형 사상"은 어떤 객체가 "동일한 구조"를 갖는다는 비형식적인 개념을 포착하며, 이는 객체의 "원자적" 구성 요소의 개별적인 차이점을 무시할 경우를 말한다. 그래프에서 "원자적" 구성 요소는 정점과 변을 의미하며, 이러한 요소들의 개별성이 중요한 경우에는 유향 그래프, 라벨 그래프, 색칠된 그래프, 루트 트리 등과 같이 구조에 추가적인 제약을 가한 모델을 사용한다. 동형 사상 관계는 이러한 그래프의 일반화된 형태에도 정의될 수 있으며, 동형 사상 전단사는 구조의 요소를 보존해야 한다.

"그래프 동형 사상" 개념은 그래프 자체의 구조에 내재된 그래프 속성과 그래프 그리기, 그래프에 대한 자료 구조, 그래프 라벨링 등 그래프 표현과 관련된 속성을 구별할 수 있게 해준다. 예를 들어, 그래프가 정확히 하나의 사이클(그래프 이론)을 가지면, 해당 동형 사상 클래스의 모든 그래프도 정확히 하나의 사이클을 갖는다.

부분그래프 동형사상 문제(주어진 그래프의 부분그래프가 다른 그래프와 동형인지 판단하는 문제)는 NP-완전임이 밝혀졌다.

4.1. 관련 연구

그래프 동형 사상 문제는 전통적인 수학적 방식으로 연구될 수 있지만, 주로 알고리즘적 접근 방식으로 해결해야 할 문제로 인식된다. 이 문제는 화학정보학, 수리화학(화합물 식별), 전자 설계 자동화(전자 회로 디자인 일치 여부 판단) 등 다양한 분야에 응용된다.

그래프 동형 사상 문제는 계산 복잡도 이론에서 NP에 속하지만, P 또는 NP-완전에 속하는지는 아직 밝혀지지 않은 몇 안 되는 문제 중 하나이다. 이 문제는 Garey^영어와 Johnson^영어이 제시한 12개의 미해결 문제 중 하나이며, 다른 하나는 정수 인수분해 문제이다. 만약 이 문제가 NP-완전으로 판명된다면, 다항식 계층은 유한 수준으로 붕괴될 것이다.

4.1.1. 알고리즘 개발

그래프 동형 사상 문제는 화학정보학, 수리화학, 전자 설계 자동화 등 다양한 분야에 응용된다. 이 문제에 대한 주요 연구는 알고리즘 설계와 계산 복잡도 이론 조사에 초점을 맞추고 있다.

2015년 11월, 시카고 대학교의 러즐로 바바이는 그래프 동형 사상 문제를 준다항 시간에 풀 수 있음을 증명했다고 주장했다. 2017년 1월, 바바이는 잠시 준다항성 주장을 철회하고 준지수 시간 복잡도 경계를 언급했으나, 5일 후 원래 주장을 복원했다.

와이스파일러-레만 그래프 동형 사상 검사는 그래프 동형 사상을 발견하기 위한 휴리스틱 방법으로 사용할 수 있다. 이 검사에 실패하면 두 그래프가 동형이 아님을 보장하지만, 성공하더라도 동형임을 보장하지는 않는다. 동형 사상을 확실하게 감지하는 알고리즘의 일반화가 존재하지만, 실행 시간은 지수적이다.

2001년 Cordella 등이 개발한 vf2 알고리즘은 또 다른 잘 알려진 그래프 동형 사상 알고리즘이다. vf2 알고리즘은 깊이 우선 탐색을 사용하여 두 그래프 사이의 동형 사상을 점진적으로 구축한다. 이 알고리즘은 검색 공간을 줄이기 위한 규칙을 사용하여 수천 개의 노드가 있는 그래프를 효율적으로 처리할 수 있지만, 최악의 경우 지수 시간 복잡도를 가진다.

4.1.2. 복잡도 분석

그래프 동형사상 문제는 계산 복잡도 이론에서 NP에 속하지만, 그 부분집합인 P 또는 NP-완전에 속하는지는 밝혀지지 않은 몇 안 되는 문제 중 하나이다. 만약 이 문제가 NP-완전하다면 다항식 계층이 유한 수준으로 붕괴된다.

2015년 11월, 시카고 대학교의 러즐로 바바이는 그래프 동형사상 문제가 준다항 시간에 풀 수 있음을 증명했다고 주장했다. 그러나 2017년 1월, 바바이는 잠시 준다항성 주장을 철회하고 준지수 시간 복잡도 경계를 언급했다가 5일 후 원래 주장을 복원했다.

부분 그래프 동형 사상 문제는 NP-완전으로 알려져 있다.

그래프 동형사상 문제에 대한 주요 연구는 일반적인 문제와 특수한 종류의 그래프에 대한 빠르고 계산 복잡성 이론 조사를 포함한 알고리즘 설계에 초점을 맞추고 있다.

4.1.3. 양자 알고리즘

양자 컴퓨터를 사용하여 그래프 동형 사상 문제를 다항 시간 내에 풀 수 있는지에 관해서도 활발히 연구가 진행되고 있다.