신장 부분 그래프 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:4x4 grid spanning tree.svg|섬네일|오른쪽|그래프의 신장 부분 나무 그래프]]
[[파일:Натурализация гамильтоновых циклов.jpg|섬네일|8*8 [[격자 그래프|그리드 그래프]]의 세 가지 예]]
[[파일:Graph with all its spanning trees.svg|섬네일|오른쪽|왼쪽의 그래프는 오른쪽과 같이 총 8개의 신장 부분 나무 그래프들을 갖는다.]]
[[그래프 이론]]에서 '''신장 부분 그래프'''(身長部分graph, {{llang|en|spanning subgraph|스패닝 서브그래프}}) 또는 '''생성 부분 그래프'''(生成部分graph)는 모든 꼭짓점을 포함하는 [[부분 그래프]]이다.

== 정의 ==
[[그래프]] <math>\Gamma</math>의 [[부분 그래프]]
:<math>\Gamma'\subseteq\Gamma</math>
에 대하여, 만약
:<math>\operatorname V(\Gamma')=\operatorname V(\Gamma)</math>
라면, <math>\Gamma'</math>을 <math>\Gamma</math>의 '''신장 부분 그래프'''라고 한다. [[나무 그래프]]인 신장 부분 그래프를 '''신장 나무 부분 그래프'''(身長나무部分graph, {{llang|en|spanning subtree}})라고 하며, [[숲 그래프]]인 신장 부분 그래프를 '''신장 숲 부분 그래프'''(身長숲部分graph, {{llang|en|spanning subforest}})라고 한다.

=== 인자 ===
신장 부분 그래프 가운데, <math>r</math>-[[정규 그래프]]인 것을 '''<math>r</math>차 인자'''(<math>r</math>次因子, {{llang|en|<math>r</math>-factor}})라고 한다. 특히, 1차 인자는 '''[[완벽 부합]]'''이라고 한다. (0차 인자는 꼭짓점 집합 위의 [[무변 그래프]]이다.)
<gallery>
Petersen-graph-factors.svg|[[페테르센 그래프]]에서, 붉은 변들은 1차 인자([[완벽 부합]])를 이루며, 푸른 변들은 2차 인자를 이룬다.
Desargues graph 3color edge.svg|[[데자르그 그래프]]에서, 붉은 색의 변들 · 푸른 색의 변들 · 녹색의 변들은 각각 1차 인자([[완벽 부합]])를 이룬다.
</gallery>

=== 최소 비용 신장 나무 ===
[[파일:Minimum spanning tree.svg|섬네일|오른쪽|[[평면 그래프]]의 최소 비용 신장 부분 나무 그래프]]
다음이 주어졌다고 하자.
* [[연결 그래프|연결]] [[유한 그래프]] <math>\Gamma</math>
* 함수 <math>f\colon\operatorname E(\Gamma)\to\mathbb R</math>. 이를 '''비용 함수'''(費用函數, {{llang|en|cost function}})이라고 하자.

<math>\Gamma</math>의 '''최소 비용 신장 나무 부분 그래프'''(最小費用身長部分graph, {{lang|en|minimum cost spanning tree}})는 <math>\Gamma</math>의 [[연결 그래프|연결]] 신장 부분 그래프 <math>\Gamma'\subseteq\Gamma</math>가운데, 변들의 비용의 합, 즉
:<math>\sum_{e\in\operatorname E(\Gamma')\subseteq\operatorname E(\Gamma)}f(e)\in\mathbb R</math>
를 최소화하는 것이다. (이는 항상 [[나무 그래프]]가 되며, 항상 존재한다.)

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

특히, <Math>\operatorname V(\Gamma)</math> 위의 [[무변 그래프]] <math>\Gamma\setminus\operatorname E(\Gamma)</math>는 <math>\Gamma</math>의 신장 숲 그래프이다.

모든 [[연결 그래프]]는 적어도 하나의 신장 나무 부분 그래프를 갖는다. (무한 그래프의 경우 이를 증명하려면 [[선택 공리]]가 필요하다.)
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
[[연결 그래프]] <math>\Gamma</math>의 부분 그래프 가운데 [[나무 그래프]]인 것들의 집합 <math>\mathcal T</math>를 생각하자.
:<math>\mathcal T=\left\{T\subseteq\Gamma\colon
|\operatorname{Conn}(T)|=1,\;\operatorname H_1(T)=0\right\}</math>
이는 [[부분 그래프]] 관계에 따라 [[부분 순서 집합]]을 이룬다. 나무 그래프들의 [[사슬 (순서론)|사슬]]의 합집합은 항상 [[나무 그래프]]이다. ([[귀류법]]을 써 만약 아니라고 가정하면, 모든 [[순환 (그래프 이론)|순환]]은 [[유한 그래프]]이므로, 사슬의 어떤 유한한 단계에서 이러한 순환이 이미 존재해야 한다.) 즉, <math>\mathcal T</math>는 [[닫힌 원순서 집합]]을 이룬다.

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

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

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

== 예 ==
네 개의 꼭짓점을 갖는 [[완전 그래프]] <math>K_4</math>는 총 <math>2^6=64</math>개의 신장 부분 그래프를 가지며, 그 가운데 다음 16개가 신장 나무이다.
:[[파일:Spanning Trees qtl1.svg|300px]]
보다 일반적으로, [[나무 그래프|케일리 공식]]에 따라, <math>K_n</math>의 <math>2^{n(n-1)/2}</math>개의 신장 부분 그래프 가운데
:<math>n^{n-2}</math>
개가 신장 나무이다.

[[나무 그래프]] <math>T</math>의 신장 부분 나무 그래프는 <math>T</math> 자신 밖에 없다.

== 역사 ==
최소 비용 신장 나무 부분 그래프를 구하는 문제는 1926년에 오타카르 보루프카({{llang|cs|Otakar Borůvka}}, 1899~1995)가 최초로 제시하였다.<ref>{{저널 인용|이름=Otakar|성=Borůvka|제목=O jistém problému minimálním | 저널=Práce moravské přírodovědecké společnosti|권=3|날짜=1926 | 쪽=37–58 | jfm=57.1343.06 | url= http://hdl.handle.net/10338.dmlcz/500114 | 언어=cs }}</ref><ref>{{저널 인용|이름=Otakar|성=Borůvka|제목=Příspěvek k řešení otázky ekonomické stavby elektrovodných sítí | 저널=Elektrotechnický obzor | 권=15 |날짜=1926-03-05 | 쪽=153–154 | url=http://hdl.handle.net/10338.dmlcz/500190 |  언어=cs }}</ref><ref>{{저널 인용|제목=On the history of the minimum spanning tree problem | 이름=Ronald Lewis |성=Graham | 저자링크=로널드 그레이엄 | 이름2=Pavol | 성2=Hell | url=http://www.math.ucsd.edu/~ronspubs/85_07_minimum_spanning_tree.pdf | 저널=Institute of Electrical and Electronics Engineers Annals of the History of Computing | 권=7 | 호=1 | 날짜=1985-01 | 쪽=43–57 | doi= 10.1109/MAHC.1985.10011 | 언어=en}}</ref>

== 각주 ==
{{각주}}

== 외부 링크 ==
{{위키공용분류|Spanning trees|신장 나무}}
* {{eom|title=Factorization}}
* {{eom|title=One-factor}}
* {{eom|title=One-factorization}}
* {{매스월드|id=SpanningTree|title=Spanning tree}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Spanning_Subgraph | 제목=Spanning subgraph | 웹사이트=ProofWiki | 언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Spanning_Tree | 제목=Spanning tree | 웹사이트=ProofWiki | 언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Maximum_Spanning_Tree | 제목=Maximum spanning tree | 웹사이트=ProofWiki | 언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Definition:Minimum_Spanning_Tree | 제목=Minimum spanning tree | 웹사이트=ProofWiki | 언어=en}}

{{전거 통제}}

[[분류:그래프 이론의 계산 문제]]
[[분류:트리 구조]]
[[분류:선택 공리]]