매칭(그래프 이론)

그래프 이론의 수학적 분야에서는 방향성이 없는 그래프에 설정된 일치 또는 독립 에지는 공통 정점이 없는 에지 집합이다. 초당적 그래프에서 일치하는 항목을 찾는 것은 네트워크 흐름 문제로 간주될 수 있다.

덮개/포장-문제 쌍
커버 문제 포장문제 최소 세트 커버 최대세트패킹 최소 에지 커버 최대 일치 최소 꼭지점 커버 최대 독립 집합 빈 커버 빈패킹 폴리곤 피복 직사각형 패킹
v t

정의들

그래프 G = (V, E)의 경우, G의 일치하는 M은 쌍으로 이루어진 비인접 에지 집합이며, 이 중 루프는 하나도 없으며, 즉 두 에지는 공통 정점을 공유하지 않는다.

일치에서 가장자리 중 하나의 끝점인 경우 꼭지점이 일치(또는 포화)된다. 그렇지 않으면 정점이 일치하지 않는다(또는 불포화).

최대 일치는 다른 일치의 하위 집합이 아닌 그래프 G의 일치 M이다. G의 모든 에지가 적어도 하나의 에지와 M의 비 빈 교차점을 갖는 경우 그래프 G의 일치하는 M은 최대값이다. 다음 그림은 3개의 그래프에서 최대 일치(빨간색)의 예를 보여준다.

최대 일치(최대 카디널리티 일치라고도^[1] 함)는 가능한 가장 많은 수의 가장자리를 포함하는 일치 항목이다. 최대 일치 항목이 많을 수 있다. 그래프 G의 일치$$ 번호 $\nu {\displaystyle (G}$) ${\displaystyle \nu(G)}$은(는) 최대 일치 크기입니다. 모든 최대 매칭이 최대 매칭이지만 모든 최대 매칭이 최대 매칭인 것은 아니다. 다음 그림은 동일한 세 개의 그래프에서 최대 일치 항목의 예를 보여준다.

완벽한 매칭은 그래프의 모든 정점과 일치하는 매칭이다. 즉, 그래프의 모든 꼭지점이 일치의 가장자리까지 인시던트인 경우 일치가 완벽하다. 모든 완벽한 매칭은 최대값이며 따라서 최대값이다. 일부 문헌에서는 완전 매칭이라는 용어가 사용된다. 위의 그림에서 부분 (b)만이 완벽한 일치를 보여준다. 완벽한 매칭도 최소 사이즈 엣지 커버다. 따라서 최대 일치의 크기는 최소 에지 커버의 크기보다 크지 않다: ${\displaystyle \nu }$(${\displaystyle G}$ )${\displaystyle \le }$ ( ${\displaystyle G}$) { ( )$$\$displaystyle \nu$(G)\$leq \rho (G)}.$ 그래프는 그래프의 정점 수가 짝수일 때만 완벽한 일치를 포함할 수 있다$.$

거의 완벽한 일치는 정확히 하나의 꼭지점이 일치하지 않는 것이다. 분명히 그래프에는 정점 수가 홀수일 때만 거의 완벽한 일치가 포함될 수 있으며, 거의 완벽한 일치가 최대 일치가 된다. 위의 그림에서 부분(c)은 거의 완벽한 일치를 보여준다. 만약 모든 꼭지점이 거의 완벽에 가까운 어떤 일치에 의해 일치하지 않는다면, 그래프를 인자중요라고 부른다.

일치하는 M이 주어진 교대 경로는 일치하지 않는 정점으로^[2] 시작하는 경로로, 그 에지가 매칭에 번갈아 속하며 매칭에 속하지 않는다. 증강 경로는 자유(일치되지 않은) 정점에서 시작하고 끝나는 교대 경로다. Berge의 보조정리에서는 M에 관한 증강 경로가 없는 경우에만 일치하는 M이 최대라고 한다.

유도 매칭은 유도 서브그래프의 가장자리 집합인 매칭이다.^[3]

특성.

분리된 정점이 없는 그래프에서 일치하는 번호와 가장자리 포함 숫자의 합은 정점의 수와 같다.^[4] 완벽한 일치가 있으면 일치하는 번호와 가장자리 커버 번호가 모두 V / 2가 된다.

A와 B가 두 개의 최대 일치인 경우, A and 2 B와 B . 2 A. 이를 확인하려면 A가 일치하므로 B \ A의 각 가장자리가 A \ B의 최대 두 가장자리에 인접할 수 있음을 관찰하십시오. 더욱이 A \ B의 각 가장자리는 B의 최대값에 의해 B \ A의 가장자리에 인접해 있으므로,

$\displaystyle A\setminus B \leq 2B\setminus A.}$

더 나아가서 우리는 그것을 추론한다.

${\displaystyle A = A\cap B + A\setminus B \leq 2B\cap A +2B\setminus A =2B .}$

특히, 이것은 모든 최대 일치가 최대 일치의 2 근사치이며 또한 최소 최대 일치의 2 근사치임을 보여준다. 예를 들어 G가 3개의 가장자리와 4개의 정점을 가진 경로라면 최소 최대 일치의 크기는 1이고 최대 일치의 크기는 2이다.

그래프의 일치하는 숫자에 대한 스펙트럼 특성화는 하사니 몬프레드와 말리크가 다음과 같이 부여한다. n{n\displaystyle}vertices에 G{G\displaystyle}를 그래프와 1>λ, λ 2>…>λ k>0{\displaystyle \lambda_{1}>, \lambda _{2}>, \ldots입니다.;\lambda _{k}>, 2k≤ n{2k\leq n\displaystyle}0}일 경우 k{k\displaystyle} 뚜렷한 영이 아닌 순수한 허수는. 그 다음자.수 일치${\displaystyle G}$ is ${\displaystyle k}$ if and only if (a) there is a real skew-symmetric matrix ${\displaystyle A}$ with graph ${\displaystyle G}$ and eigenvalues ${\displaystyle \pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{k}}$ and ${\displaystyl$$e n-2k}$ 0$$ 및 (b) 그래프 $G{\displaystyle }$ ${\displaystyle G}$이(가) 있는 모든 실제 스큐 대칭 행렬은 최대 ${\displaystyle \mathrm{2k}}$ ${\displaystyle 2k}$의 비영원$$ 고유값을 갖는다$$.^[5] $n{\displaystyle }$ 순서 n ${\displaystyle n}$의 $실제{\displaystyle }$ 대칭 또는 스큐 대칭 행렬 A ${\displaystyle A}$에 대한 (단순) 그래프에는 $A{\displaystyle }$ ${\displaystyle A}$의 비대각 입력이 제공하는 $n{\displaystyle }$ ${\displaystyle n}$ 정점과$$ 가장자리가 있다는$$ 점에 유의하십시오$.$

일치하는 다항식

그래프에서 k-edge 일치 항목 수의 생성 함수를 일치하는 다항식이라고 한다. G를 그래프로 하고 m을_k k-edge 일치의 수로 하자. G의 일치하는 다항식 중 하나는

${\displaystyle \sum _{k\geq 0}m_{k}x^{k}.}$

다른 정의는 일치하는 다항식을 다음과 같이 지정한다.

${\displaystyle \sum _{k\geq 0}(1)^{k}m_{k}x^{n-2k}}}$

여기서 n은 그래프의 정점 수입니다. 각 유형은 용도가 있다. 자세한 내용은 일치하는 다항식 항목을 참조하십시오.

알고리즘 및 계산 복잡성

최대 카디널리티 일치

조합 최적화의 근본적인 문제는 최대 일치를 찾는 것이다. 이 문제는 다른 등급의 그래프에 대한 다양한 알고리즘을 가지고 있다.

가중치가 없는 초당적 그래프에서 최적화 문제는 최대 카디널리티 일치를 찾는 것이다. 문제는 홉크로프트-카프 알고리즘에 의해 시간(시간)VE 내에 해결되며, 본문에서 설명한 바와 같이 초당적 평면 그래프와 같은 특수 등급의 그래프를 위한 보다 효율적인 무작위화 알고리즘, 근사 알고리즘, 알고리즘이 있다.

최대 가중치 일치

