Blomkompressionsalgoritm

Blossom-algoritmen är en algoritm inom grafteorin för att konstruera de största matchningarna på grafer . Algoritmen utvecklades av Jack Edmonds 1961 [1] och publicerades 1965 [2] . Givet en allmän graf G =( V , E ), hittar algoritmen en matchande M så att varje vertex i V faller mot högst en kant i M och | M | maximal. En matchning konstrueras genom att iterativt förbättra den initiala tomma matchningen längs förstärkande grafbanor. I motsats till tvådelad matchning var den viktigaste nya idén att komprimera en udda cykel i en graf (blomma) till en enda vertex och fortsätta sökningen iterativt över den komprimerade grafen.

Den främsta anledningen till att blomkompressionsalgoritmen är viktig är att den gav det första beviset på att det var möjligt att hitta den största matchningen i polynomtid. En annan anledning är att metoden leder till beskrivningen av en linjär programmeringspolytop för en matchande polytop , vilket leder till en minsta viktmatchningsalgoritm [3] . Som Alexander Schreiver klargjorde , den ytterligare betydelsen av resultatet följer av det faktum att denna polytop var den första vars integrerade bevis "inte bara följde av total unimodularitet , utan dess beskrivning var ett genombrott i polyedrarnas kombinatorik " [4] .

Öka sökvägar

Givet en graf G =( V , E ) och en matchande M för G , är en vertex v blottad (inte täckt av matchningen) om det inte finns någon kant i M som faller samman med v . En bana i G är en växelvis bana om dess kanter växelvis inte tillhör M och ingår i M. Den förstärkande banan P är en alternerande kedja som börjar och slutar med kala hörn. Observera att antalet omatchade hörn i förstärkningsbanan är större med en än antalet kanter i matchningen, och därför är antalet kanter i förstärkningsbanan udda. Att öka matchningarna längs vägen P är operationen att ersätta uppsättningen M med en ny matchning . $M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)$

Enligt Berges lemma är en matchande M maximal om och endast om det inte finns någon M -förstärkande väg i G [5] [6] . Därför är antingen matchningen störst, eller så kan den ökas. Alltså, med början med viss matchning, kan vi beräkna den största matchningen genom att öka den aktuella matchningen med den utökade sökvägen. Algoritmen kan formaliseras enligt följande

INPUT: Graf G , initial matchning M på G OUTPUT: största matchande M* på G A1 - funktionen find_largest_matching ( G , M ) : M* A2 find_increasing_path ( G , M )

P\leftarrow

A3 om P inte är tomt returnerar A4 find_greatest_match ( G , öka M längs P ) A5 annars A6 retur M A7 slut om A8 slutfunktion

Vi behöver beskriva hur förstärkningsvägar kan konstrueras effektivt. Deras sökrutin använder blommor och sammandragning.

Blommor och förträngning

Givet en graf G =( V , E ) och en matchande M av en graf G , då är blomman B en cykel i G som består av 2k + 1 kanter varav exakt k tillhör M och har en vertex v ( bas ) såsom att det finns en omväxlande kedja av jämn längd ( stam ) från v till en bar vertex w .

Hitta blommor:

Vi tittar igenom grafen, med början från den kala toppen;
Utgående från denna vertex markerar vi den som den yttre " o " ;
Märk växelvis topparna som 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 " , har vi en udda längdcykel, och därmed en blomma [7] .

Vi definierar en komprimerad graf G' som den graf som erhålls från G genom att dra ihop alla kanter på blomman B , och vi definierar en komprimerad matchande M' som matchningen av grafen G' som motsvarar M .

G' har en M' -ökande bana om och bara om G har en M -ökande bana, och då kan vilken M' -ökande bana P' i G' som helst höjas till en M -ökande bana i G genom att återställa blomman B kontrakterade tidigare, så att segmentet av banan P' (om någon) som går genom v B ersätts av ett lämpligt segment som passerar genom B [8] . I mer detalj:

Om P' passerar genom ett segment i G' så ersätts detta segment med ett segment i G , där blomma hörn u' och w' och sidan av blomman B , från u' till w' väljs så att ny väg förblir alternerande ( u ' naken i förhållande till , ). $u\to v_{B}\to w$ $u\to (u'\to \dots \to w')\to w$ $(u'\to \dots \to w')$ $M\cap B$ $\{w',w\}\in E\setminus M$

