부합 (그래프 이론)

그래프 이론에서 부합(附合, 영어: matching 매칭^[*])은 서로 만나지 않는 변들의 집합이다.^[1][2]

그래프 ${\displaystyle \Gamma }$의 부합 ${\displaystyle M\subseteq E(\Gamma )}$은 다음을 만족시키는, 변들의 부분 집합이다.

• 임의의 ${\displaystyle e_{1},e_{2}\in M}$에 대하여, ${\displaystyle e_{1}}$과 ${\displaystyle e_{2}}$가 하나 이상의 꼭짓점을 공유한다면 ${\displaystyle e_{1}=e_{2}}$이다.

${\displaystyle \Gamma }$의 부합들은 포함 관계에 따라서 부분 순서 집합을 이룬다. 이 부분 순서에 대하여 극대인 부합을 극대 부합(영어: maximal matching)이라고 한다. 최대 부합(영어: maximum matching)은 극대 부합 가운데, 변의 수가 최대인 부합이다.

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

• 
  완벽 부합의 예
• 
  페테르센 그래프 속에서, 붉게 칠해진 변들은 완벽 부합을 이룬다. 보다 일반적으로, 모든 일반화 페테르센 그래프는 마찬가지로 완벽 부합을 갖는다.
• 
  데자르그 그래프 속에서, 붉은 색 · 푸른 색 · 녹색 변들은 각각 완벽 부합을 이룬다.

유한 그래프 ${\displaystyle \Gamma }$가 주어졌으며, 그 가운데 크기(즉, 포함된 변의 수)가 ${\displaystyle n}$인 부합의 수를 ${\displaystyle m_{n}}$이라고 하자. 그렇다면, 그 생성 함수

${\displaystyle Z_{\Gamma }(x,y)=\sum _{n=0}^{\infty }m_{n}x^{n}y^{|\operatorname {V} (\Gamma )|-2n}\in \mathbb {Z} [x,y]}$

를 ${\displaystyle \Gamma }$의 부합 다항식(附合多項式, 영어: matching polynomial)이라고 한다. (여기서 ${\displaystyle m_{0}=1}$이다.)

또한, 유한 그래프 ${\displaystyle \Gamma }$의 모든 부합의 수, 즉

${\displaystyle Z_{\Gamma }(1,1)}$

를 ${\displaystyle \Gamma }$의 호소야 지표([細矢]指標, 영어: Hosoya index)라고 한다.

만약

${\displaystyle x\mapsto \exp(-\beta E_{2})}$

${\displaystyle y\mapsto \exp(-\beta E_{1})}$

로 치환하였을 때, 이는 단량체-이합체 모형의 분배 함수와 같다.

