최대 카디널리티 일치

최대 카디널리티 매칭은 그래프 이론에서 근본적인 문제다.^[1]그래프 $G{\displaystyle }$ ${\displaystyle G}$을$($를) 제공받았으며 목표는 가능한 한 많은 에지, 즉 각 정점이 부분 집합의 최대 한 에지에 인접하도록 에지의 최대 카디널리티 서브셋을 포함하는 일치를 찾는 것이다.각 가장자리는 정확히 두 개의 정점을 커버하므로, 이 문제는 가능한 한 많은 정점을 커버하는 일치를 찾는 작업과 동일하다.

최대 카디널리티 일치 문제의 중요한 특별한 경우는 G가 초당적 그래프일 때, 정점 V가 X의 왼쪽 정점과 Y의 오른쪽 정점 사이에 분할되고 E의 가장자리는 항상 왼쪽 정점을 오른쪽 정점에 연결한다.이 경우 일반적인 경우보다 간단한 알고리즘으로 문제를 효율적으로 해결할 수 있다.

초당적 그래프 알고리즘

흐름 기반 알고리즘

최대 카디널리티 일치를 계산하는 가장 간단한 방법은 포드-풀커슨 알고리즘을 따르는 것이다.이 알고리즘은 최대 흐름을 계산하는 일반적인 문제를 해결한다.초당적 그래프(X+Y, E)는 다음과 같이 플로우 네트워크로 변환할 수 있다.

• 소스 꼭지점 s를 추가하고, X의 각 꼭지점에 s의 가장자리를 추가한다.
• 싱크 정점 t를 추가하고 Y의 각 정점에서 t까지의 가장자리를 추가한다.
• 각 에지에 1의 용량을 할당하십시오.

네트워크의 각 가장자리에는 정수 용량이 있기 때문에 모든 흐름이 정수인 최대 흐름이 존재한다. 모든 용량이 1이므로 이들 정수는 0 또는 1이어야 한다.각 적분 흐름은 흐름이 1인 경우 에지가 일치하는 일치 항목을 정의한다.다음과 같은 이유로 일치한다.

• X의 각 꼭지점으로 들어오는 흐름은 최대 1이므로, 나가는 흐름도 최대 1이므로 X의 각 꼭지점에 인접한 최대 하나의 가장자리가 존재한다.
• Y의 각 꼭지점에서 나가는 흐름은 최대 1이므로, 유입되는 흐름도 최대 1이므로 Y의 각 꼭지점에 인접한 최대 하나의 가장자리가 존재한다.

Ford-Fulkerson 알고리즘은 일부 x from X에서 일부 y ∈ Y까지의 증강 경로를 반복적으로 찾아내고 M과 그 경로의 대칭적 차이를 취함으로써 일치하는 M을 업데이트하는 것으로 진행한다(그런 경로가 존재한다고 가정).${\displaystyle 각}$ 경로는 O${\displaystyle }$(${\displaystyle E}$) ${\displaystyle$\$O(E)}$시간에서$$ 찾을 수 있으므로, 실행 시간은 O${\displaystyle }$(${\displaystyle V)}$ ${\displaystyle$\$O(VE)}$이며$,$ 최대 일치는 X에서 Y로 흐름을 전달하는 E의 가장자리로 구성된다.

고급 알고리즘

