여기서 그래프 G'가 그래프 G에 대해 V'=V고 E(G') ⊆ E(G)를 만족하면 이 그래프를 신장 부분 그래프(spanning subgraph)라고 합니다. 그림 6-11을 보면 G'는 V'=V를 만족하므로 신장 부분 그래프이지만, G''에는 정점 3이 누락되었으므로 V'=V를 만족하지 못해서 부분 그래프이지만 신장 부분 그래프는 아닙니다.

▲ 그림 6-11 신장 부분 그래프

그래프 용어는 이 정도만 정리하기로 하지요. 다음 절에서는 그래프를 코드에서 어떻게 표현하는지 고민해 보겠습니다.