부분 그래프

어떤 그래프의 꼭짓점과 변 가운데 일부로 이루어진 그래프

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

정의

편집

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

  •  
  •  

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

  •  
  •  

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

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

 

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

  •  ,  ,   모두  의 부분 그래프이다.
  •  은 변 26과 변67을 포함하지 않으므로 유도 부분 그래프가 아니다. 반면,   는 유도 부분 그래프이다.
  •   의 유도 부분 그래프이다.

참고 문헌

편집

외부 링크

편집

같이 보기

편집