그래프 동형 사상

그래프 이론에서 그래프의 동형사상(-同型寫像, 영어: isomorphism of graph)이란 두 그래프 G와 H에 대해, G의 임의의 두 꼭짓점 u와 v가 주어졌을 때 u와 v가 G에서 인접인 것과 $f(u)$와 $f(v)$가 H에서 인접인 것이 필요충분조건이 되도록 하는 함수

$f\colon V(G)\to V(H)$

가 존재하는 일대일 대응이다. 그래프의 동형사상은 '변-보존 일대일 대응'이라고도 하는데, 이는 구조를 보존하는 일대일 대응인 동형사상의 의미와도 일치한다.

두 그래프 G와 H 간에 동형사상이 존재하면, 두 그래프는 동형(同型, 영어: isomorphic)이라고 하고 $G\simeq H$라 쓴다. 일대일 대응이 자기 자신으로의 사상인 경우, 즉 G와 H가 같은 그래프인 경우의 동형사상은 G의 자기동형사상이라 한다.

그래프의 동형사상은 그래프 간에 주어진 동치관계로 볼 수 있으며, 따라서 모든 그래프들은 동치류의 원소로 분류할 수 있다.

아래는 서로 다른 것처럼 보이지만 동형인 두 그래프이다.

그래프 G	그래프 H	G와 H의 동형 관계
		f(a) = 1 f(b) = 6 f(c) = 8 f(d) = 3 f(g) = 5 f(h) = 2 f(i) = 4 f(j) = 7

변형

위에서는 무향이고 라벨이 없으며, 가중치가 없는 그래프에 대하여 동형사상을 정의하였지만, 방향이나 가중치, 라벨 등이 부여된 그래프에 대해 각 대응하는 요소를 보존하도록 동형을 정의할 수도 있다.

라벨 그래프의 동형사상

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

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

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

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

휘트니 정리

휘트니 정리의 예외:두 그래프는 선 그래프가 같지만 동형이 아니다.

해슬러 휘트니가 증명한 휘트니 정리에 따르면, 두 연결 그래프가 동형사상인 것은 두 그래프의 선 그래프가 동형사상인 것과 동치이다. 단 완전 그래프 K₃과 완전 이분 그래프 K_1,3은 예외이다. 휘트니 정리는 하이퍼그래프로도 확장할 수 있다.

그래프 동형사상 문제

두 유한 그래프가 동형인지 판단하는 문제를 그래프 동형사상 문제라 한다. 그래프 동형사상 문제는 화학정보학, 수리화학(화합물의 식별), 전자 설계 자동화(전자 회로 디자인의 일치 여부 판단) 등에 적용할 수 있다.

그래프 동형사상 문제는 계산 복잡도 이론에서, NP에 속하지만 그 부분집합인 P 또는 NP-완전에 속하는지는 밝혀지지 않은 몇 안 되는 문제 중 하나이다.

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