부합 (그래프 이론)

최대 부합이 아닌 극대 부합의 예. 부합에 포함된 변들을 붉은 색으로 굵게 표시하였다. 최대 부합의 예. 부합에 포함된 변들을 붉은 색으로 굵게 표시하였다. 이 가운데 (왼쪽부터) 둘째는 완벽 부합이지만, 첫째와 셋째는 완벽 부합이 아닌 최대 부합이다. 그래프 이론에서 **부합**(附合, 매칭)은 서로 만나지 않는 변들의 집합이다.언어=en언어=en
# 정의
그래프 \Gamma의 **부합** M\subseteq E(\Gamma)은 다음을 만족시키는, 변들의 부분 집합이다. * 임의의 e_1,e_2\in M에 대하여, e_1과 e_2가 하나 이상의 꼭짓점을 공유한다면 e_1=e_2이다. \Gamma의 부합들은 포함 관계에 따라서 부분 순서 집합을 이룬다. 이 부분 순서에 대하여 극대인 부합을 **극대 부합**(maximal matching)이라고 한다. **최대 부합**(maximum matching)은 극대 부합 가운데, 변의 수가 최대인 부합이다.
## 완벽 부합
**완벽 부합**(完璧附合, perfect matching)은 모든 꼭짓점을 덮는 부합이다. 따라서 완벽 부합은 꼭짓점이 짝수 개인 경우에만 존재할 수 있다. 완벽 부합은 당연히 최대 부합이다. 부합의 예 그래프 속에서, 붉게 칠해진 변들은 완벽 부합을 이룬다. 보다 일반적으로, 모든 일반화 페테르센 그래프는 마찬가지로 완벽 부합을 갖는다. 그래프 속에서, 붉은 색 · 푸른 색 · 녹색 변들은 각각 완벽 부합을 이룬다.
## 부합 다항식
유한 그래프 \Gamma가 주어졌으며, 그 가운데 크기(즉, 포함된 변의 수)가 n인 부합의 수를 m_n이라고 하자. 그렇다면, 그 생성 함수 :Z_\Gamma(x,y)=\sum_{n=0}^\infty m_nx^ny^{|\operatorname V(\Gamma)|-2n}\in\mathbb Z[x,y] 를 \Gamma의 **부합 다항식**(附合多項式, matching polynomial)이라고 한다. (여기서 m_0=1이다.) 또한, 유한 그래프 \Gamma의 모든 부합의 수, 즉 :Z_\Gamma(1,1) 를 \Gamma의 **호소야 지표**([細矢]指標, Hosoya index)라고 한다. 만약 :x\mapsto \exp(-\beta E_2) :y\mapsto \exp(-\beta E_1) 로 치환하였을 때, 이는 단량체-이합체 모형의 분배 함수와 같다.
# 성질
(유한 또는 무한) 그래프 \Gamma 위의 두 부합 M,M'\subseteq\operatorname E(\Gamma)에 대하여, 그래프 :\Gamma'=(M\setminus M')\cup(M'\setminus M) 를 생각하자. 그렇다면, \Gamma'은 다음과 같은 종류의 연결 성분들로만 구성된다. * 짝수 길이의 순환 그래프 C_{2n}. 또한, 그 변들은 번갈아 가며 M에 속하거나 M'에 속하게 된다. * 유한한 길이의 경로 그래프 P_k. 또한, 그 변들은 번갈아 가며 M에 속하거나 M'에 속하게 된다. * 한 쪽의 끝을 갖는 무한 경로 그래프 P_\infty^+. 또한, 그 변들은 번갈아 가며 M에 속하거나 M'에 속하게 된다. * 끝점을 갖지 않는 무한 경로 그래프 P_\infty^\pm. 또한, 그 변들은 번갈아 가며 M에 속하거나 M'에 속하게 된다.

**증명:**

\Gamma'의 각 꼭짓점은 2개 또는 1개의 변에 인접하며, 2개의 변에 인접할 경우 그 가운데 하나는 M에 속하며, 다른 하나는 M'에 속하게 된다. 이 조건을 만족시키는 연결 그래프는 위의 네 족 밖에 없다.

## 베르주 보조정리
왼쪽의 부합은 덧붙임 경로(붉은 색으로 표시)를 갖는다. 이를 사용하여, 오른쪽의 더 큰 부합을 만들 수 있다. 임의의 유한 그래프 \Gamma 속의 부합 M\subseteq\operatorname E(\Gamma)의 **덧붙임 경로**(augmenting path)는 다음 조건을 만족시키는 경로 (v_0,v_1,v_2,\dotsc,v_{2n+1})이다. * 시작 꼭짓점 v_0 및 끝 꼭짓점 v_{2n+1}은 M에 속한 변과 인접하지 않는다. * 경로의 변들은 M에 속한 것과 속하지 않은 것들이 교대된다. 즉, 모든 i에 대하여, (v_{2i},v_{2i+1})\not\in M이지만, (v_{2i+1},v_{2i+2})\in M이다. **베르주 정리**(Berge’s lemma)에 따르면, 임의의 유한 그래프 \Gamma 속의 부합 M\subseteq\operatorname E(\Gamma)에 대하여 다음 두 조건이 서로 동치이다. * 최대 부합이다. * 덧붙임 경로를 갖지 않는다. (다시 말해, 덧붙임 경로를 갖는 부합에는 덧붙임 경로를 “덧붙여서” 더 큰 부합을 만들 수 있다.)

