정의
그래프 동형 사상(英: graph homomorphism)은 두 그래프 $G = (V_G, E_G)$와 $H = (V_H, E_H)$ 사이의 함수 $f: V_G \rightarrow V_H$ 로, 모든 변(edge) $(u,v) \in E_G$ 에 대하여 $(f(u), f(v)) \in E_H$ 를 만족하는 경우를 말한다. 즉, 원 그래프의 인접 관계가 목표 그래프의 인접 관계로 보존되는 사상이다.
개요
그래프 동형 사상은 그래프 이론에서 구조 보존을 다루는 기본적인 개념으로, 그래프 색칠, 제약 만족 문제, 네트워크 모델링 등 다양한 분야에서 활용된다. 동형 사상은 완전동형(동형사상, 즉 일대일·전사)보다 약한 관계이며, 두 그래프가 동형 사상을 서로 주고받을 경우 동형 관계가 성립한다는 점이 특징이다. 동형 사상은 종종 $G \rightarrow H$ 형태로 표기된다.
어원/유래
‘동형(同形)’은 ‘같은 형태’를 의미하는 한자어이며, ‘사상(寫像)’은 ‘함수’를 뜻한다. 따라서 ‘동형 사상’은 ‘형태를 동일하게 보존하는 함수’라는 의미이다. ‘그래프’는 영단어 graph를 그대로 차용한 용어이며, ‘그래프 동형 사상’이라는 표기는 20세기 후반에 서구의 그래프 이론 연구가 한국에 소개되면서 정착된 것으로, 정확한 최초 사용 시점은 확인되지 않는다.
특징
- 보존성: 정점 간 인접성이 목표 그래프에서도 유지된다.
- 비일대일성: 동형 사상은 일대일·전사일 필요가 없으며, 여러 정점이 하나의 정점으로 매핑될 수 있다.
- 구조적 활용: 그래프 색칠 문제는 목표 그래프를 완전 그래프 $K_k$ 로 하는 동형 사상의 존재 여부와 동등하다.
- 계산 복잡도: 일반적인 그래프 동형 사상의 존재 여부를 판단하는 문제는 NP-완전(NP-complete)인 경우가 많다(특정 목표 그래프에 한정될 때는 다항 시간 알고리즘이 존재한다).
- 범주론적 관점: 그래프와 그래프 동형 사상으로 이루어진 범주는 ‘그래프 범주(Graph Category)’라 불리며, 범주 이론에서 중요한 예시가 된다.
관련 항목
- 그래프 동형(同形, graph isomorphism)
- 그래프 색칠 문제(그래프 컬러링)
- 제약 만족 문제(CSP, Constraint Satisfaction Problem)
- 그래프 사상(그래프 매핑, graph mapping)
- 범주론의 그래프 범주(Graph Category)
- NP-완전 문제(NP-complete problem)
본 내용은 그래프 이론 및 컴퓨터 과학 분야에서 일반적으로 인정받는 정의와 특성을 기반으로 작성되었으며, 별도의 논란이 없는 표준적 정보를 제공한다.