가중치 있는 초당적 그래프에서 최적화 문제는 최대 가중치 일치를 찾는 것이고, 이중 문제는 최소 가중치 일치를 찾는 것이다. 이 문제를 종종 최대 가중 초당적 일치 또는 할당 문제라고 부른다. 헝가리 알고리즘은 할당 문제를 해결하며 결합 최적화 알고리즘의 시작점 중 하나였다. 증가 경로 알고리즘에서 수정된 최단 경로 검색을 사용한다. If the Bellman–Ford algorithm is used for this step, the running time of the Hungarian algorithm becomes ${\displaystyle O(V^{2}E)}$, or the edge cost can be shifted with a potential to achieve ${\displaystyle O(V^{2}\log {V}+VE)}$ running time with the Dijkstra algorithm and Fibonacci heap.^[6]

비-비-비-비-바타이트 가중 그래프에서 최대 중량 일치 문제는 에드몬드의 블라썸 알고리즘을 사용하여$$ 시간 O$){\displaystyle O(V^{2}E)}$에서 해결할 수 있다.

최대 매치

최대 매칭은 단순한 탐욕 알고리즘으로 찾을 수 있다. 최대 일치는 최대 일치가므로 다항 시간 내에 최대 일치를 찾을 수 있다. 그러나 최소 최대 일치, 즉 가능한 가장 작은 수의 가장자리를 포함하는 최대 일치를 찾는 다항식 시간 알고리즘은 알려져 있지 않다.

k 에지와 최대 매칭은 k 에지가 있는 에지 지배 세트다. 반대로 우리에게 k 에지와 함께 최소 에지 지배 세트가 주어진다면 다항식 시간에 k 에지와 최대 일치를 구성할 수 있다. 따라서 최소 최대 일치점을 찾는 문제는 기본적으로 최소 에지 지배 집합을 찾는 문제와 동일하다.^[7] 이 두 최적화 문제 모두 NP-hard인 것으로 알려져 있다. 이러한 문제의 의사결정 버전은 NP-완전 문제의 고전적인 예들이다.^[8] 두 문제 모두 다항식 시간에서 요인 2 내에서 근사치를 구할 수 있다. 즉, 임의의 최대 일치 M을 찾기만 하면 된다.^[9]

카운팅 문제

그래프의 성냥개수는 그래프의 호소야 지수라고 한다. 이 수량을 계산하는 것은 초당적 그래프에 대해서도 #P-완전하다.^[10] 임의의 0–1 매트릭스(또 다른 #P-완전한 문제)의 영구적인 계산은 주어진 매트릭스를 생체역량 매트릭스로 갖는 양분 그래프에서 완벽한 매칭의 수를 계산하는 것과 같기 때문에, 양분 그래프에서도 완벽한 매칭 수를 계산하는 것도 #P-완전하다. 단, 초당적 일치 항목 수를 계산하기 위한 완전 다항식 시간 랜덤화 근사치가 있다.^[11] Kastelyn의 주목할 만한 정리는 평면 그래프의 완벽한 일치의 수는 FKT 알고리즘을 통해 다항 시간 내에 정확하게 계산할 수 있다고 말한다.

완전한 그래프 K_n( 짝수 n)의 완벽한 일치 횟수는 이중 요인(n - 1)!!에 의해 주어진다.^[12] 완전한 그래프의 일치 항목 수는 일치 항목이 완벽하도록 구속하지 않고 전화 번호로 주어진다.^[13]

최대 일치 가능한 모든 가장자리 찾기

일치 이론의 기본적인 문제 중 하나는 그래프에서 최대 일치까지 확장될 수 있는 모든 가장자리를 찾는 것이다(그런 가장자리를 최대 일치 가능한 가장자리 또는 허용되는 가장자리라고 한다). 이 문제의 알고리즘에는 다음이 포함된다.

