부합 (그래프 이론)

위키백과, 우리 모두의 백과사전.
(매칭에서 넘어옴)
이동: 둘러보기, 검색
최대 부합이 아닌 극대 부합의 예. 부합에 포함된 변들을 붉은 색으로 굵게 표시하였다.
최대 부합의 예. 부합에 포함된 변들을 붉은 색으로 굵게 표시하였다. 이 가운데 (왼쪽부터) 둘째 및 셋째는 완벽 부합이지만, 첫째는 완벽 부합이 아닌 최대 부합이다.

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

정의[편집]

그래프 부합 은 다음을 만족시키는, 변들의 부분 집합이다.

  • 임의의 에 대하여, 가 하나 이상의 꼭짓점을 공유한다면 이다.

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

완벽 부합[편집]

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

부합 다항식[편집]

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

부합 다항식(附合多項式, 영어: matching polynomial)이라고 한다. (여기서 이다.)

또한, 유한 그래프 의 모든 부합의 수, 즉

호소야 지표([細矢]指標, 영어: Hosoya index)라고 한다.

만약

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

성질[편집]

(유한 또는 무한) 그래프 위의 두 부합 에 대하여, 그래프

를 생각하자. 그렇다면, 은 다음과 같은 종류의 연결 성분들로만 구성된다.

  • 짝수 길이의 순환 그래프 . 또한, 그 변들은 번갈아 가며 에 속하거나 에 속하게 된다.
  • 유한한 길이의 경로 그래프 . 또한, 그 변들은 번갈아 가며 에 속하거나 에 속하게 된다.
  • 한 쪽의 끝을 갖는 무한 경로 그래프 . 또한, 그 변들은 번갈아 가며 에 속하거나 에 속하게 된다.
  • 끝점을 갖지 않는 무한 경로 그래프 . 또한, 그 변들은 번갈아 가며 에 속하거나 에 속하게 된다.

증명:

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

베르주 보조정리[편집]

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

임의의 유한 그래프 속의 부합 덧붙임 경로(영어: augmenting path)는 다음 조건을 만족시키는 경로 이다.

  • 시작 꼭짓점 및 끝 꼭짓점 에 속한 변과 인접하지 않는다.
  • 경로의 변들은 에 속한 것과 속하지 않은 것들이 교대된다. 즉, 모든 에 대하여, 이지만, 이다.

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

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

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

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

유한 그래프 와 그 속의 부합 및 그 덧붙임 경로 가 주어졌다고 하자. 그렇다면, 은 부합을 이루며, 이다.

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

유한 그래프 위의 두 부합 , 이 주어졌다고 하고, 이라고 하자. 그렇다면, 그래프

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

텃-베르주 공식[편집]

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

여기서

  • 의 모든 꼭짓점들의 집합이다.
  • 의 모든 가능한 꼭짓점 집합에 대하여 취한 최솟값이다.
  • 에서 에 속한 꼭짓점 및 와 인접하는 변들을 제거하여 얻는, 의 부분 그래프이다.
  • 는 어떤 그래프의 연결 성분 가운데, 홀수 개의 꼭짓점들을 갖는 연결 성분의 수이다.

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

이므로, 임의의 에 대하여

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

알고리즘[편집]

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

[편집]

완전 그래프 의 모든 부합. 이는 10개의 부합을 가지므로, 그 호소야 지표는 10이며, 그 부합 다항식은 이다.

완전 그래프 의 부합 다항식은 다음과 같이 에르미트 다항식 으로 주어진다.[4]:258, §1

여기서

이다.

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

역사[편집]

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

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

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

참고 문헌[편집]

  1. László, Lovász; Plummer, Michael David (1986). 《Matching theory》. Annals of Discrete Mathematics (영어) 29. North-Holland. ISBN 0-444-87916-1. doi:10.1016/S0304-0208(08)73633-8. 
  2. Wallis, W. D. (1997). 《One-factorizations》. Mathematics and Its Applications (영어) 390. Kluwer. ISBN 978-0-7923-4323-3. doi:10.1007/978-1-4757-2564-3. 
  3. Valiant, Leslie (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. 
  4. Godsil, Christopher David (1981). “Hermite polynomials and a duality relation for matchings polynomials”. 《Combinatorica》 (영어) 1 (3): 257–262. doi:10.1007/BF02579331. 
  5. Tutte, William Thomas (1947년 4월). “The factorization of linear graphs”. 《Journal of the London Mathematical Society》 (영어) 22 (2): 107–111. Zbl 0029.23301. doi:10.1112/jlms/s1-22.2.107. 
  6. Berge, Claude Jacques (1958). “Sur le couplage maximum d’un graphe”. 《Comptes rendus hebdomadaires des séances de l’Académie des sciences》 (프랑스어) 247: 258–259. 
  7. Berge, Claude Jacques (1957년 9월 15일). “Two theorems in graph theory”. 《Proceedings of the National Academy of Sciences of the United States of America》 (영어) 43 (9): 842–844. JSTOR 89875. PMC 534337. PMID 16590096. doi:10.1073/pnas.43.9.842. 
  8. Hosoya, Haruo (1971). “Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons”. 《Bulletin of the Chemical Society of Japan》 (영어) 44 (9): 2332–2339. doi:10.1246/bcsj.44.2332. 

바깥 고리[편집]