부합 (그래프 이론)

3. 성질

그래프 $\backslash Gamma$ 위의 두 부합 $M,M\text{'}\backslash subseteq\backslash operatorname\; E(\backslash Gamma)$에 대하여, 그래프

:$\backslash Gamma\text{'}=(M\backslash setminus\; M\text{'})\backslash cup(M\text{'}\backslash setminus\; M)$

를 생각할 수 있다. 그렇다면, $\backslash Gamma\text{'}$은 다음과 같은 종류의 연결 성분들로만 구성된다.

• 짝수 길이의 순환 그래프 $C\_\{2n\}$. 그 변들은 번갈아 가며 $M$에 속하거나 $M\text{'}$에 속한다.
• 유한한 길이의 경로 그래프 $P\_k$. 그 변들은 번갈아 가며 $M$에 속하거나 $M\text{'}$에 속한다.
• 한 쪽 끝을 갖는 무한 경로 그래프 $P\_\backslash infty^+$. 그 변들은 번갈아 가며 $M$에 속하거나 $M\text{'}$에 속한다.
• 끝점을 갖지 않는 무한 경로 그래프 $P\_\backslash infty^\backslash pm$. 그 변들은 번갈아 가며 $M$에 속하거나 $M\text{'}$에 속한다.

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

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

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

4. 알고리즘

조합 최적화의 기본적인 문제 중 하나는 ''최대 매칭''을 찾는 것이다. 가중치가 없는 이분 그래프에서의 최적화 문제는 최대 기수 매칭을 찾는 것이며, 호프크로프트-카프 알고리즘을 통해 O(V^1/2E) 시간 안에 해결할 수 있다.^[1]

가중치 이분 그래프에서 최적화 문제는 최대 가중치 매칭을 찾는 것이고, 이 문제는 '''할당 문제'''라고도 불린다. 헝가리안 알고리즘은 이 문제를 해결하는 알고리즘 중 하나이다.

극대 매칭은 탐욕 알고리즘으로 찾을 수 있다.

그래프에서 매칭의 수를 계산하는 것은 어려운 문제(#P-완전)이며,^[11] 그래프 내 매칭의 수는 그래프의 호소야 지수라고 알려져 있다. 완전 매칭의 수를 세는 것 역시 어려운데, 이분 그래프에서조차 그러하다.^[12] 카스테레인의 정리에 따르면 평면 그래프에서 완전 매칭의 수는 FKT 알고리즘을 통해 다항 시간 내에 정확하게 계산될 수 있다.

4. 1. 최대 카디널리티 매칭

4. 2. 최대 가중치 매칭

4. 3. 극대 매칭

4. 4. 매칭 수 계산

5. 관련 개념

쾨니그의 정리(그래프 이론)에 따르면, 이분 그래프에서 최대 매칭의 크기는 최소 정점 덮개의 크기와 같다. 이 결과를 통해 최소 정점 덮개, 최대 독립 집합, 최대 정점 이분 그래프 문제를 이분 그래프에 대해 다항 시간 내에 해결할 수 있다.

홀의 결혼 정리는 완전 매칭을 갖는 이분 그래프의 특징을 제공한다.

6. 응용

• '''케쿨레 구조'''는 방향족 화합물의 탄소 골격의 완전 매칭으로 구성되며, 화학 구조에서 이중 결합의 위치를 나타낸다. 이 구조는 프리드리히 아우구스트 케쿨레 폰 슈타도니츠의 이름을 따서 명명되었으며, 그는 벤젠 (그래프 이론 용어로는 6-정점 주기)에 그러한 구조를 부여할 수 있음을 보여주었다.^[20]
• 호소야 지수는 비어 있지 않은 매칭의 수에 1을 더한 값이며, 유기 화합물에 대한 계산 화학 및 수학 화학 연구에 사용된다.
• 중국 우체부 문제는 최소 가중치의 완전 매칭을 하위 문제로 찾는 것을 포함한다.
• 졸업 문제는 졸업에 필요한 최소한의 수업을 선택하는 문제에 관한 것이다.
• 히치콕 수송 문제는 부분 문제로 이분 매칭을 포함한다.
• 부분 트리 동형 문제는 부분 문제로 이분 매칭을 포함한다.
• b-매칭

7. 역사

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

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

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

8. 일반화

b-매칭

참조

_[1] 웹사이트 is_matching https://networkx.org[...] 2022-05-31
_[2] 서적 Algorithmic Graph Theory Cambridge University Press 1985
_[3] 웹사이트 Preview http://diestel-graph[...]
_[4] 간행물 Induced matchings
_[5] 간행물 Über extreme Punkt- und Kantenmengen
_[6] 논문 Spectral characterization of matchings in graphs, Linear Algebra and its Applications 496 (2016) 407–419 https://doi.org/10.1[...]
_[7] 간행물 Fibonacci heaps and their uses in improved network optimization algorithms
_[8] 간행물 Edge dominating sets in graphs http://cgi.di.uoa.gr[...]
_[9] 서적 Computers and Intractability: A Guide to the Theory of NP-Completeness W.H. Freeman
_[10] 서적 Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties Springer
_[11] 간행물 The Complexity of Enumeration and Reliability Problems
_[12] 저널 Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
_[13] 간행물 A combinatorial survey of identities for the double factorial
_[14] 간행물 Extremal problems for topological indices in combinatorial chemistry http://www.math.tugr[...]
_[15] 간행물 Maximum matchings in general graphs through randomization
_[16] 간행물 Randomized $\backslash widetilde\; O(M(|V|))$ algorithms for problems in matching theory
_[17] 간행물 Finding all maximally-matchable edges in a bipartite graph
_[18] conference Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC 1990)
_[19] conference Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing
_[20] 간행물 On some solved and unsolved problems of chemical graph theory
_[21] 서적 Matching theory North-Holland
_[22] 서적 One-factorizations Kluwer
_[23] 저널 The complexity of enumeration and reliability problems
_[24] 저널 Hermite polynomials and a duality relation for matchings polynomials
_[25] 저널 The factorization of linear graphs
_[26] 저널 Sur le couplage maximum d’un graphe
_[27] 저널 Two theorems in graph theory 1957-09-15
_[28] 저널 Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons