부분 그래프

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

정의

그래프 ${\displaystyle G}$의 부분 그래프 ${\displaystyle H\subset G}$는 다음을 만족시키는 그래프이다.

• ${\displaystyle V(H)\subset V(G)}$
• ${\displaystyle E(H)\subset E(G)}$

그래프 ${\displaystyle G}$의 유도 부분 그래프(誘導部分graph, 영어: induced subgraph) ${\displaystyle H}$는 다음을 만족시키는 그래프이다.

• ${\displaystyle V(H)\subset V(G)}$
• ${\displaystyle uv\in E(H)\iff u,v\in V(H)\land uv\in E(G)}$

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

예

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

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

• ${\displaystyle G_{1}}$, ${\displaystyle G_{2}}$, ${\displaystyle G_{3}}$ 모두 ${\displaystyle G}$의 부분 그래프이다.
• ${\displaystyle G_{1}}$은 변 26과 변67을 포함하지 않으므로 유도 부분 그래프가 아니다. 반면, ${\displaystyle G_{2}}$와 ${\displaystyle G_{3}}$는 유도 부분 그래프이다.
• ${\displaystyle G_{3}}$는 ${\displaystyle G_{2}}$의 유도 부분 그래프이다.

참고 문헌

• Diestel, Reinhard (2010). 《Graph theory》. Graduate Texts in Mathematics (영어) 173 4판. ISBN 978-3-642-14278-9. Zbl 1204.05001.  CS1 관리 - 추가 문구 (링크)

외부 링크

• Weisstein, Eric Wolfgang. “Subgraph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Edge-induced subgraph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Vertex-induced subgraph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Supergraph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 

같이 보기

• 마이너 (그래프 이론)