Delad graf

I grafteorin är en delad graf en graf där hörnen kan delas in i en klick och en oberoende uppsättning . Delade grafer studerades först av Földes och Hammer [1] [2] , och introducerades oberoende av Tyszkiewicz och Czernyak [3] [4] .

En delad graf kan ha flera nedbrytningar per klick och en oberoende uppsättning. Således är vägen a - b - c delad och kan delas upp på tre olika sätt:

  1. klick { a , b } och oberoende uppsättning { c }
  2. klick { b , c } och oberoende uppsättning { a }
  3. klick { b } och oberoende uppsättning { a , c }

Uppdelningsbara grafer kan karakteriseras i termer av deras förbjudna subgrafer - en graf delas om och endast om ingen genererad subgraf är en cykel med fyra eller fem hörn, och det inte heller finns något par frånkopplade hörn (det vill säga komplementet till en cykel av 4 hörn) [5 ] [6] .

Släktskap med andra graffamiljer

Per definition är klassen av delade grafer stängd med avseende på komplementoperationen [7] . En annan egenskap hos delade grafer som involverar komplement är chordal graphs , vars komplement också är ackordala [8] . Eftersom ackordsgrafer är skärningsgrafer för trädunderträd, är delade grafer skärningsgrafer för olika understjärnor av stjärnor [9] . Nästan alla ackordsgrafer är delade grafer. Det vill säga, eftersom n tenderar till oändligheten, tenderar kvoten av antalet ackordsgrafer med n hörn till antalet separerbara grafer till ett [10] .

Eftersom ackordsgrafer är perfekta , är delbara grafer också perfekta. Dubbeldelade grafer , en familj av grafer som erhålls från delade grafer genom att dubbla antalet hörn (så att en klick ger en anti-matchning - en uppsättning kanter som högst 2 ifrån varandra, och en oberoende uppsättning blir en matchning), visas som en av de fem huvudklasserna av perfekta grafer från vilka alla andra kan konstrueras för att bevisa den rigorösa perfekta grafsatsen [11] .

Om en graf är både delbar och intervall , är dess komplement både delbar och en jämförbarhetsgraf , och vice versa. Delbara jämförbarhetsgrafer, och därmed delbara intervallgrafer, kan beskrivas i termer av tre förbjudna subgrafer [12] . Delade kografer är  exakt tröskeldiagram , och delade permutationsgrafer  är exakt intervallgrafer vars komplement också är intervall [13] . Det kokromatiska antalet för delade grafer är 2.

Maximal klick och maximal oberoende uppsättning

Låt G  vara en delad graf uppdelad i en klick C och en oberoende mängd I . Då sammanfaller varje maximal klick i den delade grafen antingen med C eller är en grannskap av en vertex från I . I en delad graf är det alltså lätt att hitta den maximala klicken och dessutom den maximala oberoende uppsättningen . Varje delbar graf måste ha ett av följande påståenden [14] :

  1. Det finns en vertex x i I så att C ∪ { x } är komplett. I detta fall är C ∪ { x } en maximal klick och I  en maximal oberoende mängd.
  2. Det finns en vertex x i C så att I ∪ { x } är en oberoende mängd. I detta fall är I ∪ { x } en maximal oberoende mängd och C  är en maximal klick.
  3. C är den största klicken och I den största oberoende uppsättningen. I detta fall har G en unik sönderdelning ( C , I ) till en klick och en oberoende mängd, C är en maximal klick och I är en maximal oberoende mängd.

Vissa andra optimeringsproblem som är NP-kompletta på mer allmänna graffamiljer, inklusive färgläggning , löses helt enkelt på delade grafer.

Gradsekvenser

En av de stora egenskaperna hos delade grafer är att de kan kännas igen rent av deras vertexgradsekvenser . Låt d 1 ≥ d 2 ≥ … ≥ d n  vara sekvensen av vertexgrader i grafen G och m  vara det största värdet av i för vilket d i ≥ i  - 1. Då är G en delad graf om och endast om

Om detta är sant, bildar de m hörn med de största graderna en maximal klick G , och de återstående hörnen bildar en oberoende mängd [15] .

Räkna delade grafer

Royle [16] visade att delade grafer med n hörn motsvarar en till en till vissa Sperner-familjer . Med hjälp av detta faktum hittade han en formel för antalet (icke-isomorfa) delade grafer med n hörn. För små värden på n , från n = 1, är dessa siffror

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... OEIS - sekvens A048194 .

Denna uppräkning har tidigare bevisats av Tyszkiewicz och Chernyak [17] .

Anteckningar

  1. ↑ Földes, Hammer, 1977a .
  2. ↑ Földes, Hammer, 1977b .
  3. ↑ Tysjkevitj, Chernyak, 1979 .
  4. ↑ Földes och Hammer Földes, Hammer, 1977a gav en mer allmän definition där graferna de kallar delbara även inkluderar tvådelade grafer (dvs. grafer uppdelade i två oberoende uppsättningar) och komplement till tvådelade grafer (dvs. grafer som kan delas upp i två klick). Földer och Hammer Földes, Hammer, 1977b ger den definition som ges här och används i efterföljande litteratur, t.ex. Brandstädt, Le och Spinrad Brandstädt, Le, Spinrad, 1999 , Definition 3.2.3, sid. 41
  5. ↑ Földes, Hammer, 1977a ; Golumbic, 1980 , Theorem 6.3, s. 151.
  6. ↑ Pinar Heggernes, Dieter Kratsch. Linjär-tidscertifierande igenkänningsalgoritmer och förbjudna inducerade subgrafer // Nordic Journal of Computing. - 2007. - T. 14 .
  7. ↑ Golumbic, 1980 , Theorem 6.1, s. 150.
  8. ↑ Földes, Hammer, 1977a ; Golumbic, 1980 , Theorem 6.3, s. 151; Brandstädt, Le, Spinrad, 1999 , Theorem 3.2.3, sid. 41.
  9. ↑ McMorris, Shier, 1983 ; Voss, 1985 ; Brandstädt, Le, Spinrad, 1999 , Theorem 4.4.2, s. 52.
  10. ↑ Bender, Richmond, Wormald, 1985 .
  11. ↑ Chudnovsky, Robertson, Seymour, Thomas, 2006 .
  12. ↑ Földes, Hammer, 1977b ; Golumbic, 1980 , Theorem 9.7, s. 212.
  13. ↑ Brandstädt, Le, Spinrad, 1999 , Corollary 7.1.1 s. 106 och Theorem 7.1.2 s. 107.
  14. ↑ Hammer, Simeone, 1981 ; Golumbic, 1980 , Theorem 6.2, s. 150.
  15. ↑ Hammer, Simeone, 1981 ; Tysjkevitj, 1980 ; Tyshkevich, Melnikov, Kotov, 1981 ; Golumbic, 1980 , Theorem 6.7 och Corollary 6.8, s. 154; Brandstädt, Le, Spinrad, 1999 , Theorem 13.3.2, s. 203. Merris, 2003 ytterligare övervägande av gradsekvensen för delade grafer.
  16. ↑ Royle, 2000 .
  17. ↑ Tysjkevitj, Chernyak, 1990 .

Litteratur

Ytterligare läsning