• 일반 그래프의 경우 시간 $O{\displaystyle (V}$ ${\displaystyle E)}$ ${\displaystyle O(VE)}$의 결정론적 알고리즘과$$ $시간{\displaystyle \stackrel{}{}}$ O${\displaystyle \stackrel{}{}}$~ (${\displaystyle }$V ${\displaystyle {2.376}^{}}$) ${\displaystyle {O}(V^{2.376})$의 임의화된 알고리즘$.$^[14][15]
• 초당적 그래프의 경우 단일 최대 일치가 발견되면 결정론적 알고리즘이 시간 $O{\displaystyle (V}$+ ${\displaystyle E}$) ${\displaystyle O(V+E)}$에 실행된다$.$^[16]

온라인 양당 일치

매칭을 위한 온라인 알고리즘 개발 문제는 1990년 리처드 M. 카프, 우메쉬 바지라니, 비제이 바지라니에 의해 처음 고려되었다.^[17]

온라인 설정에서, 초당적 그래프의 한 쪽에 있는 노드는 한 번에 하나씩 도착하며, 그래프의 다른 쪽과 즉시 일치시키거나 폐기해야 한다. 이는 비서 문제를 자연스럽게 일반화한 것으로 온라인 광고 경매에 응모할 수 있다. 무작위 도착 모델을 사용한 가중치 없는 최대화 사례에 대한 최고의 온라인 알고리즘은 0.696의 경쟁률을 달성한다.^[18]

특성화

Kőnig의 정리는 초당적 그래프에서 최대 일치는 최소 꼭지점 표지와 크기가 동일하다고 기술하고 있다. 이 결과를 통해 초당적 그래프의 경우 최소 꼭지점 커버, 최대 독립 세트 및 최대 정점 2iclique 문제를 다항 시간 내에 해결할 수 있다.

홀의 결혼정리는 완벽한 일치를 갖는 초당적 그래프의 특성화를 제공하고 투테의 정리는 임의의 그래프에 대한 특성화를 제공한다.

적용들

일반 그래프에서의 일치

• 방향족 화합물의 케쿨레 구조는 탄소 골격을 완벽하게 일치시켜 화학 구조에서 이중 결합의 위치를 보여준다. 이러한 구조물은 프리드리히 아우구스트 케쿨레 폰 스트라도니츠의 이름을 따서 벤젠(그래프의 이론적 용어로, 6Vertex cycle)이 그러한 구조를 부여받을 수 있다는 것을 보여주었다.^[19]
• 호소야 지수는 비빈 매치 수+1로 유기화합물의 연산 화학 및 수학적 화학 조사 등에 사용된다.

초당적 그래프의 일치

• 졸업문제는 주어진 졸업요건에서 최소수업을 선택하는 것이다.
• 히치콕 수송 문제는 초당적 매칭이 하위 문제로 작용한다.
• 하위 계통 이형성 문제에는 하위 문제로서 초당적 매칭이 포함된다.

참고 항목

• 하이퍼그래프의 일치 - 그래프의 일치 일반화.
• 분수 일치.
• 둘마지-멘델손 분해(Dulmage-Mendelson 분해)는 각 에지가 동일한 부분 집합에 속하는 경우에만 완벽한 일치를 갖도록 초당적 그래프의 정점을 부분 집합으로 분할한다.
• 그래프 모서리를 일치 항목으로 분할하는 모서리 색상
• 일치 사전 폐합, 기존과 완벽하게 일치하지 않도록 삭제할 최소 에지 수
• 레인보우 매칭, 반복된 색상이 없는 가장자리 색상의 초당적 그래프의 매칭
• 스큐 대칭 그래프(Skew-Symmetric graph), 일치 항목에 대한 교대 경로 검색을 모형화하는 데 사용할 수 있는 그래프 유형
• 안정적인 매칭, 일치하는 파트너보다 두 요소가 서로 선호하지 않는 매칭
• 정점 독립 집합, 두 개의 정점 집합(에지가 아닌 정점 집합)이 서로 인접하지 않음
• 안정적인 결혼 문제(안정적 매칭 문제라고도 함)

참조

추가 읽기

1. Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001), Introduction to Algorithms (second ed.), MIT Press and McGraw–Hill, Chapter 26, pp. 643–700, ISBN 0-262-53196-8{{citation}}: CS1 maint : 복수이름 : 작성자 목록(링크)
3. András Frank (2004). On Kuhn's Hungarian Method – A tribute from Hungary (PDF) (Technical report). Egerváry Research Group.
4. Michael L. Fredman and Robert E. Tarjan (1987), "Fibonacci heaps and their uses in improved network optimization algorithms", Journal of the ACM, 34 (3): 595–615, doi:10.1145/28869.28874, S2CID 7904683.
5. S. J. Cyvin & Ivan Gutman (1988), Kekule Structures in Benzenoid Hydrocarbons, Springer-Verlag
6. Marek Karpinski and Wojciech Rytter (1998), Fast Parallel Algorithms for Graph Matching Problems, Oxford University Press, ISBN 978-0-19-850162-6

외부 링크

• Hopcroft-Karp 및 Push-Relabel 기반 최대 카디널리티 일치 구현이 포함된 그래프 라이브러리