Blossom algoritm

I grafteorin är blossom-algoritmen en algoritm för att konstruera maximala matchningar på grafer . Algoritmen utvecklades av Jack Edmonds 1961 och publicerades 1965. Givet en allmän graf $G = (V, E)$ hittar algoritmen en matchande $M$ så att varje vertex i $V$ infaller med högst en kant i $M$ och $| M |$ är maximerad. Matchningen är konstruerad genom att iterativt förbättra en initial tom matchning längs förstärkande banor i grafen. Till skillnad från tvådelad matchning är den viktigaste nya idén att en cykel med udda längd i grafen (blomningen) dras samman till en enda vertex, med sökningen som fortsätter iterativt i den sammandragna grafen.

Algoritmen körs i tiden $O (| E || V | 2)$ , där $| E |$ är antalet kanter på grafen och $| V |$ är dess antal hörn . En bättre körtid för $O(|E|{\sqrt {|V|}})$ för samma uppgift kan uppnås med den mycket mer komplexa algoritmen för Micali och Vazirani .

En viktig anledning till att blossom-algoritmen är viktig är att den gav det första beviset på att en maximal storleksmatchning kunde hittas med en polynommängd beräkningstid. Ett annat skäl är att det ledde till en linjär programmeringspolyedrisk beskrivning av den matchande polytopen , vilket ger en algoritm för minviktsmatchning . Som utvecklats av Alexander Schrijver , kommer ytterligare betydelse av resultatet från det faktum att detta var den första polytopen vars bevis på integralitet "inte helt enkelt följer av total unimodularitet , och dess beskrivning var ett genombrott inom polyedrisk kombinatorik ."

Öka vägar

Givet $G = (V, E)$ och en matchande M av G, exponeras $en$ vertex $v$ om ingen $kant$ av $M$ faller in mot $v$ . En bana i $G$ är en alternerande bana , om dess kanter växelvis inte är i $M$ och i $M$ (eller i $M$ och inte i $M$ ). En förstärkningsbana $P$ är en alternerande väg som börjar och slutar vid två distinkta exponerade hörn. Observera att antalet omatchade kanter i en förstärkningsbana är en större än antalet matchade kanter, och därför är det totala antalet kanter i en förstärkningsbana udda. En matchande förstärkning längs en förstärkningsbana $P$ är operationen att ersätta $M$ med en ny matchning

M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)

.

Enligt Berges lemma är matchande $M$ maximalt om och endast om det inte finns någon $M$ -förstärkningsväg i $G$ . Därför är antingen en matchning maximal, eller så kan den utökas. Alltså, med utgångspunkt från en initial matchning, kan vi beräkna en maximal matchning genom att utöka den aktuella matchningen med utökade sökvägar så länge vi kan hitta dem, och återvända närhelst inga utökade vägar finns kvar. Vi kan formalisera algoritmen enligt följande:

    INPUT: Graf  G  , initial matchning  M  på  G  OUTPUT: maximal matchning  M*  på  G  A1  -funktion  find_maximum_matching  (  G  ,  M  ):  M*  A2  P  ←  find_augmenting_path  (  G  ,  M  ) A3  om  P  är icke-tom  så  returnerar  A4  find_maximum_matching  (  G  , utöka  M  längs  P  ) A5  annars  A6  returnera  M A7  slut om  A8  slutfunktion

Vi måste fortfarande beskriva hur utökade vägar kan hittas effektivt. Subrutinen för att hitta dem använder blommor och sammandragningar.

Blomningar och sammandragningar

Givet $G = (V, E)$ och en matchande $M$ av $G$ , är en blomma $B$ en cykel i $G$ som består av $2 k + 1$ kanter varav exakt $k$ tillhör $M$ , och där en av hörnen $v$ i cykeln (den bas ) är sådan att det finns en omväxlande bana med jämn längd ( stammen ) från $v$ till en exponerad vertex $w$ .

Hitta blommor:

