정의
부분 그래프(subgraph)란 주어진 그래프 $G = (V, E)$에서 정점 집합 $V' \subseteq V$와 그 정점 집합에 포함된 간선 집합 $E' \subseteq E$가 이루는 그래프 $G' = (V', E')$를 말한다. 즉, 원 그래프의 일부 정점과 그 사이에 존재하는 일부 혹은 전부의 간선으로 구성된 그래프이다.
분류
- 인덕션 서브그래프(Induced Subgraph)
- 정점 집합 $V'$가 주어졌을 때, $V'$에 속하는 모든 원 그래프의 간선을 포함한다. 즉, $E' = {(u, v) \in E \mid u, v \in V'}$.
- 스패닝 서브그래프(Spanning Subgraph)
- 정점 집합이 원 그래프와 동일($V' = V$)하고, 간선 집합은 원 그래프의 부분집합($E' \subseteq E$)인 경우이다.
- 에지 서브그래프(Edge Subgraph)
- 정점 집합은 원 그래프와 동일하거나 그 일부일 수 있으며, 간선 집합이 원 그래프의 부분집합인 경우를 통틀어 사용한다.
특징 및 성질
- 포함 관계: $G'$가 $G$의 부분 그래프이면, $G$는 $G'$의 초과 그래프(augmented graph)라고도 부른다.
- 연결성 보존: 원 그래프가 연결 그래프일 경우, 모든 스패닝 서브그래프는 역시 연결성을 유지한다. 단, 일반적인 부분 그래프는 연결성을 잃을 수 있다.
- 트리와 포레스트: 트리의 부분 그래프는 역시 무사이클이며, 포레스트의 부분 그래프는 포레스트가 된다.
- 그래프 연산: 두 그래프의 합집합, 교집합, 차집합 연산을 통해 부분 그래프를 구성할 수 있다.
응용 분야
- 알고리즘 설계: 최소 신장 트리, 최대 매칭 등에서 부분 그래프를 이용해 문제를 부분적으로 해결한다.
- 네트워크 분석: 사회·통신 네트워크에서 특정 노드 집합에 대한 지역 구조를 파악할 때 부분 그래프를 추출한다.
- 패턴 매칭: 서브그래프 동형성 문제는 화학 구조 검색, 이미지 인식 등에서 핵심적인 역할을 한다.
어원
- "부분"은 한국어에서 '일부', '일부적인'이라는 의미이며, "그래프"는 수학 및 컴퓨터 과학에서 정점과 간선으로 이루어진 구조를 가리키는 영어 단어 graph의 음역이다. 따라서 "부분 그래프"는 “전체 그래프의 일부에 해당하는 그래프”라는 뜻을 그대로 반영한 용어이다.
참고 문헌
- Diestel, R. Graph Theory, 5th Edition, Springer, 2017.
- West, D. B. Introduction to Graph Theory, 2nd Edition, Prentice Hall, 2001.
(이상은 공신력 있는 학술 자료에 기반한 객관적 서술이며, 추가적인 상세 정보는 해당 분야의 전문 서적이나 논문을 참조한다.)