(유한 또는 무한) 그래프 ${\displaystyle \Gamma }$ 위의 두 부합 ${\displaystyle M,M'\subseteq \operatorname {E} (\Gamma )}$에 대하여, 그래프

${\displaystyle \Gamma '=(M\setminus M')\cup (M'\setminus M)}$

를 생각하자. 그렇다면, ${\displaystyle \Gamma '}$은 다음과 같은 종류의 연결 성분들로만 구성된다.

• 짝수 길이의 순환 그래프 ${\displaystyle C_{2n}}$. 또한, 그 변들은 번갈아 가며 ${\displaystyle M}$에 속하거나 ${\displaystyle M'}$에 속하게 된다.
• 유한한 길이의 경로 그래프 ${\displaystyle P_{k}}$. 또한, 그 변들은 번갈아 가며 ${\displaystyle M}$에 속하거나 ${\displaystyle M'}$에 속하게 된다.
• 한 쪽의 끝을 갖는 무한 경로 그래프 ${\displaystyle P_{\infty }^{+}}$. 또한, 그 변들은 번갈아 가며 ${\displaystyle M}$에 속하거나 ${\displaystyle M'}$에 속하게 된다.
• 끝점을 갖지 않는 무한 경로 그래프 ${\displaystyle P_{\infty }^{\pm }}$. 또한, 그 변들은 번갈아 가며 ${\displaystyle M}$에 속하거나 ${\displaystyle M'}$에 속하게 된다.

임의의 유한 그래프 ${\displaystyle \Gamma }$ 속의 부합 ${\displaystyle M\subseteq \operatorname {E} (\Gamma )}$의 덧붙임 경로(영어: augmenting path)는 다음 조건을 만족시키는 경로 ${\displaystyle (v_{0},v_{1},v_{2},\dotsc ,v_{2n+1})}$이다.

• 시작 꼭짓점 ${\displaystyle v_{0}}$ 및 끝 꼭짓점 ${\displaystyle v_{2n+1}}$은 ${\displaystyle M}$에 속한 변과 인접하지 않는다.
• 경로의 변들은 ${\displaystyle M}$에 속한 것과 속하지 않은 것들이 교대된다. 즉, 모든 ${\displaystyle i}$에 대하여, ${\displaystyle (v_{2i},v_{2i+1})\not \in M}$이지만, ${\displaystyle (v_{2i+1},v_{2i+2})\in M}$이다.

베르주 정리(영어: Berge’s lemma)에 따르면, 임의의 유한 그래프 ${\displaystyle \Gamma }$ 속의 부합 ${\displaystyle M\subseteq \operatorname {E} (\Gamma )}$에 대하여 다음 두 조건이 서로 동치이다.

• 최대 부합이다.
• 덧붙임 경로를 갖지 않는다.

(다시 말해, 덧붙임 경로를 갖는 부합에는 덧붙임 경로를 “덧붙여서” 더 큰 부합을 만들 수 있다.)

텃-베르주 공식(Tutte-Berge公式, 영어: Tutte–Berge formula)에 따르면, 유한 그래프 ${\displaystyle \Gamma }$의 최대 부합의 크기는 다음과 같다.

${\displaystyle {\frac {1}{2}}\min _{U\subseteq \operatorname {V} (\Gamma )}\left(\operatorname {V} (\Gamma )+|U|-\operatorname {odd} (\Gamma \setminus U)\right)}$

여기서

• ${\displaystyle \operatorname {V} (\Gamma )}$는 ${\displaystyle \Gamma }$의 모든 꼭짓점들의 집합이다.
• ${\displaystyle \textstyle \min _{U\subseteq \operatorname {V} (\Gamma )}}$는 ${\displaystyle \Gamma }$의 모든 가능한 꼭짓점 집합에 대하여 취한 최솟값이다.
• ${\displaystyle \Gamma \setminus U}$는 ${\displaystyle \Gamma }$에서 ${\displaystyle U\subseteq \operatorname {V} (\Gamma )}$에 속한 꼭짓점 및 ${\displaystyle U}$와 인접하는 변들을 제거하여 얻는, ${\displaystyle \Gamma }$의 부분 그래프이다.
• ${\displaystyle \operatorname {odd} (-)}$는 어떤 그래프의 연결 성분 가운데, 홀수 개의 꼭짓점들을 갖는 연결 성분의 수이다.

특히, 만약 어떤 유한 그래프 ${\displaystyle \Gamma }$가 완벽 부합을 갖는 경우

${\displaystyle {\frac {1}{2}}|\operatorname {V} (\Gamma )|={\frac {1}{2}}\min _{U\subseteq \operatorname {V} (\Gamma )}\left(\operatorname {V} (\Gamma )+|U|-\operatorname {odd} (\Gamma \setminus U)\right)}$

이므로, 임의의 ${\displaystyle U\subseteq \operatorname {V} (\Gamma )}$에 대하여

${\displaystyle |U|\geq \operatorname {odd} (\Gamma \setminus U)}$

이다. 이를 텃 정리(영어: Tutte’s theorem)라고 한다.

임의의 그래프의 호소야 지표를 계산하는 것은 샤프-P-완전 문제이므로, 매우 어렵다.^[3] 다만, 평면 그래프의 경우, 파프 방향을 사용하여 P 알고리즘이 가능하다.

완전 그래프 ${\displaystyle K_{n}}$의 부합 다항식은 다음과 같이 에르미트 다항식 ${\displaystyle \operatorname {H} _{n}}$으로 주어진다.^{[4]:258, §1}

${\displaystyle Z_{K_{n}}(-1,y)=\operatorname {H} _{n}(y)}$

여기서

${\displaystyle \operatorname {H} _{n}(x)=\left(x-{\frac {\mathrm {d} }{\mathrm {d} x}}\right)^{n}1}$

이다.

마찬가지로, 완전 이분 그래프 ${\displaystyle K_{m,n}}$의 부합 다항식은 다음과 같은 (일반화) 라게르 다항식으로 주어진다.^{[4]:261, §3}

${\displaystyle Z_{K_{m,n}}(-1,y)=n!\operatorname {L} _{n}^{(m-n)}(y^{2})}$

텃 정리는 윌리엄 토머스 텃이 1947년에 증명하였다.^[5] 이후 1958년에 클로드 자크 베르주가 이를 텃-베르주 공식으로 일반화하였다.^[6]

베르주 정리는 1957년에 프랑스의 수학자 클로드 자크 베르주(프랑스어: Claude Jacques Berge, 1926~2002)가 증명하였다.^[7]

호소야 지표는 일본의 화학자 호소야 하루오(일본어: 細矢 治夫, 1936~)가 1971년에 유기화학에서의 응용을 위하여 도입하였다.^[8]

• 변 색칠

• “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. 
• “Matching polynomial of a graph”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Matching”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Maximal independent edge set”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Maximum independent edge set”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Perfect matching”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Near-perfect matching”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Matching number”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Matching polynomial”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Matching-generating polynomial”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Tutte’s theorem”. 《Wolfram MathWorld》 (영어). Wolfram Research.