신장 부분 그래프

파일:4x4 grid spanning tree.svg

그래프의 신장 부분 나무 그래프

파일:Натурализация гамильтоновых циклов.jpg

8*8 그리드 그래프의 세 가지 예

파일:Graph with all its spanning trees.svg

왼쪽의 그래프는 오른쪽과 같이 총 8개의 신장 부분 나무 그래프들을 갖는다.

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

정의

그래프 $\Gamma$의 부분 그래프

${\Gamma }^{\prime }\subseteq \Gamma$

에 대하여, 만약

$\mathrm{V}({\Gamma }^{\prime })=\mathrm{V}(\Gamma )$

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

인자

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

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

최소 비용 신장 나무

파일:Minimum spanning tree.svg

평면 그래프의 최소 비용 신장 부분 나무 그래프

다음이 주어졌다고 하자.

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

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

$\sum _{e\in \mathrm{E}({\Gamma }^{\prime })\subseteq \mathrm{E}(\Gamma )}f(e)\in ℝ$

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

성질

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

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

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

증명:

연결 그래프 $\Gamma$의 부분 그래프 가운데 나무 그래프인 것들의 집합 $𝒯$를 생각하자.

$𝒯=\{T\subseteq \Gamma :|\mathrm{Conn}(T)|=1,{\mathrm{H}}_1(T)=0\}$

이는 부분 그래프 관계에 따라 부분 순서 집합을 이룬다. 나무 그래프들의 사슬의 합집합은 항상 나무 그래프이다. (귀류법을 써 만약 아니라고 가정하면, 모든 순환은 유한 그래프이므로, 사슬의 어떤 유한한 단계에서 이러한 순환이 이미 존재해야 한다.) 즉, $𝒯$는 닫힌 원순서 집합을 이룬다.

이 때문에 초른 보조정리에 따라 $𝒯$는 극대 원소를 갖는다. 그런데 신장 부분 그래프가 아닌 것은 극대 원소가 될 수 없다. (귀류법을 써 만약 아니라고 가정하면, 극대 원소 $T$에 속하지 않는 꼭짓점 $v\in \mathrm{V}(\Gamma )\setminus \mathrm{V}(T)$ 및 $v$와 $T$를 잇는 임의의 최소 경로 $P\subseteq \Gamma$에 대하여, $P\cup T$ 역시 나무 그래프를 이루며, $P\cup T⊋T$이다.)

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

알고리즘

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

예

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

파일:Spanning Trees qtl1.svg

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

$n^{n-2}$

개가 신장 나무이다.

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

역사

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

외부 링크

• “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》.