그래프 이론에서 신장 부분 그래프(身長部分graph, 영어: spanning subgraph 스패닝 서브그래프^[*]) 또는 생성 부분 그래프(生成部分graph)는 모든 꼭짓점을 포함하는 부분 그래프이다.

그래프 ${\displaystyle \Gamma }$의 부분 그래프

${\displaystyle \Gamma '\subseteq \Gamma }$

에 대하여, 만약

${\displaystyle \operatorname {V} (\Gamma ')=\operatorname {V} (\Gamma )}$

라면, ${\displaystyle \Gamma '}$을 ${\displaystyle \Gamma }$의 신장 부분 그래프라고 한다. 나무 그래프인 신장 부분 그래프를 신장 나무 부분 그래프(身長나무部分graph, 영어: spanning subtree)라고 하며, 숲 그래프인 신장 부분 그래프를 신장 숲 부분 그래프(身長숲部分graph, 영어: spanning subforest)라고 한다.

신장 부분 그래프 가운데, ${\displaystyle r}$-정규 그래프인 것을 ${\displaystyle r}$차 인자(${\displaystyle r}$次因子, 영어: ${\displaystyle r}$-factor)라고 한다. 특히, 1차 인자는 완벽 부합이라고 한다. (0차 인자는 꼭짓점 집합 위의 무변 그래프이다.)

• 
  페테르센 그래프에서, 붉은 변들은 1차 인자(완벽 부합)를 이루며, 푸른 변들은 2차 인자를 이룬다.
• 
  데자르그 그래프에서, 붉은 색의 변들 · 푸른 색의 변들 · 녹색의 변들은 각각 1차 인자(완벽 부합)를 이룬다.

다음이 주어졌다고 하자.

• 연결 유한 그래프 ${\displaystyle \Gamma }$
• 함수 ${\displaystyle f\colon \operatorname {E} (\Gamma )\to \mathbb {R} }$. 이를 비용 함수(費用函數, 영어: cost function)이라고 하자.

${\displaystyle \Gamma }$의 최소 비용 신장 나무 부분 그래프(最小費用身長部分graph, minimum cost spanning tree)는 ${\displaystyle \Gamma }$의 연결 신장 부분 그래프 ${\displaystyle \Gamma '\subseteq \Gamma }$가운데, 변들의 비용의 합, 즉

${\displaystyle \sum _{e\in \operatorname {E} (\Gamma ')\subseteq \operatorname {E} (\Gamma )}f(e)\in \mathbb {R} }$

를 최소화하는 것이다. (이는 항상 나무 그래프가 되며, 항상 존재한다.)

임의의 그래프 ${\displaystyle \Gamma }$ 및 임의의 변 집합 ${\displaystyle S\subseteq \operatorname {E} (\Gamma )}$에 대하여, ${\displaystyle \Gamma \setminus \operatorname {E} (\Gamma )}$는 신장 부분 그래프이다. 즉, ${\displaystyle \Gamma }$의 신장 부분 그래프의 수는 ${\displaystyle 2^{|\operatorname {E} (\Gamma )|}}$이다.

특히, ${\displaystyle \operatorname {V} (\Gamma )}$ 위의 무변 그래프 ${\displaystyle \Gamma \setminus \operatorname {E} (\Gamma )}$는 ${\displaystyle \Gamma }$의 신장 숲 그래프이다.

모든 연결 그래프는 적어도 하나의 신장 나무 부분 그래프를 갖는다. (무한 그래프의 경우 이를 증명하려면 선택 공리가 필요하다.)

연결 그래프의 경우, 신장 부분 나무 그래프는 그 순환 매트로이드의 기저(극대 독립 집합)와 같다.

유한 연결 그래프의 최소 비용 신장 나무 부분 그래프는 프림 알고리즘이나 크러스컬 알고리즘을 사용하여 다항 시간 안에 찾을 수 있다.

네 개의 꼭짓점을 갖는 완전 그래프 ${\displaystyle K_{4}}$는 총 ${\displaystyle 2^{6}=64}$개의 신장 부분 그래프를 가지며, 그 가운데 다음 16개가 신장 나무이다.

보다 일반적으로, 케일리 공식에 따라, ${\displaystyle K_{n}}$의 ${\displaystyle 2^{n(n-1)/2}}$개의 신장 부분 그래프 가운데

${\displaystyle n^{n-2}}$

개가 신장 나무이다.

나무 그래프 ${\displaystyle T}$의 신장 부분 나무 그래프는 ${\displaystyle T}$ 자신 밖에 없다.

최소 비용 신장 나무 부분 그래프를 구하는 문제는 1926년에 오타카르 보루프카(체코어: Otakar Borůvka, 1899~1995)가 최초로 제시하였다.^[1][2][3]

위키미디어 공용에 관련된
미디어 분류가 있습니다.

신장 나무

• “Factorization”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “One-factor”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “One-factorization”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Spanning tree”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Spanning subgraph”. 《ProofWiki》 (영어). 
• “Spanning tree”. 《ProofWiki》 (영어). 
• “Maximum spanning tree”. 《ProofWiki》 (영어). 
• “Minimum spanning tree”. 《ProofWiki》 (영어).