이 알고리즘의 개선은 다중 증가 경로를 동시에 검색하는 보다 정교한 Hopcroft-Karp 알고리즘에 의해 주어진다.이 알고리즘은 $O{\displaystyle (V\sqrt{}}$ ${\displaystyle E}$) ${\displaystyle O({\sqrt{V}E)}$번으로$$ 실행된다.

Chandran과 Hochbaum[2]의 2부로 구성된 그래프에 대한 알고리즘에서는 X에 대한<>최대 일치하는 k{k\displaystyle}의 크기에 따라 때에 Y{\displaystyle X<>Y}은 O({\displaystyle O\left(\min\{Xk,E\}+{\sqrt{k}}\min\{k를 운영한다.^{2},E\})$right)}$. Using boolean operations on words of size ${\displaystyle \lambda }$ the complexity is further improved to ${\displaystyle O\left(\min \left\{ X k,{\frac { X Y }{\lambda }},E\right\}+k^{2}+{\frac {k^{2.$$5}{{\\cHBDA$}}\$오른쪽)}$ $."$^[2]

특별한 종류의 초당적 그래프를 위한 보다 효율적인 알고리즘이 존재한다.

• 희박한 초당적 그래프의 경우 최대 일치 문제를 전기 흐름에 기초한 매드리 알고리즘으로 $O$ ~${\displaystyle }$( E ${\displaystyle {10\mathrm{}}^{}}$/ 7${\displaystyle {}^{}}$) ${\displaystyle {\tilde{O}(E^{10/7})$에서 해결할 수 있다.^[3]
• 평면 쌍방향 그래프의 경우, 복수의 선원과 싱크에서 최대 흐름으로 문제를 줄임으로써, n이 정점수인 O(n\log $^{3}n)$ 시간 $O{\displaystyle (n}$ ${\displaystyle {\log }^{}}$ ${\displaystyle {3\mathrm{}}^{}}$ $){\displaysty O(n\log$ ^}n)에서 문제를 해결할 수 있다.^[4]

임의 그래프 알고리즘

Bloom 알고리즘은 일반적으로(꼭 초당적인 것은 아님) 그래프의 최대 카디널리티 일치를 찾는다.시간 $O{\displaystyle }$(${\displaystyle V}$ ${\displaystyle {}^{\mathrm{}}}$ ${\displaystyle {}^{}}$ ${\displaystyle E}$) ${\displaystyle O(V ^{2}\cdot$ E $)\}\}.$ 초당적 그래프에 대한 Hopcroft-Karp 알고리즘의 성능에 걸맞게 일반 그래프에 대한 (iii)VE의 더 나은 성능을 미칼리와 바지라니라는 훨씬 복잡한 알고리즘으로 달성할 수 있다.^[5]같은 경계는 블럼(de)^[6]의 알고리즘과 가보우와 타르잔의 알고리즘에 의해 달성되었다.^[7]

대안적 접근법은 무작위화를 사용하며 빠른 매트릭스 곱셈 알고리즘을 기반으로 한다.이것은 복잡성 $O{\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {2.376}^{}}$) ${\displaystyle O(V^{2.376})$가 있는 일반 그래프의 무작위화된 알고리즘을 제공한다$.$^[8]이것은 이론상으로는 충분히 밀도가 높은 그래프에 더 좋지만, 실제로는 알고리즘이 더 느리다.^[2]

과제에 대한 다른 알고리즘은 듀안과 페티가^[9] 검토한다(표 I 참조).근사 알고리즘의 측면에서도 미칼리와 바지라니에 의한 블라썸 알고리즘과 알고리즘은 고정된 오차범위에 대해 선형적으로 실행되는 근사 알고리즘으로 볼 수 있다고 지적한다.

애플리케이션 및 일반화

• 최대 카디널리티 일치를 찾음으로써 완벽한 일치가 있는지 여부를 결정할 수 있다.
• 가중 그래프에서 최대 중량으로 일치를 찾는 문제를 최대 가중치 일치 문제라고 하며, 초당적 그래프에 대한 제한을 할당 문제라고 한다.각 정점을 한 번에 여러 정점과 일치시킬 수 있다면 이는 일반적인 할당 문제다.
• 우선 순위 일치는 우선 순위가 매칭된 정점이 먼저 일치하는 특정 최대 카디널리티 일치를 말한다.
• 하이퍼그래프에서 최대 카디널리티 일치를 찾는 문제는 3개 균일 하이퍼그래프에서도 NP-완전하다.^[10]

참조