Om P' har en destination v B , så ersätts banasegmentet i G' med ett banasegment i G , där blomkanterna u' och v' och sidan av blomman B , från u' till v' , är vald så att vägen är alternerande ( v' naken, ). $u\to v_{B}$ $u\to (u'\to \dots \to v')$ $(u'\to \dots \to v')$ $\{u',u\}\in E\setminus M$

Sedan kan blomman komprimeras och sökningen kan fortsätta över de komprimerade graferna. Denna komprimering är hjärtat i Edmonds algoritm.

Hitta en utökad sökväg

Ökad sökväg använder en ytterligare datastruktur, som är en skog F , vars individuella träd motsvarar delar av grafen G . Faktum är att skogen F är densamma som används för att hitta de största matchningarna i tvådelade grafer (utan att blommor behöver dras ihop). Vid varje iteration hittar algoritmen antingen (1) en förstärkningsbana, eller (2) hittar en blomma och återkommer till en komprimerad graf, eller (3) drar slutsatsen att det inte finns någon förstärkningsbana. Den extra strukturen byggs med hjälp av en inkrementell procedur, som diskuteras nedan [8] .

Konstruktionsproceduren tittar på hörnen v och kanterna e på grafen G och uppdaterar F stegvis i enlighet därmed. Om v finns i ett skogsträd T använder vi rot(v) för att beteckna roten till T . Om både u och v ligger i samma träd T i F anger vi med avstånd(u, v) längden på den enda vägen från u till v i träd T .

INPUT: Graf G , matchande M till G OUTPUT: Öka sökväg P till G eller tom sökväg om ingen sådan sökväg hittas B01 funktion find_increment_path ( G , M ): P B02 tom skog

F\leftarrow

B03 gör alla hörn och kanter omärkta i G , märk alla kanter M B05 för varje kal vertex v gör B06 skapa träd från en vertex { v } och lägg till träd till F B07- änden för B08 medan det finns omärkt vertex v i F med jämnt avstånd ( v, root(v)) gör B09 medan det finns en omärkt kant e ={ v , w } gör B10 om w inte är i F då // w är i matchningen, så lägg till kanten // som täcker e och w i F B11 matchas med vertex w i M B12 lägg till kanter { v , w } och { w , x } till trädet för v B13 annars B14 om avstånd (w, root( w )) är konstigt då

x\leftarrow

// göra ingenting. B15 annars B16 om root(v) ≠ root(w) så // Rapportera förstärkningsvägen i F .

{\displaystyle \cup \{e\))

B17 sätt ( )

P\leftarrow

