일부를 남기는 작업
삼각형 A,B,C에서 간선 AB와 BC만 남기고 정점 세 개를 유지하면 경로 모양의 부분 그래프를 얻는다. 원래 없던 간선이나 정점을 새로 넣는 것은 부분 그래프를 고르는 작업과 다르다.
정점과 간선의 선택
정점을 지우면 그 정점에 닿는 간선도 함께 지워야 한다. 반면 간선만 지우고 그 끝점은 그대로 둘 수 있다. 정점이 고립되어 남아 있어도 그래프를 이룰 수 있다.
유도 부분 그래프와 비교
일반 부분 그래프에서는 선택한 정점 사이에 원래 있던 간선 일부를 빼도 된다. 유도 부분 그래프는 선택한 정점 사이의 원래 간선을 모두 남겨야 하므로 더 강한 조건이다.
모든 정점을 남기면
원래 정점 집합을 모두 유지하는 부분 그래프를 신장 부분 그래프라고 한다. 신장 트리는 이런 부분 그래프 중 연결되어 있고 순환이 없는 경우다.
관련 문서
유도 부분 그래프 / 신장 트리 / 트리 (그래프 이론) / 정점 (그래프 이론) / 간선 (그래프 이론) / 부분집합