부합 (그래프 이론) 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Maximal-matching.svg|섬네일|오른쪽|최대 부합이 아닌 극대 부합의 예. 부합에 포함된 변들을 붉은 색으로 굵게 표시하였다.]]
[[파일:Maximum-matching.svg|섬네일|오른쪽|최대 부합의 예. 부합에 포함된 변들을 붉은 색으로 굵게 표시하였다. 이 가운데 (왼쪽부터) 둘째는 완벽 부합이지만, 첫째와 셋째는 완벽 부합이 아닌 최대 부합이다.]]
[[그래프 이론]]에서 '''부합'''(附合, {{llang|en|matching|매칭}})은 서로 만나지 않는 변들의 [[집합]]이다.<ref>{{서적 인용|성=László|이름=Lovász|저자링크=로바스 라슬로|이름2=Michael David|성2=Plummer|날짜=1986|제목=Matching theory|출판사= North-Holland|isbn=0-444-87916-1|doi=10.1016/S0304-0208(08)73633-8|총서=Annals of Discrete Mathematics|권=29|언어=en}}</ref><ref>{{서적 인용|성=Wallis|이름= W. D.|제목=One-factorizations|출판사=Kluwer|날짜=1997|doi=10.1007/978-1-4757-2564-3|isbn=978-0-7923-4323-3|총서=Mathematics and Its Applications|권=390|언어=en}}</ref>

== 정의 ==
[[그래프]] <math>\Gamma</math>의 '''부합''' <math>M\subseteq E(\Gamma)</math>은 다음을 만족시키는, 변들의 부분 집합이다.
* 임의의 <math>e_1,e_2\in M</math>에 대하여, <math>e_1</math>과 <math>e_2</math>가 하나 이상의 꼭짓점을 공유한다면 <math>e_1=e_2</math>이다.
<math>\Gamma</math>의 부합들은 포함 관계에 따라서 [[부분 순서 집합]]을 이룬다. 이 부분 순서에 대하여 극대인 부합을 '''극대 부합'''({{llang|en|maximal matching}})이라고 한다. '''최대 부합'''({{llang|en|maximum matching}})은 극대 부합 가운데, 변의 수가 최대인 부합이다.

=== 완벽 부합 ===
'''완벽 부합'''(完璧附合, {{llang|en|perfect matching}})은 모든 꼭짓점을 덮는 부합이다. 따라서 완벽 부합은 꼭짓점이 짝수 개인 경우에만 존재할 수 있다. 완벽 부합은 당연히 최대 부합이다.

<gallery>
Perfect-simple.svg|완벽 부합의 예
Petersen-graph-factors.svg|[[페테르센 그래프]] 속에서, 붉게 칠해진 변들은 완벽 부합을 이룬다. 보다 일반적으로, 모든 [[일반화 페테르센 그래프]]는 마찬가지로 완벽 부합을 갖는다.
Desargues_graph_3color_edge.svg|[[데자르그 그래프]] 속에서, 붉은 색 · 푸른 색 · 녹색 변들은 각각 완벽 부합을 이룬다.
</gallery>

=== 부합 다항식 ===
유한 그래프 <math>\Gamma</math>가 주어졌으며, 그 가운데 [[집합의 크기|크기]](즉, 포함된 변의 수)가 <math>n</math>인 부합의 수를 <math>m_n</math>이라고 하자. 그렇다면, 그 [[생성 함수 (수학)|생성 함수]]
:<math>Z_\Gamma(x,y)=\sum_{n=0}^\infty m_nx^ny^{|\operatorname V(\Gamma)|-2n}\in\mathbb Z[x,y]</math>
를 <math>\Gamma</math>의 '''부합 다항식'''(附合多項式, {{llang|en|matching polynomial}})이라고 한다. (여기서 <math>m_0=1</math>이다.)

또한, 유한 그래프 <math>\Gamma</math>의 모든 부합의 수, 즉
:<math>Z_\Gamma(1,1)</math>
를 <math>\Gamma</math>의 '''호소야 지표'''([細矢]指標, {{llang|en|Hosoya index}})라고 한다.