Traversera grafen med början från en exponerad vertex.
Utgå från det hörnet och märk det som ett yttre hörn $o$ .
Alternera märkningen mellan hörn som är inre $i$ och yttre $o$ så att inga två närliggande hörn har samma etikett.
Om vi slutar med två angränsande hörn märkta som yttre $o$ så har vi en udda längd cykel och därmed en blomning.

Definiera den sammandragna grafen $G'$ som den graf som erhålls från $G$ genom att kontrahera varje kant av B $,$ och definiera den sammandragna matchningen $M'$ som matchningen av $G'$ som motsvarar $M.$

$G'$ har en $M'$ -förstärkningsbana om och endast om $G$ har en $M$ -förstärkningsbana, och att vilken $M'$ -förstärkningsbana $P'$ i $G' som helst$ kan lyftas till en $M$ -förstärkningsbana i $G$ genom att ångra sammandragningen med $B$ så att segmentet av $P'$ (om någon) som går genom $v B$ ersätts med ett lämpligt segment som går genom $B$ . I mer detalj:

om $P'$ korsar ett segment $u \to v B \to w$ i $G'$ , då ersätts detta segment med segmentet $u \to (u' \to \dots \to w') \to w$ i $G$ , där blompunkten $u'$ och $w'$ och sidan av $B$ , $(u' \to \dots \to w')$ , som går från $u'$ till $w'$ väljs för att säkerställa att den nya vägen fortfarande är alternerande ( $u'$ är exponerad med avseende på $M\cap B$ , ${\displaystyle \{w',w\}\in E\setminus M} )$ .

om $P'$ har en ändpunkt $v B$ , då ersätts vägsegmentet $u \to v B$ i $G'$ med segmentet $u \to (u' \to \dots \to v')$ i $G$ , där blompunkten $u'$ och $v'$ och sidan av $B$ , $(u' \to \dots \to v')$ , som går från $u'$ till $v'$ väljs för att säkerställa att banan är alternerande ( $v'$ är exponerad, $\{ u',u\}\in E\setminus M$ ).

Således kan blommor dras ihop och sökning utföras i de sammandragna graferna. Denna minskning är kärnan i Edmonds algoritm.

Att hitta en förstärkningsväg

Sökningen efter en förstärkningsväg använder en extra datastruktur som består av en skog $F$ vars individuella träd motsvarar specifika delar av grafen $G$ . Faktum är att skogen $F$ är densamma som skulle användas för att hitta maximala matchningar i tvådelade grafer (utan behov av krympande blommor). I varje iteration hittar algoritmen antingen (1) en förstärkningsväg, (2) hittar en blomning och återkommer till den motsvarande sammandragna grafen, eller (3) drar slutsatsen att det inte finns några förstärkningsvägar. Hjälpstrukturen byggs genom en inkrementell procedur som diskuteras härnäst.

Konstruktionsproceduren beaktar hörn $v$ och kanter $e$ i $G$ och uppdaterar $F stegvis$ efter behov. Om $v$ finns i ett träd $T$ i skogen låter vi rot(v) beteckna roten till $T$ . Om både $u$ och $v$ är i samma träd $T$ i $F$ låter vi distans(u,v) beteckna längden på den unika vägen från $u$ till $v$ i $T$ .

          INPUT: Graph  G  , matching  M  on  G  OUTPUT: augmenting bana  P  i  G  eller tom bana om ingen hittas B01  funktion  find_augmenting_path  (  G  ,  M  ):  P  B02  F  ← tom skog B03 avmarkera alla hörn och kanter i  G  , markera alla kanter på  M  B05  för varje  exponerad vertex  v  gör  B06 skapa ett singelträd {  v  } och lägg till trädet till  F  B07  -änden för  B08  medan  det finns en omarkerad vertex  v  i  F  med  avstånd(v, rot(v))  även  gör  B09  medan  det finns finns en omarkerad kant  e  = {  v  ,  w  }  gör  B10  om  w  inte är i  F  då  //  w  matchas, så lägg till  e  och  ws  matchade kant till  F  B11  x  ← vertex matchad till  w  i  M  B12 add edges {  v  ,  w  } och {  w  ,  x  } till trädet i  v  B13  annars  B14  om  avstånd(w, rot(w))  är udda  då  // Gör ingenting. B15   annars  B16  om  root(v)  ≠  root(w)  then  // Rapportera en utökad sökväg i F  $\cup$  {  e  }. B17   P  ← banan (  rot  (  v  ) → ... →  v  ) → (  w  → ... →  rot  (  w  )) B18  return  P  B19  else  // Dra ihop en blomma i  G  och leta efter banan i den sammandragna grafen . B20   B  ← blomning bildad av  e  och kanter på banan  v  →  w  i  T  B21  G', M'  ← kontrakt  G  och  M  av  B  B22  P'  ←  find_augmenting_path  (  G'  ,  M'  ) B23  P  ← lyft  P'  till  G  B24  retur  P  B25  slut om  B26  slut om  B27  slut om  B28 markerar kant  e  B29  slut medan  B30 markerar vertex  v  B31  slut medan  B32  returnerar  tom sökväg B33  slutfunktion

