부합 (그래프 이론)

섬네일을 만드는 중 오류 발생:

최대 부합이 아닌 극대 부합의 예. 부합에 포함된 변들을 붉은 색으로 굵게 표시하였다.

섬네일을 만드는 중 오류 발생:

최대 부합의 예. 부합에 포함된 변들을 붉은 색으로 굵게 표시하였다. 이 가운데 (왼쪽부터) 둘째는 완벽 부합이지만, 첫째와 셋째는 완벽 부합이 아닌 최대 부합이다.

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

정의

그래프 $\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}^{\mathrm{\infty }}{m}_n{x}^n{y}^{|\mathrm{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^{\prime }\subseteq \mathrm{E}(\Gamma )$에 대하여, 그래프

${\Gamma }^{\prime }=(M\setminus M^{\prime })\cup (M^{\prime }\setminus M)$

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

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

증명:

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

베르주 보조정리

파일:Edmonds augmenting path.svg

왼쪽의 부합은 덧붙임 경로(붉은 색으로 표시)를 갖는다. 이를 사용하여, 오른쪽의 더 큰 부합을 만들 수 있다.

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

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

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

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

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

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

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

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

유한 그래프 $\Gamma$ 위의 두 부합 $M$, $M^{\prime }$이 주어졌다고 하고, $|M|<|M^{\prime }|$이라고 하자. 그렇다면, 그래프

${\Gamma }^{\prime }=(M\setminus M^{\prime })\cup (M^{\prime }\setminus M)$

를 생각하자. 이는 두 부합의 대칭차이므로, 경로 그래프 및 짝수 길이 순환 그래프로 구성된다. $|M|<|M^{\prime }|$이므로, ${\Gamma }^{\prime }$은 처음 및 끝 변이 $M^{\prime }$에 속하는 홀수 길이의 경로 그래프 $P$를 포함한다. $P$는 $M$의 덧붙임 경로를 이룬다.

텃-베르주 공식

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

$\frac{1}{2}\underset{U\subseteq \mathrm{V}(\Gamma )}{\min }(\mathrm{V}(\Gamma )+|U|-\mathrm{odd}(\Gamma \setminus U))$

여기서

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

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

$\frac{1}{2}|\mathrm{V}(\Gamma )|=\frac{1}{2}\underset{U\subseteq \mathrm{V}(\Gamma )}{\min }(\mathrm{V}(\Gamma )+|U|-\mathrm{odd}(\Gamma \setminus U))$

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

$|U|\ge \mathrm{odd}(\Gamma \setminus U)$

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

알고리즘

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

예

섬네일을 만드는 중 오류 발생:

완전 그래프 $K_4$의 모든 부합. 이는 10개의 부합을 가지므로, 그 호소야 지표는 10이며, 그 부합 다항식은 $y^4+6x{y}^2+3x^2$이다.

완전 그래프 $K_n$의 부합 다항식은 다음과 같이 에르미트 다항식 ${\mathrm{H}}_n$으로 주어진다.^{:258, §1}

$Z_{K_n}(-1,y)={\mathrm{H}}_n(y)$

여기서

${\mathrm{H}}_n(x)={(x-\frac{\mathrm{d}}{\mathrm{d}x})}^{n}1$

이다.

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

$Z_{K_{m,n}}(-1,y)=n!{\mathrm{L}}_n^{(m-n)}(y^2)$

역사

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

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

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

같이 보기

• 변 색칠

외부 링크

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