서브 그래프

서브 그래프

정의 1

그래프 $G$ 에 대해서 그래프 $H$ 가 $V(H) \subset V(G)$ 와 $ E(H) \subset E(G)$ 를 만족하면 $H$ 가 $G$ 의 서브 그래프라 한다.

설명

주의해야하는 것은 $H$ 가 $G$ 의 서브 그래프라고 $H \subset G$ 와 같이 나타내면 안 된다는 것이다. 서브 그래프는 직접적으로 그래프 이론에서 어떤 관심의 대상이 된다기보단 당연하고 상식적인 용어로써 의미가 있다.

예시

서브 그래프를 정의함으로써 생각할 수 있는 것들의 예시로 다음과 같은 것들을 소개한다:

컴포넌트

단절 그래프 $D$ 의 컴포넌트들은 모두 $D$ 의 서브 그래프다.

그래프의 뺄셈

그래프 $G$ 가 주어져 있다고 하자:

이러한 그래프의 뺄셈은 그래프를 구축하는 알고리즘 등을 이야기할 때 아주 편리한 도구가 된다.

스패닝

$G$ 의 서브그래프 $H$ 가 $V\left( H \right) = V(G)$ 를 만족하면 $H$ 를 $G$ 의 Spanning이라고 한다. 쉽게 말해, 버텍스는 그대로 유지되지만 에지만 제거되었을 수 있는 서브그래프다. 그래프의 뺄셈에서 에지를 뺀 케이스에 속한다.

유도 그래프

$G$ 의 서브그래프 $H$ 가 $$ E \left( H \right) = \left\{ uv \in E(G) : u,v \in V \left( H \right) \right\} $$ 를 만족하면 Induced Graph라고 한다. 인듀스드 그래프는 스패닝과 달리 그래프의 뺄셈에서 버텍스를 뺀 케이스며, $G$ 의 서브 그래프일 뿐 어떤 규칙으로 에지가 제거되었는지 모를 스패닝과 달리 버텍스가 보존된 부분엔 에지도 보존되어있으므로 원래 그래프 $G$ 의 성질을 어느정도 물려받았음을 짐작할 수 있다.


  1. Wilson. (1970). Introduction to Graph Theory: p12. ↩︎

댓글