부분 그래프

틀:위키데이터 속성 추적 그래프 이론에서 부분 그래프(部分graph, 틀:Llang)는 어떤 그래프의 꼭짓점과 변 가운데 일부로 이루어진 그래프이다.

정의

그래프 $G$ 의 부분 그래프 $H \subset G$ 는 다음을 만족시키는 그래프이다.

그래프 $G$ 의 유도 부분 그래프(誘導部分graph, 틀:Llang) $H$ 는 다음을 만족시키는 그래프이다.

그래프 $G$ 의 부분 그래프 가운데, $G$ 의 모든 꼭짓점을 포함하는 것을 인자(因子, 틀:Llang)라고 한다.

다음 네 개의 그래프를 생각해 보자.

이들 사이의 관계는 다음과 같다.

$G_{1}$ , $G_{2}$ , $G_{3}$ 모두 $G$ 의 부분 그래프이다.
$G_{1}$ 은 변 26과 변67을 포함하지 않으므로 유도 부분 그래프가 아니다. 반면, $G_{2}$ 와 $G_{3}$ 는 유도 부분 그래프이다.
$G_{3}$ 는 $G_{2}$ 의 유도 부분 그래프이다.