부분 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[그래프 이론]]에서 '''부분 그래프'''(部分graph, {{llang|en|subgraph|서브그래프}})는 어떤 그래프의 꼭짓점과 변 가운데 일부로 이루어진 그래프이다.

== 정의 ==
[[그래프]] <math>G</math>의 '''부분 그래프''' <math>H\subset G</math>는 다음을 만족시키는 그래프이다.
* <math>V(H)\subset V(G)</math>
* <math>E(H)\subset E(G)</math>
그래프 <math>G</math>의 '''유도 부분 그래프'''(誘導部分graph, {{llang|en|induced subgraph}}) <math>H</math>는 다음을 만족시키는 그래프이다.
* <math>V(H)\subset V(G)</math>
* <math>uv\in E(H)\iff u,v\in V(H)\land uv\in E(G)</math>

그래프 <math>G</math>의 부분 그래프 가운데, <math>G</math>의 모든 꼭짓점을 포함하는 것을 '''인자'''(因子, {{llang|en|factor}})라고 한다.

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

== 참고 문헌 ==
* {{서적 인용|제목=Graph theory|총서=Graduate Texts in Mathematics|권=173|성=Diestel|이름=Reinhard|판=4판|날짜=2010|isbn= 978-3-642-14278-9|url=http://diestel-graph-theory.com/|zbl=1204.05001|언어=en}}

== 외부 링크 ==
* {{매스월드|id=Subgraph|title=Subgraph}}
* {{매스월드|id=Edge-InducedSubgraph|title=Edge-induced subgraph}}
* {{매스월드|id=Vertex-InducedSubgraph|title=Vertex-induced subgraph}}
* {{매스월드|id=Supergraph|title=Supergraph}}

== 같이 보기 ==
* [[마이너 (그래프 이론)]]

[[분류:그래프 이론]]