root(v)\to \dots \to v)\to (w\to \dots \to root(w)

B18 returnera P B19 annat // Dra ihop blomman till G och leta efter en bana i den komprimerade grafen. B20 blomman som bildas av e och kanterna på banan i T B21 krymper G och M genom att krympa blomman B B22 find_increasing_path B23 höj P' till G B24 retur P B25 slut om B26 slut om B27 slut om B28 markera kant e B29 slut medan B30 markerar vertex v B31 slut medan B32 returnerar tom bana

B\leftarrow

v\to w

G',M'\leftarrow

P'\leftarrow

(G',M')

P\leftarrow

B33 slutfunktion

Exempel

De följande fyra figurerna illustrerar utförandet av algoritmen. De streckade linjerna visar kanter som för närvarande inte finns i skogen. Först bearbetar algoritmen en kant som inte tillhör skogen, vilket leder till expansion av den nuvarande skogen (linjerna B10 - B12).

Därefter tas blomman bort och grafen komprimeras (linjerna B20 - B21).

Slutligen hittar algoritmen en förstärkningsväg P′ i den komprimerade grafen (linje B22) och lyfter den i den ursprungliga grafen (linje B23). Observera att förmågan hos blomkontraktionsalgoritmen är avgörande här. Algoritmen kan inte hitta P i den ursprungliga grafen direkt, eftersom endast icke-skogskanter mellan hörn på ett jämnt avstånd från roten beaktas i linje B17 i algoritmen.

Analys

Skogen F konstruerad av find_increasing_path() är en randig skog [9] .

ett träd T i G är ett alternerande träd med avseende på M if
- T innehåller exakt en kal vertex r , som kallas trädets rot
- vilken vertex som helst på ett udda avstånd från roten har exakt två infallande kanter i T , och
- alla vägar från r till blad i T har jämna längder, deras udda kanter tillhör inte M , men deras jämna kanter tillhör M.
en skog F i G är en randig skog med avseende på M if
- dess anslutna komponenter är alternerande träd och
- vilken bar vertex som helst i G är en rot i ett alternerande träd i F .

Varje iteration av slingan, med start från linje B09, lägger antingen till en nod till trädet T i F (linje B10), hittar en förstärkningsbana (linje B17) eller hittar en blomma (linje B20). Det är lätt att se att körtiden för algoritmen är . Micali och Vazirani [10] visade en algoritm som bygger den största matchningen i tid . $O(|E||V|^{2})$ $O(|E||V|^{1/2})$

Tvådelad matchning

Algoritmen reduceras till standardalgoritmen för matchning i tvådelade grafer [6] om G är tvådelad . Eftersom det inte finns några udda cykler i G i det här fallet kommer blommorna aldrig att hittas, och du kan helt enkelt ta bort raderna B20 - B24 i algoritmen.

Viktad matchning

Matchningsproblemet kan generaliseras genom att tilldela vikter till kanterna på grafen G . I det här fallet ställs frågan om uppsättningen M , som ger en matchning med den maximala (minsta) totalvikten. Det viktade matchningsproblemet kan lösas med en kombinatorisk algoritm som använder den oviktade Edmonds-algoritmen som en subrutin [5] . Vladimir Kolmogorov gav en effektiv implementering av denna algoritm i C++ [11] .

Anteckningar

↑ Edmonds, 1961 , s. 32-54.
↑ Edmonds, 1965 , s. 449-467.
↑ Edmonds, 1965 , s. 125-130.
↑ Schrijver, 2003 .
↑ 1 2 Lovász, Plummer, 1986 .
↑ 12 Karp , 2006 .
↑ Genom konstruktion markerar " i " början av en kant från M , så att fallet med mötet av två angränsande hörn märkta " i " är omöjligt.
↑ 12 Tarjan , 2002 .
↑ Kenyon, Lovász, 1990 .
↑ Micali, Vazirani, 1980 , s. 17-27.
↑ Kolmogorov, 2009 , s. 43-67.

Litteratur

Alexander Schrijver. Kombinatorisk optimering: polyedrar och effektivitet . - Berlin, Heidelberg: Springer-Verlag, 2003. - (Algorithms and Combinatorics). — ISBN 9783540443896 .
Jack Edmonds. En glimt av himlen // History of Mathematical Programming - A Collection of Personal Reminiscences / JK Lenstra, AHG Rinnooy Kan, A. Schrijver. - CWI, Amsterdam och Nord-Holland, Amsterdam, 1961. - s. 32-54.
Jack Edmonds. Stigar, träd och blommor // Can. J. Math .. - 1965. - T. 17 . — S. 449–467 . - doi : 10.4153/CJM-1965-045-4 .
Jack Edmonds. Maximal matchning och en polyeder med 0,1-hörn // Journal of Research of the National Bureau of Standards Section B. - 1965. - T. 69 . — S. 125–130 .
László Lovász, Michael D. Plummer. Matchande teori. - Akademiai Kiado, 1986. - ISBN 963-05-4168-8 .
Richard Karp. kursanteckningar. UC Berkeley . - 2006. Arkiverad den 30 december 2008.
Robert. Skissartade anteckningar om Edmonds' Incredible Shrinking Blossom Algorithm for General Matching // Course Notes-423: Theory of Algorithms . — Institutionen för datavetenskap, Princeton University, 2002.
Claire Kenyon, László Lovász. Algoritmisk diskret matematik // Teknisk rapport CS-TR-251-90, Institutionen för datavetenskap, Princeton University. — 1990.
Blossom V: En ny implementering av en lägsta kostnad perfekt matchningsalgoritm // Mathematical Programming Computation. - 2009. - T. 1 , nr 1 . — s. 43–67 .
Silvio Micali, Vijay Vazirani. En O(V 1/2 E) algoritm för att hitta maximal matchning i allmänna grafer // 21st Annual Symposium on Foundations of Computer Science,. - IEEE Computer Society Press, New York, 1980. - S. 17-27.