Lexikografisk bredd-först sökning

Inom datavetenskap är lexikografisk bredd-först-sökning eller Lex-BFS en linjär tidsalgoritm för att sortera hörn på en graf . Algoritmen skiljer sig från en bredd-först-sökning , men den ger en ordning som överensstämmer med bredd-först-sökning.

Den lexikografiska bredd-första sökalgoritmen är baserad på idén om partitionsförfining och utvecklades först av Donald J. Rose, Robert E. Tarjan och George S. Lueker ( 1976 ). En mer detaljerad översikt av ämnet presenteras av Corneil (2004) . Den har använts som en subrutin i andra grafalgoritmer inklusive igenkänning av ackordsgrafer och optimal färgning av ärftliga distansgrafer .

Bakgrund

Den bredd-första sökalgoritmen definieras vanligtvis av följande process:

• Initiera en kö av grafens hörn, med grafens startpunkt som köns enda element.
• Medan kön inte är tom, ta bort (avkö) en vertex v från kön och lägg till i kön (enqueue) alla andra hörn som kan nås av en kant från v som inte redan har lagts till i tidigare steg.

Istället för att definiera den vertex som ska väljas vid varje steg på ett imperativt sätt som den som produceras av en kös avköningsoperation, kan man definiera samma sekvens av hörn deklarativt genom egenskaperna hos dessa hörn. Det vill säga, en vanlig bredd-först-sökning är bara resultatet av att upprepade gånger tillämpa denna regel:

• Mata ut en vertex v upprepade gånger , välj vid varje steg en vertex v som inte redan har valts och som har en föregångare (en vertex som har en kant till v ) så tidigt i utgången som möjligt.

I vissa fall kan denna ordning av hörn efter utgångspositionerna för deras föregångare ha kopplingar - två olika hörn har samma tidigaste föregångare. I detta fall kan ordningen i vilken dessa två hörn väljs vara godtycklig. Resultatet av lexikografisk bredd-först-sökning skiljer sig från en vanlig bredd-först-sökning genom att ha en konsekvent regel för att bryta sådana band. I lexikografisk bredd-först-sökning är utdataordningen den ordning som skulle produceras av regeln:

• Mata ut en vertex v upprepade gånger , välj vid varje steg en vertex v som inte redan har valts och vars hela uppsättning av redan utmatade föregångare är så liten som möjligt i lexikografisk ordning .

Så när två hörn v och w har samma tidigaste föregångare, tidigare än alla andra ovalda hörn, kommer standardsökningsalgoritmen för bredd-först att ordna dem godtyckligt. I stället, i det här fallet, skulle LexBFS-algoritmen välja mellan v och w genom utgångsordningen för deras näst tidigaste föregångare. Om bara en av dem har en näst tidigaste föregångare som redan har matats ut, väljs den. Om både v och w har samma näst tidigaste föregångare, så bryts bandet genom att ta hänsyn till deras tredje tidigaste föregångare, och så vidare.

Att tillämpa denna regel direkt genom att jämföra hörn enligt denna regel skulle leda till en ineffektiv algoritm. Istället använder den lexikografiska bredd-först-sökningen en uppsättning partitioneringsdatastruktur för att producera samma ordning mer effektivt, precis som en standard bredd-först-sökning använder en ködatastruktur för att producera sin ordning på ett effektivt sätt.

Algoritm

Den lexikografiska bredd-först-sökningsalgoritmen ersätter kön av hörn i en standard bredd-först-sökning med en ordnad sekvens av uppsättningar av hörn. Uppsättningarna i sekvensen bildar en partition av de återstående hörnen. Vid varje steg tas en vertex v från den första mängden i sekvensen bort från den mängden, och om den borttagningen gör att mängden blir tom så tas mängden bort från sekvensen. Sedan ersätts varje uppsättning i sekvensen av två delmängder: grannarna till v och icke-grannarna till v . Delmängden av grannar placeras tidigare i sekvensen än delmängden av icke-grannar. I pseudokod kan algoritmen uttryckas på följande sätt:

• Initiera en sekvens Σ av mängder för att innehålla en enda uppsättning som innehåller alla hörn.
• Initiera utgångssekvensen av hörn så att den är tom.
• Medan Σ är icke-tom:
  • Hitta och ta bort en vertex v från den första mängden i Σ
  • Om den första uppsättningen i Σ nu är tom, ta bort den från Σ
  • Lägg till v i slutet av utdatasekvensen.
  • För varje kant vw så att w fortfarande tillhör en mängd S i Σ:
    • Om uppsättningen S som innehåller w ännu inte har ersatts under bearbetning av v , skapa en ny tom ersättningsuppsättning T och placera den före S i sekvensen; låt annars T vara mängden före S .
    • Flytta w från S till T , och om detta gör att S blir tomt, ta bort S från Σ.

Varje vertex bearbetas en gång, varje kant undersöks endast när dess två ändpunkter bearbetas, och (med en lämplig representation för mängderna i Σ som gör att objekt kan flyttas från en uppsättning till en annan i konstant tid) varje iteration av den inre slingan tar bara konstant tid. Därför, precis som enklare grafsökningsalgoritmer som bredd-först-sökning och djup-först-sökning , tar denna algoritm linjär tid.

