그래프 동형 사상 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''그래프의 동형사상'''(-同型寫像, [[영어]]: isomorphism of graph)이란 두 [[그래프 (수학)|그래프]] ''G''와 ''H''에 대해, ''G''의 임의의 두 꼭짓점 ''u''와 ''v''가 주어졌을 때 ''u''와 ''v''가 ''G''에서 [[그래프 이론 용어#무향 그래프의 기본 정의|인접]]인 것과 <math> f(u) </math>와 <math> f(v) </math>가 ''H''에서 인접인 것이 [[필요충분조건]]이 되도록 하는 함수

<math> f \colon V(G) \to V(H) </math>

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

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

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

아래는 서로 다른 것처럼 보이지만 동형인 두 그래프이다.
{| class="wikitable" style="margin: 1em auto 1em auto"
!그래프 G
!그래프 H
!''G''와 ''H''의 동형 관계
|-
| style="padding-left:2em;padding-right:2em;" |[[파일:Graph_isomorphism_a.svg|200x200픽셀]]
| style="padding-left:1em;padding-right:1em;" |[[파일:Graph_isomorphism_b.svg|210x210픽셀]]
| align="center" style="background-color:white;" |''f''(''a'') = 1

''f''(''b'') = 6

''f''(''c'') = 8

''f''(''d'') = 3

''f''(''g'') = 5

''f''(''h'') = 2

''f''(''i'') = 4

''f''(''j'') = 7
|}

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

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

첫 번째 정의에서 동형사상은 라벨을 보존하는 변-보존 일대일 대응이다.<ref>[https://books.google.com/books?id=14138OJXzy4C&pg=PA424 p.424]</ref><ref>[https://link.springer.com/chapter/10.1007/11751649_46 "Efficient Method to Perform Isomorphism Testing of Labeled Graphs"] in: ''Computational Science and Its Applications - ICCSA 2006'', pp 422–431</ref>

두 번째 정의에서 동형사상은 라벨의 동치류를 보존하는 변-보존 일대일 대응이다. 즉, 같은 라벨을 가진 꼭짓점들은 대응되는 그래프에서의 라벨이 모두 같다.<ref>Pierre-Antoine Champ in, Christine Sol-non, [https://link.springer.com/chapter/10.1007/3-540-45006-8_9 "Measuring the Similarity of Labeled Graphs"] in:  ''Lecture Notes in Computer Science'', vol. 2689, pp 80–95</ref>

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

== 휘트니 정리 ==
[[파일:Whitneys_theorem_exception.svg|오른쪽|섬네일|200x200픽셀|휘트니 정리의 예외:두 그래프는 선 그래프가 같지만 동형이 아니다.]]
[[해슬러 휘트니]]가 증명한 '''휘트니 정리'''<ref>{{저널 인용|title=Congruent Graphs and the Connectivity of Graphs|url=https://archive.org/details/sim_american-journal-of-mathematics_1932-01_54_1/page/n155|journal=American Journal of Mathematics|last=Whitney|first=Hassler|date=January 1932|volume=54|issue=1|pages=150–168|doi=10.2307/2371086|jstor=2371086|hdl=10338.dmlcz/101067|hdl-access=free}}</ref>에 따르면, 두 연결 그래프가 동형사상인 것은 두 그래프의 [[선 그래프]]가 동형사상인 것과 동치이다. 단 [[완전 그래프]] ''K''<sub>3</sub>과 [[완전 이분 그래프]] ''K''<sub>1,3</sub>은 예외이다. 휘트니 정리는 [[하이퍼그래프]]로도 확장할 수 있다.<ref>Dirk L. Vertigan, Geoffrey P. Whittle: A 2-Isomorphism Theorem for Hypergraphs. J. Comb. Theory, Ser. B 71(2): 215–230. 1997.</ref>

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

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

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

== 각주 ==
<references />

[[분류:그래프 이론]]
[[분류:그래프 알고리즘]]