Exempel

Följande fyra figurer illustrerar exekveringen av algoritmen. Streckade linjer indikerar kanter som för närvarande inte finns i skogen. Först bearbetar algoritmen en kant utanför skogen som orsakar expansionen av den nuvarande skogen (linjerna B10 – B12).

Därefter upptäcker den en blomning och drar ihop grafen (linjerna B20 – B21).

Slutligen lokaliserar den en förstärkningsbana $P'$ i den sammandragna grafen (linje B22) och lyfter den till den ursprungliga grafen (linje B23). Observera att algoritmens förmåga att dra ihop blommor är avgörande här; Algoritmen kan inte hitta $P$ i den ursprungliga grafen direkt eftersom endast ut-ur-skogskanter mellan hörn på jämna avstånd från rötterna betraktas på linje B17 i algoritmen.

Analys

Skogen $F$ som konstrueras av funktionen find_augmenting_path() är en alternerande skog.

ett träd T i G är ett alternerande träd med avseende på M , if
- $T$ innehåller exakt en exponerad vertex $r$ som kallas trädroten
- varje vertex på ett udda avstånd från roten har exakt två infallande kanter i $T$ , och
- alla banor från $r$ till blad i $T$ har jämna längder, deras udda kanter är inte i $M$ och deras jämna kanter är i $M$ .
en skog F i G är en alternerande skog med avseende på M , if
- dess anslutna komponenter är alternerande träd, och
- varje exponerad vertex i $G$ är en rot av ett alternerande träd i $F$ .

Varje iteration av slingan som börjar på linje B09 läggs antingen till ett träd $T$ i $F$ (linje B10) eller hittar en förstärkningsbana (linje B17) eller hittar en blomning (linje B20). Det är lätt att se att körtiden är $O(|E||V|^{2})$ .

Tvådelad matchning

När $G$ är tvådelad finns det inga udda cykler i $G.$ I så fall kommer blommor aldrig att hittas och man kan helt enkelt ta bort raderna B20 – B24 i algoritmen. Algoritmen reduceras alltså till standardalgoritmen för att konstruera maximala kardinalitetsmatchningar i tvådelade grafer där vi upprepade gånger söker efter en förstärkningsväg genom en enkel graftraversering: detta är till exempel fallet med Ford–Fulkerson- algoritmen .

Viktad matchning

Matchningsproblemet kan generaliseras genom att tilldela vikter till kanter i $G$ och be om en uppsättning $M$ som ger en matchning av maximal (minsta) totalvikt: detta är det maximala viktmatchningsproblemet . Detta problem kan lösas med en kombinatorisk algoritm som använder den oviktade Edmonds algoritm som en subrutin. Kolmogorov tillhandahåller en effektiv C++-implementering av detta.