**증명 (덧붙임 경로의 존재 ⇒ 최대 부합이 아님):**

유한 그래프 \Gamma와 그 속의 부합 M\subseteq\operatorname E(\Gamma) 및 그 덧붙임 경로 P가 주어졌다고 하자. 그렇다면, M'=(M\setminus P)\cup(P\setminus M)은 부합을 이루며, |M'|=|M|+1이다.

**증명 (최대 부합이 아님 ⇒ 덧붙임 경로의 존재):**

유한 그래프 \Gamma 위의 두 부합 M, M'이 주어졌다고 하고, |M|<|M'|이라고 하자. 그렇다면, 그래프 :\Gamma'=(M\setminus M')\cup(M'\setminus M) 를 생각하자. 이는 두 부합의 대칭차이므로, 경로 그래프 및 짝수 길이 순환 그래프로 구성된다. |M|<|M'|이므로, \Gamma'은 처음 및 끝 변이 M'에 속하는 홀수 길이의 경로 그래프 P를 포함한다. P는 M의 덧붙임 경로를 이룬다.

## 텃-베르주 공식
**텃-베르주 공식**(Tutte-Berge公式, Tutte–Berge formula)에 따르면, 유한 그래프 \Gamma의 최대 부합의 크기는 다음과 같다. :\frac12\min_{U\subseteq\operatorname V(\Gamma)}\left(\operatorname V(\Gamma)+|U|-\operatorname{odd}(\Gamma\setminus U)\right) 여기서 * \operatorname V(\Gamma)는 \Gamma의 모든 꼭짓점들의 집합이다. * \textstyle\min_{U\subseteq\operatorname V(\Gamma)}는 \Gamma의 모든 가능한 꼭짓점 집합에 대하여 취한 최솟값이다. * \Gamma\setminus U는 \Gamma에서 U\subseteq\operatorname V(\Gamma)에 속한 꼭짓점 및 U와 인접하는 변들을 제거하여 얻는, \Gamma의 부분 그래프이다. * \operatorname{odd}(-)는 어떤 그래프의 연결 성분 가운데, 홀수 개의 꼭짓점들을 갖는 연결 성분의 수이다. 특히, 만약 어떤 유한 그래프 \Gamma가 완벽 부합을 갖는 경우 :\frac12|\operatorname V(\Gamma)|=\frac12\min_{U\subseteq\operatorname V(\Gamma)}\left(\operatorname V(\Gamma)+|U|-\operatorname{odd}(\Gamma\setminus U)\right) 이므로, 임의의 U\subseteq\operatorname V(\Gamma)에 대하여 :|U|\ge\operatorname{odd}(\Gamma\setminus U) 이다. 이를 **텃 정리**(Tutte’s theorem)라고 한다.
## 알고리즘
임의의 그래프의 호소야 지표를 계산하는 것은 샤프-P-완전 문제이므로, 매우 어렵다.언어=en 다만, 평면 그래프의 경우, 파프 방향을 사용하여 P 알고리즘이 가능하다.
# 예
완전 그래프 K_4의 모든 부합. 이는 10개의 부합을 가지므로, 그 호소야 지표는 10이며, 그 부합 다항식은 y^4+6xy^2+3x^2이다. 완전 그래프 K_n의 부합 다항식은 다음과 같이 에르미트 다항식 \operatorname H_n으로 주어진다.언어=en258, §1 :Z_{K_n}(-1,y)=\operatorname H_n(y) 여기서 :\operatorname H_n(x)=\left(x-\frac{\mathrm d}{\mathrm dx}\right)^n1 이다. 마찬가지로, 완전 이분 그래프 K_{m,n}의 부합 다항식은 다음과 같은 (일반화) 라게르 다항식으로 주어진다.261, §3 :Z_{K_{m,n(-1,y) = n! \operatorname L_n^{(m-n)}(y^2)
# 역사
텃 정리는 윌리엄 토머스 텃이 1947년에 증명하였다.언어=en 이후 1958년에 클로드 자크 베르주가 이를 텃-베르주 공식으로 일반화하였다.언어=fr 베르주 정리는 1957년에 프랑스의 수학자 클로드 자크 베르주(Claude Jacques Berge, 1926~2002)가 증명하였다.언어=en 호소야 지표는 일본의 화학자 호소야 하루오(細矢 治夫, 1936~)가 1971년에 유기화학에서의 응용을 위하여 도입하였다.언어=en