그래프 동형 사상
그래프 이론에서 그래프의 동형사상(-同型寫像, 영어: isomorphism of graph)이란 두 그래프 G와 H에 대해, G의 임의의 두 꼭짓점 u와 v가 주어졌을 때 u와 v가 G에서 인접인 것과 와 가 H에서 인접인 것이 필요충분조건이 되도록 하는 함수
가 존재하는 일대일 대응이다. 그래프의 동형사상은 '변-보존 일대일 대응'이라고도 하는데, 이는 구조를 보존하는 일대일 대응인 동형사상의 의미와도 일치한다.
두 그래프 G와 H 간에 동형사상이 존재하면, 두 그래프는 동형(同型, 영어: isomorphic)이라고 하고 라 쓴다. 일대일 대응이 자기 자신으로의 사상인 경우, 즉 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]
두 번째 정의에서 동형사상은 라벨의 동치류를 보존하는 변-보존 일대일 대응이다. 즉, 같은 라벨을 가진 꼭짓점들은 대응되는 그래프에서의 라벨이 모두 같다.[3]
예를 들어 첫 번째 정의에서, 각 꼭짓점이 1과 2로 번호매김된 그래프의 자기동형사상은 동일한 꼭짓점으로 사상하는 1가지 경우뿐이다. 그러나 두 번째 정의에서는 서로 다른 꼭짓점으로 사상되는 경우도 포함하여 자기동형사상은 2가지가 된다.(이 예시에서는 같은 라벨을 가지는 꼭짓점이 각각 하나뿐이다.)
휘트니 정리
[편집]해슬러 휘트니가 증명한 휘트니 정리[4]에 따르면, 두 연결 그래프가 동형사상인 것은 두 그래프의 선 그래프가 동형사상인 것과 동치이다. 단 완전 그래프 K3과 완전 이분 그래프 K1,3은 예외이다. 휘트니 정리는 하이퍼그래프로도 확장할 수 있다.[5]
그래프 동형사상 문제
[편집]두 유한 그래프가 동형인지 판단하는 문제를 그래프 동형사상 문제라 한다. 그래프 동형사상 문제는 화학정보학, 수리화학(화합물의 식별), 전자 설계 자동화(전자 회로 디자인의 일치 여부 판단) 등에 적용할 수 있다.
그래프 동형사상 문제는 계산 복잡도 이론에서, NP에 속하지만 그 부분집합인 P 또는 NP-완전에 속하는지는 밝혀지지 않은 몇 안 되는 문제 중 하나이다.
그래프 동형사상 문제의 일반화에 해당하는 부분그래프 동형사상 문제(주어진 그래프의 부분그래프가 다른 그래프와 동형인지 판단하는 문제)는 NP-완전임이 밝혀졌다.
각주
[편집]- ↑ p.424
- ↑ "Efficient Method to Perform Isomorphism Testing of Labeled Graphs" in: Computational Science and Its Applications - ICCSA 2006, pp 422–431
- ↑ Pierre-Antoine Champ in, Christine Sol-non, "Measuring the Similarity of Labeled Graphs" in: Lecture Notes in Computer Science, vol. 2689, pp 80–95
- ↑ Whitney, Hassler (January 1932). “Congruent Graphs and the Connectivity of Graphs”. 《American Journal of Mathematics》 54 (1): 150–168. doi:10.2307/2371086. hdl:10338.dmlcz/101067. JSTOR 2371086.
- ↑ Dirk L. Vertigan, Geoffrey P. Whittle: A 2-Isomorphism Theorem for Hypergraphs. J. Comb. Theory, Ser. B 71(2): 215–230. 1997.