홉크로프트-카프 알고리즘

홉크로프트-카프 알고리즘
클래스	그래프 알고리즘
데이터 구조	그래프
최악의 경우 공연
최악의 경우 공간 복잡성

컴퓨터 과학에서, Hopcroft-Karp 알고리즘(때로는 더 정확하게 호프크로프트-Karp-Karzanov 알고리즘으로 불림)^[1]은 초당적 그래프를 입력하여 최대 카디널리티 일치를 산출하는 알고리즘이다. 즉, 두 모서리가 엔드포인트를 공유하지 않는 속성과 가능한 한 많은 에지의 집합을 생산한다.It runs in $O( E {\sqrt { V }})$ time in the worst case, where $E$ is set of edges in the graph, $V$ is set of vertices of the graph, and it is assumed that $E =\Omega ( V )$ . In the case of dense graphs 시간 제한은 $O(|V|^{2.5})$ ( $O(|V|^{2.5})$ 2.5 $O(|V|^{2.5})$ ) ${\displaystyle O(V ^{2.5})$ 가 되며 $O(|V|^{2.5})$ 희박한 랜덤 그래프의 경우 높은 확률로 $O(|E|\log |V|)$ 시간 $O(|E|\log |V|)$ $O(|E|\log |V|)$ V $O(|E|\log |V|)$ ) ${\displaystyle$ O $(E \log$ V $)$ 로 실행된다.^[2]

이 알고리즘은 존 홉크로프트와 리차드 카르프(1973)에 의해 발견되었고 알렉산더 카르자노프(1973)에 의해 독자적으로 발견되었다.^[3]헝가리 알고리즘과 에드몬드의 작업(1965)과 같은 매칭에 대한 이전의 방법에서와 같이, 홉크로프트-카프 알고리즘은 증강 경로를 찾아내어 부분 매칭의 크기를 반복적으로 증가시킨다.이러한 경로는 일치의 가장자리와 부분 일치의 가장자리 사이를 번갈아 가며 초기 에지와 최종 에지가 부분 일치를 하지 않는 그래프의 가장자리 시퀀스다.증분 경로를 찾으면 증분 경로의 가장자리를 간단히 토글하여 부분 일치의 크기를 증가시킬 수 있다(미확장 경로의 가장자리를 부분 일치로 입력하거나 그렇지 않은 경로의 가장자리로 입력).Simpler algorithms for bipartite matching, such as the Ford–Fulkerson algorithm‚ find one augmenting path per iteration: the Hopcroft-Karp algorithm instead finds a maximal set of shortest augmenting paths, so as to ensure that only $O({\sqrt { V }})$ iterations are needed instead of ${\displa$ $ystyle$ O $(V)}$ 반복 $O(V)$ . $O(|E|{\sqrt {|V|}})$ $){\displaystyle O(E {\sqrt{$ V $}}})$ 의 동일한 성능을 달성하여 미칼리와 바지라니의 보다 복잡한 알고리즘으로 임의 그래프에서 최대 카디널리티 일치를 찾을 수 있다 $O(|E|{\sqrt {|V|}})$ .^[4]

Hopcroft-Karp 알고리즘은 최대 흐름 문제에 대한 Dinic 알고리즘의 특별한 사례로 볼 수 있다.^[5]

경로 증가

$일부$ 부분 일치 M $M$ 에서 에지의 끝점이 아닌 정점을 자유 정점이라고 한다 $M$ .알고리즘이 의존하는 기본 개념은 확장 경로의 개념으로, 자유 정점에서 시작하여 자유 정점에서 끝나고 경로 내에서 일치하지 않는 가장자리와 일치되지 않은 가장자리 사이를 교대하는 경로다.이 정의는 엔드포인트를 제외하고 증가 경로의 다른 모든 정점(있는 경우)은 자유 정점이 아니어야 한다는 것을 따른다.증강 경로는 두 개의 꼭지점(둘 다 자유)과 그것들 사이의 일치하지 않는 단일 가장자리로만 구성될 수 있다.

