부분 그래프

그래프 이론에서 부분 그래프(部分graph, )는 어떤 그래프의 꼭짓점과 변 가운데 일부로 이루어진 그래프이다.

 정의 
그래프 의 부분 그래프 는 다음을 만족시키는 그래프이다.


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



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

 예 
다음 네 개의 그래프를 생각해 보자.
파일:Teilgraphenbeziehungen.svg
이들 사이의 관계는 다음과 같다.
 , ,  모두 의 부분 그래프이다.
 은 변 26과 변67을 포함하지 않으므로 유도 부분 그래프가 아니다. 반면, 와 는 유도 부분 그래프이다.
 는 의 유도 부분 그래프이다.

 참고 문헌 


 외부 링크 





 같이 보기 
 마이너 (그래프 이론)

분류:그래프 이론