부분 그래프와 신장 부분 그래프

부분 그래프(subgraph)를 추측해 보기란 어렵지 않습니다. 정의해 보자면 그래프 G'가 G에 대해 V(G') ⊆ (G)고 E(G') ⊆ E(G)면 그래프 G'는 그래프 G의 부분 그래프입니다. 몇 가지 예제로 살펴보겠습니다.

그림 6-10을 보면 G'는 에지 (0, 1)은 없지만 부분 그래프 조건에 만족합니다. G''도 에지가 많이 없고 정점 3도 없지만 역시 부분 그래프입니다. 심지어 G'''를 보면 정점 0만 있어도 부분 그래프입니다.

▲ 그림 6-10 부분 그래프