📂그래프이론

서브 그래프

정의 ¹

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

설명

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

예시

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

컴포넌트

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

그래프의 뺄셈

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

• 에지: $e \in E(G)$ 에 대해 $E(G) - e$ 는 $G$ 의 에지 $e$ 를 제거한 그래프로 정의되며 자명하게도 $G$ 의 서브 그래프가 된다. 이러한 그래프의 뺄셈 연산 $-$ 는 에지의 집합 $E \subset E(G)$ 에 대해서도 확장할 수 있다. $E(G) - E$ 는 $G$ 의 에지들의 부분집합 $E$ 의 에지들을 제거한 그래프로 정의되며 마찬가지로 $G$ 의 서브 그래프가 된다.
• 버텍스: $v \in V(G)$ 에 대해 $E(G) - v$ 는 $G$ 의 버텍스 $v$ 와 $v$ 에 딸린 모든 에지들을 제거한 그래프로 정의된다. 버텍스의 경우에도 버텍스의 집합 $V \subset V(G)$ 에 대해서 확장할 수 있다. $E(G) - V$ 는 $G$ 의 버텍스의 부분집합 $V$ 의 버텍스들과 그에 딸린 에지들을 제거한 그래프로 정의되며, 당연히 $G$ 의 서브 그래프가 된다.
• 그래프 수축: 위 두 뺄셈에서 기호가 $-$ 인 것에 주목하라. 집합 뺄셈 기호 $\setminus$ 는 그래프에서 에지를 Contraction한다는 의미로 쓰인다. 에지가 수축된다는 것은 다음과 같이 에지 $e$ 가 사라지고 $e$ 에 달려있던 두 끝점 $v$ 와 $w$ 를 같은 것으로 취급한다는 것이다.

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

스패닝

$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$ 의 성질을 어느정도 물려받았음을 짐작할 수 있다.