블라썸 알고리즘

블라썸 알고리즘은 그래프에 최대 일치를 구성하기 위한 그래프 이론의 알고리즘이다.이 알고리즘은 1961년 잭 에드먼즈에 의해 개발되었고,^[1] 1965년에 출판되었다.^[2]일반 그래프 G = (V, E)를 지정하면 알고리즘은 일치하는 M을 찾아 V의 각 꼭지점이 M의 최대 한 에지와 입사하도록 하고 M을 최대화한다.일치는 그래프의 경로 증대를 따라 초기 빈 일치를 반복적으로 개선하여 생성된다.초당적 매칭과 달리 새로운 핵심 아이디어는 그래프에서 홀수 길이 사이클(블라우섬)이 단일 꼭지점으로 수축되고, 수축된 그래프에서 반복적으로 검색이 지속된다는 것이다.

알고리즘은 시간 $O{\displaystyle (E}$ V ${\displaystyle {}^{\mathrm{}}}$) ${\displaystyle O(E$V$^{2})$로 실행되며$,$ ${\displaystyle 여기}$서 ${\displaystyle E}$ $displaystyle E}$은 그래프의 가장자리 수, V $displaystyle V}$은 정점 수입니다.동일한 작업에 대한$$ $O{\displaystyle ({}^{\mathrm{}}}$ ${\displaystyle V}$ 1${\displaystyle {}^{}}$/ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle O(E$V$^{1/2})$의 더 나은 실행 시간은 미칼리와 바지라니라는 훨씬 복잡한 알고리즘을 사용하여 달성할 수 있다.^[3]

블라썸 알고리즘이 중요한 주요 이유는 다항식 연산 시간을 이용해 최대 크기 일치를 찾을 수 있다는 첫 번째 증거를 제시했기 때문이다.또 다른 이유는 그것이 일치 폴리토프에 대한 선형 프로그래밍 다면체 설명으로 이어져서 미니 웨이트 매칭을 위한 알고리즘을 제시했기 때문이다.^[4]알렉산더 슈리히버가 상세히 기술한 바와 같이, 그 결과의 더 큰 의의는 이것이 "전혀 비이상적인 것만으로 간단히 따라가지 않는 최초의 폴리토프였으며, 그 서술은 다면 결합술의 획기적인 발전이었다"는 사실에서 나온다.^[5]

경로 증가

G = (V, E)와 일치하는 G의 M을 주어진 경우, M의 가장자리가 v와 충돌하지 않는 경우 정점 v가 노출된다. G의 경로는 그 가장자리가 M과 M(또는 M에 있지 않은 경우)에 번갈아 있는 경우(또는 M에 있지 않은 경우)의 교차 경로다. 증가 경로 P는 노출된 두 정점으로부터 시작하고 끝나는 교대 경로다.증가 경로에서 일치하지 않는 에지 수가 일치된 에지 수보다 1개 더 크므로 증가 경로의 총 에지 수는 홀수라는 점에 유의하십시오.증강경로 P를 따라 매칭 증가는 $M{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= ${\displaystyle M}$ ${\displaystyle \oplus }$ ${\displaystyle P}$=${\displaystyle }$(${\displaystyle M}$ ${\displaystyle \setminus }$ ${\displaystyle P}$) ${\displaystyle \cup }$( P ${\displaystyle \setminus }$ ${\displaystyle M}$) ∪ (${\displaystyle P}$ ∖ M )$${ (P style M ) {\$displaystyle M_{1}=M\oplus P=(M\setminus$ P$)\cup (P\setminus M$

Berge의 보조정리기로, 일치하는 M은 G에 M-증강 경로가 없는 경우에만 최대값이다.^[6][7]따라서 일치가 최대치이거나 또는 증강될 수 있다.따라서 초기 일치부터 현재 일치를 찾을 수 있는 한 증가 경로로 증가시킴으로써 최대 일치를 계산할 수 있으며, 증가 경로가 남아 있지 않을 때는 언제든지 반환할 수 있다.알고리즘을 다음과 같이 공식화할 수 있다.

INPUT:  Graph G, initial matching M on G    OUTPUT: maximum matching M* on G A1 function find_maximum_matching(G, M) : M* A2     P ← find_augmenting_path(G, M) A3     if P is non-empty then A4         return find_maximum_matching(G, augment M along P) A5     else A6         return M A7     end if A8 end function

우리는 어떻게 증강 경로를 효율적으로 찾을 수 있는지 여전히 설명해야 한다.그들을 찾기 위한 서브루틴은 꽃과 수축을 사용한다.

꽃과 수축

G = (V, E)와 G의 일치하는 M을 볼 때, 블라썸 B는 정확히 k가 M에 속하는 2k + 1 에지로 구성된 G의 사이클이며, 사이클의 꼭지점 v 중 하나가 v에서 노출된 꼭지점 w까지 균일한 길이(줄기)의 교대 경로가 존재하는 경우다.

꽃 찾기:

• 노출된 정점부터 그래프를 가로지른다.
• 그 꼭지점에서 시작하여, 바깥 꼭지점 "o"로 라벨을 붙인다.
• 내부 "i"인 정점과 외부 "o"인 정점 사이에 라벨을 교체하여 두 개의 인접한 정점이 동일한 라벨을 가지지 않도록 한다.
• 만약 우리가 바깥쪽 "o"라고 표시된 두 개의 인접 정점을 갖게 된다면, 우리는 홀수 길이 사이클을 갖게 되고 따라서 꽃이 핀다.

수축된 그래프 G'를 B의 모든 가장자리를 수축하여 G로부터 얻은 그래프로 정의하고, 수축된 일치 M'을 M에 해당하는 G'의 일치로 정의한다.

G'는 G가 M-증강 경로가 있는 경우에만 M-증강 경로를 가지고 있으며, B가 수축력을 해제하여 G'의 M'증강 경로 P'를 G의 M-증강 경로로 들어 올려 V를_B 통과하는 P' (있는 경우)의 세그먼트가 B를 통과하는 적절한 세그먼트로 대체되도록 한다.^[8]자세한 내용:

• P'가 세그먼트 u → v → w_B in G'를 통과하면, 이 세그먼트는 세그먼트 u → (u' → ...로 대체된다. → w' ) → g에서, 꽃 정점이 u'와 w' 그리고 b의 옆면인 (u' → ... → u')에서 w'로 이동하는 것은 새로운 경로가 여전히 교대로 유지되도록 하기 위해 선택된다(${\displaystyle {}^{}}$는 M ∩$[\displaystyle$ M$\cap B},${${\displaystyle w}$ ${\displaystyle {\prime }^{}}$ , w${\displaystyle \}}$ ${\displaystyle E\{}$ ${\displaystyle M}$ ${\displaystyle \{w',w\}\in$ E$\setmus M}).$

• P'에 끝점 v가_B 있으면 경로 세그먼트 u → g'가 세그먼트_B u → (u' → ...로 대체된다. 꽃 정점이 u'와 v' 그리고 B의 옆면이 있는 G에서 (u' → ... → u'에서 v'로 가는 경로를 교대로(v'가 노출되도록 선택한다$({\displaystyle }$v'가 노출됨, { ${\displaystyle {}^{}\prime ,}$ ${\displaystyle u}$} ${\displaystyle E}$ ${\displaystyle M}$ {\$displaystyle \{u',u\}\\in E\setminus M}).$

따라서 꽃들은 수축될 수 있고 수축된 그래프에서 검색할 수 있다.이 감소는 에드몬드의 알고리즘의 핵심이다.

증축 경로 찾기

증강 경로 검색은 개별 트리가 그래프 G의 특정 부분에 해당하는 포리스트 F로 구성된 보조 데이터 구조를 사용한다.사실, 숲 F는 (꽃을 줄이지 않아도) 초당적 그래프에서 최대 일치점을 찾는 데 사용되는 것과 같다.각 반복에서 알고리즘은 (1) 증분 경로를 찾거나, (2) 꽃을 찾아 해당 수축된 그래프에 재귀하거나, (3) 증분 경로가 없다는 결론을 내린다.보조 구조는 다음에 논의되는 증분 절차에 의해 구축된다.^[8]

시공 절차는 정점 v와 에지 e in G를 고려하며 F를 증분 업데이트한다.만약 v가 숲의 T나무에 있다면, 우리는 루트(v)가 T의 뿌리를 나타내도록 한다.u와 v가 모두 F의 같은 트리 T에 있다면, 우리는 거리(u,v)는 T의 u에서 v까지의 고유 경로의 길이를 나타낸다.

INPUT:  Graph G, matching M on G     OUTPUT: augmenting path P in G or empty path if none found B01 function find_augmenting_path(G, M) : P B02    F ← empty forest B03    unmark all vertices and edges in G, mark all edges of M B05    for each exposed vertex v do B06        create a singleton tree { v } and add the tree to F B07    end for B08while there is an unmarked vertex v in F with distance(v, root(v)) even do B09        while there exists an unmarked edge e = { v, w } do B10            if w is not in F then                    // w is matched, so add e and w's matched edge to F B11                x ← vertex matched to w in M B12                add edges { v, w } and { w, x } to거리(w, 루트(w))가 홀수인 경우 // 아무 것도 하지 마십시오.B15 그 밖의 B16은 root(v) (root(w)이면 // F $\cup {\displaystyle }$ ${\displaystyle \cup }{$ e }. B17 P ← 경로(root(v) → … → v) → (w → ...)로 증분 경로를 보고한다.→ root(w) B18 return P B19 other // G로 꽃을 계약하고 계약된 그래프에서 경로를 찾는다.B20 B '경로 v → W in T B21 G'에서 e와 가장자리에 의해 형성된 꽃, B22 P에 의한 M'의 ← 계약 G 및 M' find_증강_path(G', M') B23 P 'P'는 B26이 끝나면 G B24 P B25로 돌아간다.B28 표시 에지 e B29가 끝나는 동안 B30 표시 꼭지점 V B31이 끝나는 동안 B32가 빈 경로 B33 끝 함수를 반환하는 경우 종료

예

다음 4개의 그림은 알고리즘의 실행을 예시한다.점선은 현재 숲에 존재하지 않는 가장자리를 나타낸다.첫째, 알고리즘은 현재 숲(B10 – B12 라인)의 확장을 유발하는 숲 밖의 가장자리를 처리한다.

다음으로 꽃을 감지하여 그래프(B20~B21 선)를 수축시킨다.

마지막으로, 수축된 그래프(B22)에 증강 경로 P p을 위치시키고, 이를 원래의 그래프(B23)로 들어 올린다.여기서 꽃들을 수축시키는 알고리즘의 능력은 매우 중요하다; 알고리즘은 원래 그래프에서 P를 직접 찾을 수 없다. 왜냐하면 뿌리에서 고른 거리에 있는 꼭지점 사이의 숲 밖의 가장자리만 알고리즘의 B17 선에서 고려되기 때문이다.

분석

find_augmenting_path() 함수에 의해 구성된 f숲은 교대숲이다.^[9]

• G의 T나무는 M에 관한 교대나무다.
  • T에는 트리 루트라고 하는 노출된 꼭지점 r이 정확히 하나 포함되어 있다.
  • 뿌리로부터 홀수 거리에 있는 모든 꼭지점에는 정확히 두 개의 입사 가장자리가 있으며,
  • t의 r에서 잎까지의 모든 경로는 짝수 길이를 가지며, 홀수 가장자리는 M에 있지 않고 짝수 가장자리는 M에 있다.
• G의 숲 F는 M에 관한 교대림이다.
  • 그것의 연결된 구성 요소들은 교대하는 나무들이다.
  • G의 모든 노출된 꼭지점은 F의 교대 나무의 뿌리다.

Line B09에서 시작하는 루프의 각 반복은 F(Line B10)의 T 트리에 추가되거나 증가 경로(Line B17)를 찾거나 꽃(Line B20)을 찾는다.실행 시간이 $O{\displaystyle (E}$ ${\displaystyle V}$ ${\displaystyle {}^{\mathrm{}}}$) ${\displaystyle O(E$V$^{2})}$인 것을 쉽게 알 수 있다$.$

초당적 매칭

G가 초당적일 때 G에는 홀수 사이클이 없다.이 경우 꽃은 절대 발견되지 않으며 알고리즘의 B20~B24 라인을 간단히 제거할 수 있다.따라서 알고리즘은 초당적^[7] 그래프에서 최대 카디널리티 일치를 구성하기 위한 표준 알고리즘으로 축소된다. 여기서 간단한 그래프 통과로 증분 경로를 반복적으로 검색한다. 예를 들어 Ford-Fulkerson 알고리즘의 경우다.

가중 일치

일치 문제는 G의 가장자리에 가중치를 할당하고 최대(최소) 총 중량의 일치를 생성하는 세트 M을 요청함으로써 일반화할 수 있다: 이것이 최대 중량 일치 문제다.이 문제는 가중되지 않은 에드몬드의 알고리즘을 서브루틴으로 사용하는 결합 알고리즘으로 해결할 수 있다.^[6]콜모고로프는 이것의 효율적인 C++ 구현을 제공한다.^[10]

참조