$M$ $M$ 이(가) 일치하고 $M$ P ${\displaystyle$ $P$ $}$ 에 상대적인 증강 경로인 $P$ 경우 $M$ 두 에지 집합의 대칭 차이인 $M\oplus P$ ⊕ $M\oplus P$ ${\displaystyle M\oplus$ P $}$ 이(가 $)$ $|M|+1$ + $|M|+1$ ${\displaystystyle M +$ 1}과 일치를 형성할 것이다 $|M|+1$ 따라서 증가 경로를 찾음으로써 알고리즘은 일치의 크기를 증가시킬 수 있다.

반대로 일치하는 $M$ $M$ 이 $M$ (가) 최적이 아니라고 가정하고, $P$ $P$ 을(를) 대칭 차이 $M\oplus M^{*}$ $M\oplus M^{*}$ $∗$ {\ $displaystyle M^{*}}$ 이 $M^*$ (가) 되도록 $P$ 한다. $M^{*}$ 서 $M \oplus M^*$ M $M^{*}$ { $M^{*}$ {\ $displaystystyle$ M $^{*}}$ 이 최적 일치한다. $M$ $M$ 과 $M$ ( $)$ M $display$ {\ $displaystyle$ M $^{*}$ 은(는) 모두 일치하므로 $M^{*}$ 모든 정점에는 $P$ $P$ 에서 최대 2개의 등급이 있다 $P$ $따라서$ P ${\displaystyle P$ $}$ 은(는) 확장 $경로$ 의 $M$ ${\disjection$ 사이클의 집합을 구성해야 한다 $P$ $M$ $M$ 는 M ${\displaystyle M$ 의 경우 $M^{*}$ M $\$ {\ $displaystyle$ M $M^{*}$ 의 경로 증축이 가능하지만, $M^{*}$ $M^{*}$ ${\$ M $^{*}$ 이 최적이기 $M^{*}$ 때문에 후자는 불가능하다.이제 일치하거나 일치하지 않는 정점의 수가 동일한 사이클과 경로는 M $M$ 과 $M$ $M^{*}$ $와$ ) $M^{*}$ $M^{*}$ ${\$ 사이의 크기 차이에 기여하지 않으므로, 이 $P$ 는 P $P$ 의 $M$ M{\ $displaystyle M}$ 에 대한 증강 경로 수와 같다 $P$ 따라서 현재 일치하는 $M$ $M$ 보다 큰 일치하는 $M^{*}$ M $M^{*}$ ${\$ 이 있을 때마다 증가 경로도 존재해야 한다 $M$ $이$ 경우 M $M$ 이(가) 최적이어야 하므로 $M$ 증강 경로를 찾을 수 없는 경우 알고리즘이 안전하게 종료될 수 있다.

일치하는 문제에서의 증가 경로는 흐름의 단자 사이의 흐름량을 증가시킬 수 있는 경로인 최대 흐름 문제에서 발생하는 증가 경로와 밀접하게 관련되어 있다.쌍방향 일치 문제를 최대 흐름 인스턴스로 변환하여 일치 문제의 교대 경로가 흐름 문제의 경로 증대가 되도록 할 수 있다. $U$ {\ $displaystyle$ $U$ $U$ 의 소스에서 각 꼭지점까지, $그리고$ V ${\$ $displaystyle$ V $}$ 의 각 꼭지점에서 싱크까지 $V$ 장치 용량의 가장자리를 삽입하고 U {\ $displaystyle U}$ 에서 $U$ $V$ $V$ 까지의 가장자리에는 장치 용량이 있게 한다 $V$ .^[6]임의의 네트워크에서 최대 흐름을 찾기 위해 Hopcroft-Karp 알고리즘에서 사용되는 기법의 일반화를 Dinic의 알고리즘이라고 한다.

알고리즘.

알고리즘은 다음과 같은 가성으로 표현할 수 있다.

입력: 초당적 그래프

G(U\cup V,E)

G(U\cup V,E)

V

G(U\cup V,E)

,

G(U\cup V,E)

)

G(U\cup V,E)

출력:

M\subseteq E

하는

M\subseteq E

M\subseteq E

E

M\subseteq E

M\왼쪽 화살표 \emptyset

되풀이하여 말하다

{\mathcal{P}\왼쪽 화살표 \{P_{1},P_{2},\dots,P_{k}\}}

정점 분리 최단 증가 경로의 최대 집합

M\leftarrow M\oplus(P_{1}\cup P_{2}\cup \dots \cup P_{k}})

까지

{\mathcal{P}=\emptyset

$자세한$ 내용은 $U$ $U$ 과 $U$ V $V$ 을 $V$ (를 $G$ $G$ $G$ 의 양분에서 두 세트로 하고, U $U$ 에서 $U$ $V$ V $V$ 까지의 일치를 언제든지 $세트$ M{\ $displaysty M}$ 으로 나타내도록 하십시오. 알고리즘은 단계별로 실행된다 $M$ 각 단계는 다음과 같은 단계로 구성된다.

너비 우선 검색은 그래프의 정점을 레이어로 분할한다. $U$ $U$ 의 자유 정점은 이 검색의 시작 정점으로 사용되며 $U$ 분할의 첫 번째 계층을 형성한다. $U$ $U$ 의 자유 정점은 정의상 일치하는 가장자리와 인접하지 않기 $U$ 때문에 검색의 첫 번째 수준에는 일치하지 않는 가장자리만 있다.검색의 후속 레벨에서 교차된 가장자리는 일치된 가장자리와 일치하지 않는 가장자리로 교체해야 한다.즉, $U$ $U$ 의 꼭지점에서 후계자를 검색할 때 일치하지 않는 가장자리만 통과할 수 있고, $V$ $V$ 의 꼭지점에서는 일치하는 가장자리만 $V$ 통과할 수 있다 $U$ $V$ $V$ 에서 하나 이상의 사용 가능한 정점에 도달하는 첫 번째 $k$ $V$ k $k$ 에서 검색이 종료된다.
$K$ 레이어 $k$ 에 $V$ 있는V {\ $displaystyle V}$ 의 모든 자유 정점은 $F$ 된 F $F$ 에 수집된다 $k$ $F$ 즉, 정점 $v$ $v$ 이(가) $최단$ 확장 경로를 종료하는 경우에만 $F$ F ${\displaystystystyle F}$ 에 배치된다 $v$ .
알고리즘은 길이 $k$ $k$ 의 정점 분리 증분 경로의 최대 집합을 찾는다 $k$ 최대치란 그러한 경로가 더 이상 추가될 수 없음을 의미한다).이는 하기 어려울 그런 경로의 최대 개수를 찾는 것과는 다르다.다행히 여기서는 최대 경로 집합을 찾기에 충분하다.)이 세트는 $F$ $F$ 에서 $U$ $U$ 의 자유 정점까지의 깊이 $F$ 첫 번째 검색(DFS)으로 계산할 수 있으며 $U$ 검색의 안내를 위해 첫 번째 레이어링의 너비로만 DFS가 이전 계층에서 사용되지 않은 정점을 유도하는 에지를 따를 수 있으며, DFS 트리의 경로는 일치된 것과 언인 경로를 번갈아 사용해야 한다.일치된 가장자리 $F$ $F$ 의 꼭지점 중 하나를 포함하는 증가 경로가 발견되면 DFS는 다음 시작 꼭지점부터 계속된다 $F$ DFS의 현재 지점에서 $U$ $U$ $U$ 까지의 경로가 없는 경우 DFS의 다른 $U$ 에서 U{\ $displaystyle U$ }에 $U$ 도달하는 데 해당 정점을 사용할 수 없으므로 DFS 중에 발생하는 정점을 즉시 사용으로 표시할 수 있다.이렇게 하면 DFS의 $O(|E|)$ ( $O(|E|)$ ) ${\displaystyle$ O $(E )}$ 실행 시간이 $O(|E|)$ 보장된다. $또한$ U $U$ 의 자유 정점부터 유사코드에 사용되는 변형인 $V$ $V$ 의 정점까지 다른 $U$ 방향으로 작업하는 것도 가능하다.
$이러한$ 방식으로 발견된 모든 경로가 M $M$ 을(를) 확대하기 위해 사용된다 $M$

알고리즘은 단계 중 하나의 폭의 첫 번째 검색 부분에서 더 이상의 증가 경로가 발견되지 않을 때 종료된다.

분석

각 단계는 단일 범위 첫 번째 검색과 단일 깊이 첫 번째 검색으로 구성된다.따라서 단일 페이즈는 $O(|E|)$ ( $O(|E|)$ ) $O(E )$ 시간에 $O(|E|)$ 구현될 수 있다.따라서 $|V|$ $displaystyle V}$ $|E|$ 과 $|V|$ E $|E|$ {\ $displaystyle E}$ 가장자리가 $|E|$ 있는 그래프에서 첫 ${\sqrt {|V|}}$ V ${\sqrt {|V|}}$ {\displaystyle {\ $sqrt$ { $V$ $}$ $O(|E|{\sqrt {|V|}})$ 는 $\sqrt{|V|}$ O $O(|E|{\sqrt {|V|}})$ ) ${\displaystystyle O(E {\sqrt{$ $V}})}}$ 에 시간이 걸린다 $O(|E|{\sqrt {|V|}})$

각 위상은 최소 하나 이상 최단 증가 경로의 길이를 증가시킨다. 위상은 주어진 길이의 최대 증가 경로 집합을 찾으므로 나머지 증가 경로가 더 길어야 한다.따라서 알고리즘의 ${\sqrt {|V|}}$ V $displaystyle {\sqrt {V}$ 단계가 완료되면 ${\sqrt {|V|}}$ 최단 남은 증강 경로에는 적어도 ${\sqrt {|V|}}$ $displaystyle {\sqrt$ { $V}$ 개의 가장자리가 ${\sqrt {|V|}}$ 있다.그러나 최종 최적 일치와 초기 단계에 의해 발견된 부분 일치 M의 대칭적 차이는 정점-분할 경로와 교대 사이클의 집합을 형성한다.이 컬렉션의 각 경로에 길이가 ${\sqrt {|V|}}$ V {\ $displaystyle {\sqrt{$ V ${\sqrt {|V|}}$ 인 경우 ${\sqrt {|V|}}$ 에 V ${\sqrt {|V|}}$ {\ $displaystyle$ {\ $sqrt{ V}}}$ 개 ${\sqrt {|V|}}$ 경로가 있을 수 있으며, 최적의 일치 크기는 ${\sqrt {|V|}}$ V $displaystyle$ $M}$ 의 $M$ 크기와 다를 수 있다. ${\sqrt{V}}$ 에지 ${\sqrt {|V|}}$ .알고리즘의 각 위상은 일치의 크기를 적어도 하나 이상 증가시키므로 알고리즘이 종료되기 전에 ${\sqrt {|V|}}$ V $displaystyle {\sqrt{$ V $}$ 의 추가 ${\sqrt {|V|}}$ 위상이 있을 수 있다.

알고리즘은 최대 $2{\sqrt {|V|}}$ $displaystyle 2{\sqrt{V}}$ 페이즈에서 총 2V {\sqrt {V}을 $2{\sqrt {|V|}}$ (를) 수행하므로 최악의 경우 $O(|E|{\sqrt {|V|}})$ 총 $O(|E|{\sqrt {|V|}})$ $O(|E|{\sqrt {|V|}})$ $){\displaystyle O(E {\sqrt{$ V $})$ 의 시간이 소요된다.

그러나 대부분의 경우 알고리즘에 의해 걸리는 시간은 이 최악의 경우 분석이 나타내는 시간보다 훨씬 더 빠를 수 있다.예를 들어, 희박한 초당 랜덤 그래프의 평균 사례에서 Bast 등. (2006) (Motwani 1994의 이전 결과 개선) 높은 확률로 모든 비최적 일치 항목이 로그 길이의 경로를 증가시킨다는 것을 보여주었다.따라서 이러한 그래프에 대해 Hopcroft-Karp 알고리즘은 총 O( $O(\log |V|)$ $O(|E|\log |V|)$ $O(\log |V|)$ ) ${\displaystyle O(\log$ V $)}$ 단계와 $O(\log |V|)$ $O(|E|\log |V|)$ $O(|E|\log |V|)$ $O(|E|\log |V|)$ V $O(|E|\log |V|)$ ) ${\displaystyle O(E \log$ V $)}$ 의 총 시간이 소요된다.

다른 초당적 매칭 알고리즘과 비교

희소성 그래프의 경우, Hopcroft-Karp 알고리즘은 계속해서 가장 잘 알려진 최악의 성능을 유지하지만, 조밀한 그래프( $|E|=\Omega (|V|^{2})$ = $|E|=\Omega (|V|^{2})$ ( $|E|=\Omega (|V|^{2})$ 2 $|E|=\Omega (|V|^{2})$ ) ${\displaystyle$ E $=\Oomega ($ V $^{2$ 의 경우, Alt 외 연구진(1991)의 보다 최근의 알고리즘은 시간 범위 O( $O\left(|V|^{1.5}{\sqrt {\frac {|E|}{\log |V|}}}\right)$ 1. $O\left(|V|^{1.5}{\sqrt {\frac {|E|}{\log |V|}}}\right)$ ⁡ $O\left(|V|^{1.5}{\sqrt {\frac {|E|}{\log |V|}}}\right)$ V $O\left(|V|^{1.5}{\sqrt {\frac {|E|}{\log |V|}}}\right)$ 를 약간 더 잘 달성한다. $O\left(|V|^{1.5}{\sqrt {\frac {|E|}{\log |V|}}}\right)$ ${\$ V $}}\오른쪽$ .그들의 알고리즘은 푸시-릴라벨 최대 흐름 알고리즘을 사용한 다음, 이 알고리즘에 의해 만들어진 일치가 최적치에 가까워지면, Hopcroft-Karp 방법으로 전환되는 것에 기초한다.

여러 저자가 초당적 매칭 알고리즘의 실험적 비교를 수행했다.일반적으로 그들의 결과는 Hopcroft-Karp 방법이 이론에서처럼 실제적으로 좋지 않다는 것을 보여주는 경향이 있다. 즉, 확대 경로를 찾기 위한 단순한 폭 우선 및 깊이 우선 전략과 푸시-릴라벨 기법 둘 다에 의해 능가된다.^[7]

비-Bipartite 그래프

최단 증강 경로의 최대 집합을 찾는 동일한 아이디어는 비-비-비-비-바타이트 그래프에서 최대 카디널리티 일치를 찾는 데에도 효과가 있으며, 같은 이유로 이 아이디어를 기반으로 하는 $O({\sqrt {|V|}})$ 은 O $O({\sqrt {|V|}})$ ( $){\displaystyle$ O $({\sqrt{{V}})}$ 단계를 $O({\sqrt {|V|}})$ 취한다.단, 비-biparte 그래프의 경우 각 단계 내에서 증강 경로를 찾는 작업이 더 어렵다.미칼리 & 바지라니(1980년)는 몇몇 느린 전임자들의 작업을 토대로 하여, 한 단계를 선형 시간에 구현하는 방법을 보여주었고, 그 결과 초당적 그래프를 위한 Hopcroft-Karp 알고리즘과 동일한 시간 바인딩으로 비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-비-미칼리-바지라니 기법은 복잡하고, 그 저자들은 그들의 결과에 대한 완전한 증거를 제공하지 않았다. 그 후, 피터슨&루이(1988)에 의해 "명확한 설명"이 출판되었고, 다른 작가들에 의해 대체 방법이 설명되었다.^[8]2012년에 바지라니는 미칼리-바지라니 알고리즘의 새로운 단순화된 증거를 제시했다.^[9]

가성음

/* G = U and V ∪ {NIL} 여기서 U와 V는 양분 그래프의 왼쪽과 오른쪽이고 NIL은 특수 null 정점 */ 함수 BFS()는 Pair_일 경우 U에서 각 U에 대한 것이다.U[u] = NIL 이후 Dist[u] := 0 Enqueue(Q, u) 기타 Dist[u] := ∞ Dist[]NIL] :=공백(Q) = 거짓 do u := Dist[u] < Dist[]이면 Dequeue(Q)NIL] 그러면 Adj[u]의 각 v에 대해 Dist[Pair_V[v] = Dist[Pair_V] :=Dist[u] + Enqueue(Q, Pair_V[v])가 Dist[Pair]를 반환하면 된다.NIL] ≠ ∞ 함수 DFS(u)는 u NIL이면 Adj[u]의 각 v에 대해 Dist[Pair_V[v] = Dist[u] + 1이면 DFS(Pair_V[v]) = true이면 Pair_V[v] = Upair] = Upair____air____air]이다.U[u] :=v return true Dist[u] := ∞ return false true 함수 Hopcroft-Karp는 Udo Pair_의 각 u에 대한 것이다.U[u] :=V do Pair_V[v] := NIL 일치 := 0인 반면 BFS()는 Pair_일 경우 U do에서 각 u에 대해 true do.U[u] = NIL DFS(u) = true이면 일치 := 일치 + 1 반환 일치

중간 반복 1과 최종 반복 2 이후의 입력 그래프를 보여주는 예제 그래프에서 실행.

설명

그래프의 정점을 U와 V로 분할하고 U와 V의 각 정점이 일치하는 하나의 정점을 포함하는 Pair_U와 Pair_V 테이블에서 표시한 대로 부분 일치 또는 일치하지 않는 정점에 대한 NIL을 고려하십시오.핵심 아이디어는 그래프의 양쪽에 두 개의 더미 정점, 즉 U의 모든 일치하지 않는 정점에 연결된 uDummy와 V의 모든 일치하지 않는 정점에 연결된 vDummy를 추가하는 것이다.이제 uDummy에서 vDummy까지 BFS(광역 우선 검색)를 실행하면 현재 U에서 일치하지 않는 정점과 V에서 현재 일치하지 않는 정점을 연결하는 최소 길이의 경로를 얻을 수 있다.그래프가 초당적이기 때문에 이러한 경로는 항상 U의 정점과 V의 정점 사이를 번갈아 가며, 우리는 BFS에서 V에서 U로 이동할 때 항상 일치하는 에지를 선택하도록 요구한다.V의 정점에 도달하면 vDummy에서 종료되고 BFS의 경로 검색이 종료된다.요약하자면, BFS는 U에서 일치하지 않는 정점에서 시작하여 V의 모든 주변 정점으로 이동하며, 만약 모든 정점이 일치한다면, 이 정점들이 일치하는 U의 정점으로 되돌아간다(그리고 이전에는 방문하지 않았던 정점들), 그리고 V에서 도달한 정점들 중 하나가 일치하지 않을 때까지 이 정점들의 모든 이웃들로 이동한다.

특히 BFS가 U의 일치하지 않는 노드를 거리 0으로 표시한 다음 U로 돌아올 때마다 거리를 늘린다. 이렇게 하면 BFS에서 고려하는 경로가 최소 길이의 것으로서 U의 일치하지 않는 정점을 V의 일치하지 않는 정점에 연결하는 동시에 현재 일부인 가장자리에서는 항상 V에서 U로 되돌아가는 것을 보장할 수 있다.e 매칭특히 vDummy에 해당하는 특수 NIL 정점에는 유한 거리가 할당되므로, 만약 일부 경로가 발견되면 BFS 함수는 true를 반환한다.경로를 찾을 수 없는 경우, 추가 경로가 남아 있지 않고 일치 항목이 최대값이다.

BFS가 true를 반환하면 U에서 V로 이어지는 최소 길이 경로에서 정점에 대한 페어링을 업데이트할 수 있다. 우리는 DFS(Depth-First Search)를 사용하여 그렇게 한다.이러한 경로에 있는 V의 각 꼭지점(마지막 정점 제외)은 현재 일치한다는 점에 유의하십시오.따라서 우리는 DFS를 통해 우리가 따르는 경로가 BFS에서 계산된 거리와 일치하는지 확인할 수 있다.현재 일치 중인 경로의 모든 에지에서 일치하는 경로를 제거하고 현재 일치되지 않은 경로의 모든 에지(경로의 첫 번째 및 마지막 에지는 일치 경로의 일부가 아니었으며, 일치하는 경로 사이에 교대된 경로)에 추가함으로써 이러한 경로를 따라 업데이트한다.일치하지 않는 가장자리 수), 이렇게 하면 일치되는 가장자리 수가 증가한다.이는 현재 일치와 전체 경로 사이의 대칭적 차이에 의해 전류 일치를 대체하는 것과 같다.

이 코드는 우리가 고려하는 모든 증강 경로가 정점 분리임을 보장한다는 점에 유의한다.실제로, DFS에서는 Dist[Pair_V[V]가 Dist[u] + 1(정확히 Dist[u]가 아니라는 이유만으로, 어떤 정점도 다시 고려할 수 없었다.

또한 DFS가 동일한 꼭지점을 여러 번 방문하지 않도록 주의하십시오.이는 다음 대사 덕분이다.

dist[u] = ∞ 반환 거짓

정점 u에서 가장 짧은 증가 경로를 찾을 수 없을 때 DFS는 Dist[u]를 무한대로 설정하여 정점 u를 표시하므로 이러한 정점들이 다시 방문되지 않는다.

마지막 관찰은 우리가 실제로 UDummy를 필요로 하지 않는다는 것이다: 그것의 역할은 단순히 우리가 BFS를 시작할 때 비교할 수 없는 U의 모든 정점을 대기열에 넣는 것이다.vDummy에 대해서는 위의 가성 코드에서 NIL로 표기된다.

참고 항목

최대 카디널리티 일치, 알고리즘에 의해 해결된 문제, 비-비-비-비-바타이트 그래프에 대한 일반화
할당 문제, 가중 그래프에서 이 문제의 일반화, 예를 들어 헝가리 알고리즘에 의해 해결됨
최대 흐름을 찾기 위한 Edmonds-Karp 알고리즘, Hopcroft-Karp 알고리즘의 일반화

메모들

^ 가보우(2017년); 안나말라이(2018년)
^ 바스트 외. (2006).
^ 디니츠(2006년).
^ 피터슨&루이(1988년).
^ 타르잔(1983년), 페이지 102.
^ 아후자, 마그난티 & 오를린(1993) 섹션 12.3, 초당적 카디널리티 일치 문제, 페이지 469–470.
^ Chang & McCormick (1990), Darby-Dowman (1980), Setubal (1993 ), Setubal (1996).
^ 가보 & 타르잔(1991년).
^ 바지라니(2012년)

참조

Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), Network Flows: Theory, Algorithms and Applications, Prentice-Hall.
Alt, H.; Blum, N.; Mehlhorn, K.; Paul, M. (1991), "Computing a maximum cardinality matching in a bipartite graph in time $\scriptstyle O\left(n^{1.5}{\sqrt {\frac {m}{\log n}}}\right)$ ", Information Processing Letters, 37 (4): 237–240, doi:10.1016/0020-0190(91)90195-N.
Annamalai, Chidambaram (2018), "Finding perfect matchings in bipartite hypergraphs", Combinatorica, 38 (6): 1285–1307, arXiv:1509.07007, doi:10.1007/s00493-017-3567-2, MR 3910876, S2CID 1997334
Bast, Holger; Mehlhorn, Kurt; Schäfer, Guido; Tamaki, Hisao (2006), "Matching algorithms are fast in sparse random graphs", Theory of Computing Systems, 39 (1): 3–14, doi:10.1007/s00224-005-1254-y, MR 2189556, S2CID 9321036
Chang, S. Frank; McCormick, S. Thomas (1990), A faster implementation of a bipartite cardinality matching algorithm, Tech. Rep. 90-MSC-005, Faculty of Commerce and Business Administration, Univ. of British Columbia. Setubal(1996)에서 인용한 바와 같다.
Darby-Dowman, Kenneth (1980), The exploitation of sparsity in large scale linear programming problems – Data structures and restructuring algorithms, Ph.D. thesis, Brunel University. Setubal(1996)에서 인용한 바와 같다.
Dinitz, Yefim (2006), "Dinitz' Algorithm: The Original Version and Even's Version", in Goldreich, Oded; Rosenberg, Arnold L.; Selman, Alan L. (eds.), Theoretical Computer Science: Essays in Memory of Shimon Even, Lecture Notes in Computer Science, vol. 3895, Berlin and Heidelberg: Springer, pp. 218–240, doi:10.1007/11685654_10.
Edmonds, Jack (1965), "Paths, Trees and Flowers", Canadian Journal of Mathematics, 17: 449–467, doi:10.4153/CJM-1965-045-4, MR 0177907.
Gabow, Harold N. (2017), "The weighted matching approach to maximum cardinality matching", Fundamenta Informaticae, 154 (1–4): 109–130, arXiv:1703.03998, doi:10.3233/FI-2017-1555, MR 3690573, S2CID 386509
Gabow, Harold N.; Tarjan, Robert E. (1991), "Faster scaling algorithms for general graph matching problems", Journal of the ACM, 38 (4): 815–853, doi:10.1145/115234.115366, S2CID 18350108.
1971년 제12회 자동변환 이론 심포지엄에서 발표하였다Hopcroft, John E.; Karp, Richard M. (1973), "An n^5/2 algorithm for maximum matchings in bipartite graphs", SIAM Journal on Computing, 2 (4): 225–231, doi:10.1137/0202019.
Karzanov, A. V. (1973), "An exact estimate of an algorithm for finding a maximum flow, applied to the problem on representatives", Problems in Cybernetics, 5: 66–70. 조합 수학 세미나에서 이전에 발표되었다(Moscow, 1971).
Micali, S.; Vazirani, V. V. (1980), "An $\scriptstyle O({\sqrt { V }}\cdot E )$ algorithm for finding maximum matching in general graphs", Proc. 21st IEEE Symp. Foundations of Computer Science, pp. 17–27, doi:10.1109/SFCS.1980.12, S2CID 27467816.
Peterson, Paul A.; Loui, Michael C. (November 1988), "The general maximum matching algorithm of Micali and Vazirani", Algorithmica, 3 (1–4): 511–533, CiteSeerX 10.1.1.228.9625, doi:10.1007/BF01762129, ISSN 1432-0541, S2CID 16820.
Motwani, Rajeev (1994), "Average-case analysis of algorithms for matchings and related problems", Journal of the ACM, 41 (6): 1329–1356, doi:10.1145/195613.195663, S2CID 2968208.
Setubal, João C. (1993), "New experimental results for bipartite matching", Proc. Netflow93, Dept. of Informatics, Univ. of Pisa, pp. 211–216. Setubal(1996)에서 인용한 바와 같다.
Setubal, João C. (1996), Sequential and parallel experimental results with bipartite matching algorithms, Tech. Rep. IC-96-09, Inst. of Computing, Univ. of Campinas, CiteSeerX 10.1.1.48.3539.
Tarjan, Robert Endre (1983). Data Structures and Network Algorithms. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
Vazirani, Vijay (2012), An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm, CoRR abs/1210.4594, arXiv:1210.4594, Bibcode:2012arXiv1210.4594V.

[1] 가보우(2017년); 안나말라이(2018년)

[FOOTNOTEBastMehlhornSchäferTamaki2006-2] 바스트 외. (2006).

[FOOTNOTEDinitz2006-3] 디니츠(2006년).

[FOOTNOTEPetersonLoui1988-4] 피터슨&루이(1988년).

[FOOTNOTETarjan1983102-5] 타르잔(1983년), 페이지 102.

[6] 아후자, 마그난티 & 오를린(1993) 섹션 12.3, 초당적 카디널리티 일치 문제, 페이지 469–470.

[7] Chang & McCormick (1990), Darby-Dowman (1980), Setubal (1993 ), Setubal (1996).

[8] 가보 & 타르잔(1991년).

[9] 바지라니(2012년)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Search