동형사상 (그래프)

위키백과, 우리 모두의 백과사전.

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

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

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

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

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

그래프 G 그래프 H GH의 동형 관계
Graph isomorphism a.svg Graph isomorphism b.svg 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-완전임이 밝혀졌다.

각주[편집]

  1. p.424
  2. "Efficient Method to Perform Isomorphism Testing of Labeled Graphs" in: Computational Science and Its Applications - ICCSA 2006, pp 422–431
  3. Pierre-Antoine Champ in, Christine Sol-non, "Measuring the Similarity of Labeled Graphs" in: Lecture Notes in Computer Science, vol. 2689, pp 80–95
  4. 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. 
  5. Dirk L. Vertigan, Geoffrey P. Whittle: A 2-Isomorphism Theorem for Hypergraphs. J. Comb. Theory, Ser. B 71(2): 215–230. 1997.