^ Edmonds, Jack (1991), "En glimt av himlen", i JK Lenstra; AHG Rinnooy Kan; A. Schrijver (red.), History of Mathematical Programming --- A Collection of Personal Reminiscences , CWI, Amsterdam och North-Holland, Amsterdam, s. 32–54
^ Edmonds, Jack (1965). "Stigar, träd och blommor". Burk. J. Math . 17 : 449–467. doi : 10.4153/CJM-1965-045-4 .
^ Micali, Silvio; Vazirani, Vijay (1980). En O(V ^1/2 E) algoritm för att hitta maximal matchning i allmänna grafer . 21:a årliga symposiet om grunderna för datavetenskap. IEEE Computer Society Press, New York. s. 17–27.
^ Edmonds, Jack (1965). "Maximal matchning och en polyeder med 0,1-hörn" . Journal of Research för National Bureau of Standards Sektion B . 69 : 125–130. doi : 10.6028/jres.069B.013 .
^ Schrijver, Alexander (2003). Kombinatorisk optimering: polyedrar och effektivitet . Algoritmer och kombinatorik. Berlin Heidelberg: Springer-Verlag. ISBN 9783540443896 .
^ ^a ^b Lovász, László ; Plummer, Michael (1986). Matchningsteori . Akadémiai Kiadó. ISBN 963-05-4168-8 .
^ ^a ^b Karp, Richard, "Edmonds's Non-Bipartite Matching Algorithm", kursanteckningar. UC Berkeley (PDF) , arkiverad från originalet (PDF) 2008-12-30
^ ^a ^b Tarjan, Robert, "Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching", Kursanteckningar, Institutionen för datavetenskap, Princeton University (PDF)
^ Kenyon, Claire; Lovász, László , "Algorithmic Discrete Mathematics", teknisk rapport CS-TR-251-90, Institutionen för datavetenskap, Princeton University
^ Kolmogorov, Vladimir (2009), "Blossom V: En ny implementering av en lägsta kostnad perfekt matchningsalgoritm" , Mathematical Programming Computation , 1 (1): 43–67, doi : 10.1007/s12532-009-0002-8

[glimpse-1] Edmonds, Jack (1991), "En glimt av himlen", i JK Lenstra; AHG Rinnooy Kan; A. Schrijver (red.), History of Mathematical Programming --- A Collection of Personal Reminiscences , CWI, Amsterdam och North-Holland, Amsterdam, s. 32–54

[algorithm-2] Edmonds, Jack (1965). "Stigar, träd och blommor". Burk. J. Math . 17 : 449–467. doi : 10.4153/CJM-1965-045-4 .

[micali-3] Micali, Silvio; Vazirani, Vijay (1980). En O(V ^1/2 E) algoritm för att hitta maximal matchning i allmänna grafer . 21:a årliga symposiet om grunderna för datavetenskap. IEEE Computer Society Press, New York. s. 17–27.

[weighted-4] Edmonds, Jack (1965). "Maximal matchning och en polyeder med 0,1-hörn" . Journal of Research för National Bureau of Standards Sektion B . 69 : 125–130. doi : 10.6028/jres.069B.013 .

[5] Schrijver, Alexander (2003). Kombinatorisk optimering: polyedrar och effektivitet . Algoritmer och kombinatorik. Berlin Heidelberg: Springer-Verlag. ISBN 9783540443896 .

[matching_book-6] Lovász, László ; Plummer, Michael (1986). Matchningsteori . Akadémiai Kiadó. ISBN 963-05-4168-8 .

[karp_notes-7] Karp, Richard, "Edmonds's Non-Bipartite Matching Algorithm", kursanteckningar. UC Berkeley (PDF) , arkiverad från originalet (PDF) 2008-12-30

[tarjan_notes-8] Tarjan, Robert, "Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching", Kursanteckningar, Institutionen för datavetenskap, Princeton University (PDF)

[kenyon_report-9] Kenyon, Claire; Lovász, László , "Algorithmic Discrete Mathematics", teknisk rapport CS-TR-251-90, Institutionen för datavetenskap, Princeton University

[blossom5-10] Kolmogorov, Vladimir (2009), "Blossom V: En ny implementering av en lägsta kostnad perfekt matchningsalgoritm" , Mathematical Programming Computation , 1 (1): 43–67, doi : 10.1007/s12532-009-0002-8