Split (grafteori)
I grafteorin är en uppdelning av en oriktad graf ett snitt vars cut-set bildar en komplett tvådelad graf . En graf är primtal om den inte har några delningar. Delarna av en graf kan samlas in i en trädliknande struktur som kallas split decomposition eller join decomposition , som kan konstrueras i linjär tid. Denna nedbrytning har använts för snabb igenkänning av cirkelgrafer och avståndsärftliga grafer, såväl som för andra problem i grafalgoritmer.
Uppdelningar och delade uppdelningar introducerades först av Cunningham (1982) , som också studerade varianter av samma föreställningar för riktade grafer .
Definitioner
Ett snitt av en oriktad graf är en uppdelning av hörnen i två icke-tomma delmängder, sidorna av snittet. Delmängden av kanter som har en ändpunkt på varje sida kallas en cut-set. När en cut-set bildar en komplett tvådelad graf kallas dess cut en split. Således kan en uppdelning beskrivas som en uppdelning av grafens hörn i två delmängder X och Y , så att varje granne till X i Y ligger intill varje granne till Y i X.
Ett snitt eller split är trivialt när en av dess två sidor bara har en vertex i sig; varje triviala snitt är en splittring. En graf sägs vara primtal (med avseende på delningar) om den inte har några icke-triviala delningar.
Två delningar sägs korsa om varje sida av en del har en icke-tom korsning med varje sida av den andra delningen. En split kallas stark när den inte korsas av någon annan split. Som ett specialfall är varje trivial splittring stark. De starka splittringarna i en graf ger upphov till en struktur som kallas delad uppdelning eller sammanfogad nedbrytning av grafen. Denna nedbrytning kan representeras av ett träd vars löv motsvarar en-till-en med den givna grafen, och vars kanter motsvarar en-till-en med de starka delarna av grafen, så att uppdelningen av löv som bildas genom att ta bort någon kant från trädet är detsamma som uppdelningen av hörn som ges av den associerade starka splittringen.
Varje intern nod i i det delade nedbrytningsträdet för en graf G är Gi associerad med en graf , kallad kvotgrafen för nod i . Kvotensgrafen kan bildas genom att ta bort i från trädet, bilda delmängder av hörn i G som motsvarar löven i vart och ett av de resulterande underträden, och kollapsa var och en av dessa vertexuppsättningar till en enda vertex. Varje kvotgraf har en av tre former: det kan vara en primgraf, en komplett graf eller en stjärna .
En graf kan ha exponentiellt många olika uppdelningar, men de är alla representerade i det delade nedbrytningsträdet, antingen som en kant av trädet (för en stark uppdelning) eller som en godtycklig uppdelning av en komplett graf eller stjärnkvotsgraf (för en uppdelning som är inte stark).
Exempel
I en komplett graf eller komplett tvådelad graf är varje snitt en uppdelning.
I en cykelgraf med längd fyra är uppdelningen av hörnen som ges genom att 2-färga cykeln en icke-trivial uppdelning, men för cykler av längre längd finns det inga icke-triviala uppdelningar.
En brygga av en graf som inte är 2-kantsbunden motsvarar en delning, där varje sida av delningen bildas av hörnen på ena sidan av bryggan. Spaltningens snitt är bara den enda bryggkanten, vilket är ett specialfall av en komplett tvådelad subgraf. På liknande sätt, om v är en artikulationspunkt för en graf som inte är 2-vertex-kopplad , så har grafen flera uppdelningar där v och några men inte alla komponenter som bildas av dess radering är på ena sidan, och de återstående komponenterna är på andra sidan. I de här exemplen bildar delningen en stjärna .
Algoritmer
Cunningham (1982) visade redan att det är möjligt att hitta den delade nedbrytningen i polynomtid . Efter efterföljande förbättringar av algoritmen upptäcktes linjära tidsalgoritmer av Dahlhaus (2000) och Charbit, de Montgolfier & Raffinot (2012) .
Ansökningar
Delad uppdelning har använts för att identifiera flera viktiga grafklasser:
- En avståndsärftlig graf är en graf vars delade uppdelning inte innehåller några primtalskvoter. Baserat på denna karakterisering är det möjligt att använda den delade uppdelningen för att känna igen avståndsärftliga grafer i linjär tid.
- Paritetsgrafer kan kännas igen i linjär tid som de grafer där varje delad kvot är antingen komplett eller tvådelad .
- En cirkelgraf är skärningsgrafen för en familj av ackord i en cirkel. En given graf är en cirkelgraf om och endast om var och en av kvoterna för dess delade sönderdelning är en cirkelgraf, så att testa om en graf är en cirkelgraf kan reduceras till samma problem på grafens primkvotsgrafer. När en cirkelgraf är primtal, är den kombinatoriska strukturen för uppsättningen av ackord som representerar den unikt bestämd, vilket förenklar uppgiften att känna igen denna struktur. Baserat på dessa idéer är det möjligt att känna igen cirkelgrafer i polynomtid.
Delad uppdelning har också använts för att förenkla lösningen av några problem som är NP-hårda på godtyckliga grafer:
- Som Cunningham (1982) redan har observerat, kan den maximala oberoende uppsättningen av varje graf hittas av en dynamisk programmeringsalgoritm på en genomgång nerifrån och upp av dess delade nedbrytningsträd. Vid varje nod väljer vi den maximala viktoberoende uppsättningen på dess kvotgraf, viktad med storlekarna på de oberoende uppsättningarna som redan beräknats vid undernoder.
- Även om en annan algoritm som ges av Cunningham (1982) är felaktig, kan en liknande genomgång nerifrån och upp användas för att beräkna den maximala klicken för en graf genom att kombinera beräkningar av viktade maximiklick i dess kvotgrafer.
- Rao (2008) presenterar också algoritmer för anslutna dominerande uppsättningar , kompletta dominerande uppsättningar och graffärgning .
Dessa metoder kan leda till polynomiska tidsalgoritmer för grafer där varje kvotgraf har en enkel struktur som gör att dess delproblem kan beräknas effektivt. Detta gäller till exempel de grafer där varje kvotgraf har konstant storlek.