만약
:<math>x\mapsto \exp(-\beta E_2)</math>
:<math>y\mapsto \exp(-\beta E_1)</math>
로 치환하였을 때, 이는 [[단량체-이합체 모형]]의 [[분배 함수 (통계역학)|분배 함수]]와 같다.

== 성질 ==
(유한 또는 무한) 그래프 <math>\Gamma</math> 위의 두 부합 <math>M,M'\subseteq\operatorname E(\Gamma)</math>에 대하여, [[그래프]]
:<math>\Gamma'=(M\setminus M')\cup(M'\setminus M)</math>
를 생각하자. 그렇다면, <math>\Gamma'</math>은 다음과 같은 종류의 [[연결 성분]]들로만 구성된다.
* 짝수 길이의 [[순환 그래프]] <math>C_{2n}</math>. 또한, 그 변들은 번갈아 가며 <math>M</math>에 속하거나 <math>M'</math>에 속하게 된다.
* 유한한 길이의 [[경로 그래프]] <math>P_k</math>. 또한, 그 변들은 번갈아 가며 <math>M</math>에 속하거나 <math>M'</math>에 속하게 된다.
* 한 쪽의 끝을 갖는 무한 [[경로 그래프]] <math>P_\infty^+</math>. 또한, 그 변들은 번갈아 가며 <math>M</math>에 속하거나 <math>M'</math>에 속하게 된다.
* 끝점을 갖지 않는 무한 [[경로 그래프]] <math>P_\infty^\pm</math>. 또한, 그 변들은 번갈아 가며 <math>M</math>에 속하거나 <math>M'</math>에 속하게 된다.
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
<math>\Gamma'</math>의 각 꼭짓점은 2개 또는 1개의 변에 인접하며, 2개의 변에 인접할 경우 그 가운데 하나는 <math>M</math>에 속하며, 다른 하나는 <math>M'</math>에 속하게 된다. 이 조건을 만족시키는 연결 그래프는 위의 네 족 밖에 없다.
</div></div>

=== 베르주 보조정리 ===
[[파일:Edmonds augmenting path.svg|섬네일|오른쪽|왼쪽의 부합은 덧붙임 경로(붉은 색으로 표시)를 갖는다. 이를 사용하여, 오른쪽의 더 큰 부합을 만들 수 있다.]]
임의의 [[유한 그래프]] <Math>\Gamma</math> 속의 부합 <math>M\subseteq\operatorname E(\Gamma)</math>의 '''덧붙임 경로'''({{llang|en|augmenting path}})는 다음 조건을 만족시키는 [[경로 (그래프 이론)|경로]] <Math>(v_0,v_1,v_2,\dotsc,v_{2n+1})</math>이다.
* 시작 꼭짓점 <math>v_0</math> 및 끝 꼭짓점 <math>v_{2n+1}</math>은 <math>M</math>에 속한 변과 인접하지 않는다.
* 경로의 변들은 <math>M</math>에 속한 것과 속하지 않은 것들이 교대된다. 즉, 모든 <math>i</math>에 대하여, <math>(v_{2i},v_{2i+1})\not\in M</math>이지만, <math>(v_{2i+1},v_{2i+2})\in M</math>이다.

'''베르주 정리'''({{llang|en|Berge’s lemma}})에 따르면, 임의의 [[유한 그래프]] <math>\Gamma</math> 속의 부합 <math>M\subseteq\operatorname E(\Gamma)</math>에 대하여 다음 두 조건이 서로 [[동치]]이다.
* 최대 부합이다.
* 덧붙임 경로를 갖지 않는다.
(다시 말해, 덧붙임 경로를 갖는 부합에는 덧붙임 경로를 “덧붙여서” 더 큰 부합을 만들 수 있다.)
<div class="mw-collapsible mw-collapsed toccolours">
'''증명 (덧붙임 경로의 존재 ⇒ 최대 부합이 아님):'''
<div class="mw-collapsible-content">
[[유한 그래프]] <math>\Gamma</math>와 그 속의 부합 <math>M\subseteq\operatorname E(\Gamma)</math> 및 그 덧붙임 경로 <math>P</math>가 주어졌다고 하자. 그렇다면, <math>M'=(M\setminus P)\cup(P\setminus M)</math>은 부합을 이루며, <math>|M'|=|M|+1</math>이다.
</div></div>
<div class="mw-collapsible mw-collapsed toccolours">
'''증명 (최대 부합이 아님 ⇒ 덧붙임 경로의 존재):'''
<div class="mw-collapsible-content">
[[유한 그래프]] <math>\Gamma</math> 위의 두 부합 <math>M</math>, <math>M'</math>이 주어졌다고 하고, <math>|M|<|M'|</math>이라고 하자. 그렇다면, 그래프
:<math>\Gamma'=(M\setminus M')\cup(M'\setminus M)</math>
를 생각하자. 이는 두 부합의 [[대칭차]]이므로, [[경로 그래프]] 및 짝수 길이 [[순환 그래프]]로 구성된다. <math>|M|<|M'|</math>이므로, <math>\Gamma'</math>은 처음 및 끝 변이 <math>M'</math>에 속하는 홀수 길이의 경로 그래프 <math>P</math>를 포함한다. <math>P</math>는 <math>M</math>의 덧붙임 경로를 이룬다.
</div></div>

=== 텃-베르주 공식 ===
'''텃-베르주 공식'''(Tutte-Berge公式, {{llang|en|Tutte–Berge formula}})에 따르면, [[유한 그래프]] <Math>\Gamma</math>의 최대 부합의 [[집합의 크기|크기]]는 다음과 같다.
:<math>\frac12\min_{U\subseteq\operatorname V(\Gamma)}\left(\operatorname V(\Gamma)+|U|-\operatorname{odd}(\Gamma\setminus U)\right)</math>
여기서
* <math>\operatorname V(\Gamma)</math>는 <math>\Gamma</math>의 모든 꼭짓점들의 집합이다.
* <math>\textstyle\min_{U\subseteq\operatorname V(\Gamma)}</math>는 <math>\Gamma</math>의 모든 가능한 꼭짓점 집합에 대하여 취한 최솟값이다.
* <math>\Gamma\setminus U</math>는 <math>\Gamma</math>에서 <math>U\subseteq\operatorname V(\Gamma)</math>에 속한 꼭짓점 및 <math>U</math>와 인접하는 변들을 제거하여 얻는, <math>\Gamma</math>의 부분 그래프이다.
* <math>\operatorname{odd}(-)</math>는 어떤 그래프의 [[연결 성분]] 가운데, 홀수 개의 꼭짓점들을 갖는 [[연결 성분]]의 수이다.

특히, 만약 어떤 [[유한 그래프]] <math>\Gamma</math>가 완벽 부합을 갖는 경우
:<math>\frac12|\operatorname V(\Gamma)|=\frac12\min_{U\subseteq\operatorname V(\Gamma)}\left(\operatorname V(\Gamma)+|U|-\operatorname{odd}(\Gamma\setminus U)\right)</math>
이므로, 임의의 <math>U\subseteq\operatorname V(\Gamma)</math>에 대하여
:<math>|U|\ge\operatorname{odd}(\Gamma\setminus U)</math>
이다. 이를 '''텃 정리'''({{llang|en|Tutte’s theorem}})라고 한다.

=== 알고리즘 ===
임의의 그래프의 호소야 지표를 계산하는 것은 [[샤프-P-완전]] 문제이므로, 매우 어렵다.<ref>{{저널 인용|이름=Leslie|성=Valiant|날짜=1979|제목=The complexity of enumeration and reliability problems|저널=Society for Industrial and Applied Mathematics Journal on Computing|권=8|호=3|쪽=410–421|doi=10.1137/0208032|언어=en}}</ref> 다만, [[평면 그래프]]의 경우, [[파프 방향]]을 사용하여
[[P (복잡도)|P]] 알고리즘이 가능하다.

== 예 ==
[[파일:K4_matchings.svg|섬네일|오른쪽|[[완전 그래프]] <Math>K_4</math>의 모든 부합. 이는 10개의 부합을 가지므로, 그 호소야 지표는 10이며, 그 부합 다항식은 <math>y^4+6xy^2+3x^2</math>이다.]]
[[완전 그래프]] <math>K_n</math>의 부합 다항식은 다음과 같이 [[에르미트 다항식]] <math>\operatorname H_n</math>으로 주어진다.<ref name="Godsil">{{저널 인용|제목=Hermite polynomials and a duality relation for matchings polynomials|이름=Christopher David|성=Godsil|저널=Combinatorica|doi=10.1007/BF02579331|날짜=1981|권=1|호=3|쪽=257–262|언어=en}}</ref>{{rp|258, §1}}
:<math>Z_{K_n}(-1,y)=\operatorname H_n(y)</math>
여기서
:<math>\operatorname H_n(x)=\left(x-\frac{\mathrm d}{\mathrm dx}\right)^n1</math>
이다.

마찬가지로, [[완전 이분 그래프]] <math>K_{m,n}</math>의 부합 다항식은 다음과 같은 (일반화) [[라게르 다항식]]으로 주어진다.<ref name="Godsil"/>{{rp|261, §3}}
:<math>Z_{K_{m,n}}(-1,y) = n! \operatorname L_n^{(m-n)}(y^2)</math>

== 역사 ==
텃 정리는 [[윌리엄 토머스 텃]]이 1947년에 증명하였다.<ref>{{저널 인용|제목=The factorization of linear graphs|이름=William Thomas|성=Tutte|저자링크=윌리엄 토머스 텃|doi=10.1112/jlms/s1-22.2.107|날짜=1947-04|저널=Journal of the London Mathematical Society|권=22|호=2|쪽=107–111|zbl=0029.23301|언어=en}}</ref> 이후 1958년에 클로드 자크 베르주가 이를 텃-베르주 공식으로 일반화하였다.<ref>{{저널 인용|first=Claude Jacques|last=Berge|title=Sur le couplage maximum d’un graphe|journal=Comptes rendus hebdomadaires des séances de l’Académie des sciences|volume=247|year=1958|pages=258–259|언어=fr}}</ref>

베르주 정리는 1957년에 프랑스의 수학자 클로드 자크 베르주({{llang|fr|Claude Jacques Berge}}, 1926~2002)가 증명하였다.<ref>{{저널 인용
 | first = Claude Jacques
 | last = Berge
 | journal = Proceedings of the National Academy of Sciences of the United States of America
 | pages = 842–844
 | title = Two theorems in graph theory
 | volume = 43
 | issue = 9
 | date = 1957-09-15
 | doi=10.1073/pnas.43.9.842
 | pmc=534337
 | pmid=16590096
 | jstor=89875
 | 언어=en}}</ref>

호소야 지표는 일본의 화학자 호소야 하루오({{llang|ja|細矢 治夫}}, 1936~)가 1971년에 [[유기화학]]에서의 응용을 위하여 도입하였다.<ref>{{저널 인용
 | last=Hosoya | first=Haruo
 | title=Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons
 | journal=Bulletin of the Chemical Society of Japan
 | volume=44
 | issue=9
 | year=1971
 | pages=2332–2339
 | doi=10.1246/bcsj.44.2332
 | 언어=en
}}</ref>

== 같이 보기 ==
* [[변 색칠]]
== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=One-factor}}
* {{eom|title=One-factorization}}
* {{eom|title=Matching polynomial of a graph}}
* {{매스월드|id=Matching|title=Matching}}
* {{매스월드|id=MaximalIndependentEdgeSet|title=Maximal independent edge set}}
* {{매스월드|id=MaximumIndependentEdgeSet|title=Maximum independent edge set}}
* {{매스월드|id=PerfectMatching|title=Perfect matching}}
* {{매스월드|id=Near-PerfectMatching|title=Near-perfect matching}}
* {{매스월드|id=MatchingNumber|title=Matching number}}
* {{매스월드|id=MatchingPolynomial|title=Matching polynomial}}
* {{매스월드|id=Matching-GeneratingPolynomial|title=Matching-generating polynomial}}
* {{매스월드|id=TuttesTheorem|title=Tutte’s theorem}}

{{전거 통제}}

[[분류:그래프 이론의 계산 문제]]
[[분류:조합 최적화]]