Algoritmen kallas lexikografisk bredd-först-sökning eftersom ordningen den producerar är en ordning som också kunde ha producerats av en bredd-först-sökning, och eftersom om ordningen används för att indexera raderna och kolumnerna i en närliggande matris i en graf sedan sorterar algoritmen raderna och kolumnerna i lexikografisk ordning .

Ansökningar

Ackordsgrafer

En graf G definieras som ackordal om dess hörn har en perfekt elimineringsordning , en ordning sådan att grannarna som förekommer senare i ordningen bildar en klick för varje vertex v . I en ackordsgraf är det omvända av en lexikografisk ordning alltid en perfekt elimineringsordning. Därför kan man testa om en graf är ackordal i linjär tid med följande algoritm:

• Använd lexikografisk bredd-först-sökning för att hitta en lexikografisk ordning av G
• För varje vertex v :
  • Låt w vara granne till v som förekommer före v , så nära v i sekvensen som möjligt
    • (Fortsätt till nästa vertex v om det inte finns något sådant w )
  • Om mängden tidigare grannar till v (exklusive w själv) inte är en delmängd av mängden tidigare grannar till w , är grafen inte ackordal
• Om slingan avslutas utan att visa att grafen inte är ackordal, så är den ackordal.

Denna applikation var den ursprungliga motivationen som ledde till att Rose, Tarjan & Lueker (1976) utvecklade den första sökalgoritmen med lexikografisk bredd.

Graffärgning

En graf G sägs vara perfekt ordningsbar om det finns en sekvens av dess hörn med egenskapen att, för varje inducerad subgraf av G , en girig färgalgoritm som färgar hörnen i den inducerade sekvensordningen garanteras att producera en optimal färgning.

För en ackordsgraf är en perfekt elimineringsordning en perfekt ordning: numret på färgen som används för varje vertex är storleken på den klick som bildas av den och dess tidigare grannar, så det maximala antalet färger som används är lika med storleken på den största klicken i grafen, och ingen färgning kan använda färre färger. En inducerad subgraf av en ackordsgraf är ackordal och den inducerade undersekvensen av dess perfekta elimineringsordning är en perfekt elimineringsordning på subgrafen, så ackordsgrafer är perfekt beställningsbara, och lexikografisk bredd-först-sökning kan användas för att färglägga dem optimalt.

Samma egenskap gäller för en större klass av grafer, de ärftliga avståndsgraferna : avståndsärftliga grafer är perfekt beställningsbara, med en perfekt ordning som ges av omvänd ordning av en lexikografisk ordning, så lexikografisk bredd-först-sökning kan användas i kombination med giriga färgalgoritmer för att färga dem optimalt i linjär tid.

Andra applikationer

Bretscher et al. (2008) beskriver en utökning av lexikografisk bredd-först-sökning som bryter eventuella ytterligare band med hjälp av komplementgrafen för indatagrafen. Som de visar kan detta användas för att känna igen kografer i linjär tid. Habib et al. (2000) beskriver ytterligare tillämpningar av lexikografisk bredd-först-sökning inklusive igenkänning av jämförbarhetsgrafer och intervallgrafer .

LexBFS beställning

En uppräkning av toppen av en graf sägs vara en LexBFS-ordning om det är den möjliga utmatningen av tillämpningen av LexBFS på denna graf.

Låt $G=(V,E)$ vara en graf med $n$ hörn. Kom ihåg att $N(v)$ är uppsättningen av grannar till $v$ . Låt $\sigma =(v_{1},\dots ,v_{n})$ vara en uppräkning av hörnen till $V$ . Uppräkningen $\sigma$ är en LexBFS-ordning (med källa $v_{1}$ ) om, för alla $1\leq i<j< k\leq n$ med ${\displaystyle v_{i}\in N(v_{k})\setminus N(v_{j})} ,$ det finns $m<i$ så att $v_{m}\in N(v_{j})\setminus N(v_{k})$ .

Anteckningar

•   Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X .
•   Bretscher, Anna; Corneil, Derek ; Habib, Michel; Paul, Christophe (2008), "A simple linear time LexBFS cograph recognition algorithm" , SIAM Journal on Discrete Mathematics , 22 (4): 1277–1296, CiteSeerX 10.1.1.188.5016 , doi .6 / 469106 7/6906 :
• Corneil, Derek G. (2004), "Lexicographic width first search – a survey", Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Tyskland, 21-23 juni 2004, Revised Papers , Lecture Notes in Computer Science, vol. 3353, Springer-Verlag, s. 1–19, doi : 10.1007/978-3-540-30559-0_1 .
• Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS och förfining av partitioner, med tillämpningar för transitiv orientering, intervallgrafigenkänning och konsekutiva tester", Theoretical Computer Science , 234 (1–2): 59–84, doi : 10.1016/S0304 -3975(97)00241-7 .
• Rose, DJ; Tarjan, RE ; Lueker, GS (1976), "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing , 5 (2): 266–283, doi : 10.1137/0205021 .