부합 (그래프 이론)

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

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

그래프 이론에서 부합(附合, 틀:Llang)은 서로 만나지 않는 변들의 집합이다.

정의

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

• 임의의 $e_1,e_2\in M$에 대하여, $e_1$과 $e_2$가 하나 이상의 꼭짓점을 공유한다면 $e_1=e_2$이다.

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

완벽 부합

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

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

부합 다항식

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

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

를 $\mathrm{\Gamma }$의 부합 다항식(附合多項式, 틀:Llang)이라고 한다. (여기서 $m_0=1$이다.)

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

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

를 $\mathrm{\Gamma }$의 호소야 지표([細矢]指標, 틀:Llang)라고 한다.

만약

$x\mapsto \exp (-\beta E_2)$

$y\mapsto \exp (-\beta E_1)$

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

성질

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

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

를 생각하자. 그렇다면, ${\mathrm{\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 }$에 속하게 된다.

증명:

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

베르주 보조정리

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

임의의 유한 그래프 $\mathrm{\Gamma }$ 속의 부합 $M\subseteq \mathrm{E}(\mathrm{\Gamma })$의 덧붙임 경로(틀:Llang)는 다음 조건을 만족시키는 경로 $(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$이다.

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

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

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

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

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

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

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

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

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

텃-베르주 공식

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

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

여기서

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

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

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

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

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

이다. 이를 텃 정리(틀:Llang)라고 한다.

알고리즘

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

예

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

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

$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}$의 부합 다항식은 다음과 같은 (일반화) 라게르 다항식으로 주어진다.틀:Rp

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

역사

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

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

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

같이 보기

• 변 색칠

외부 링크

• 틀:Eom
• 틀:Eom
• 틀:Eom
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드
• 틀:매스월드