Graficul împărțit

În teoria grafurilor, un graf divizat este un graf în care vârfurile pot fi împărțite într-o clică și o mulțime independentă . Graficele split au fost studiate pentru prima dată de Földes și Hammer [1] [2] , și introduse independent de Tyszkiewicz și Czernyak [3] [4] .

Un grafic divizat poate avea mai multe descompuneri pe clică și o mulțime independentă. Astfel, calea a - b - c este împărțită și poate fi împărțită în trei moduri diferite:

  1. clică { a , b } și mulțime independentă { c }
  2. clică { b , c } și mulțime independentă { a }
  3. clică { b } și mulțime independentă { a , c }

Graficele divizabile pot fi caracterizate în funcție de subgrafele lor interzise - un grafic este împărțit dacă și numai dacă niciun subgraf generat nu este un ciclu cu patru sau cinci vârfuri și, de asemenea, nu există o pereche de vârfuri deconectate (adică complementul unui ciclu din 4 vârfuri) [5 ] [6] .

Relația cu alte familii de grafice

Prin definiție, clasa de grafice împărțite este închisă în raport cu operația de complement [7] . O altă caracteristică a grafurilor divizate care implică complement este grafurile cordale , ale căror complemente sunt tot cordale [8] . Deoarece graficele cordale sunt grafice de intersecție ale subarborilor de arbori, graficele împărțite sunt grafice de intersecție ale diferitelor substele de stele [9] . Aproape toate graficele de acorduri sunt grafice împărțite. Adică, pe măsură ce n tinde spre infinit, câtul dintre numărul de grafuri cordale cu n vârfuri și numărul de grafuri separabile tinde spre unu [10] .

Deoarece graficele de acorduri sunt perfecte , graficele divizibile sunt de asemenea perfecte. Grafice duble împărțite , o familie de grafice obținute din grafice divizate prin dublarea numărului de vârfuri (astfel încât o clică să dea o antipotrivire - un set de muchii la cel mult 2 distanțe, iar un set independent devine o potrivire), apare ca unul dintre cele cinci clase principale de grafuri perfecte din care toate celelalte pot fi construite pentru a demonstra teorema riguroasă a grafurilor perfecte [11] .

Dacă un grafic este atât divizabil, cât și interval , atunci complementul său este atât divizibil, cât și un grafic de comparabilitate și invers. Graficele de comparabilitate divizabile și, prin urmare, graficele de intervale divizabile, pot fi descrise în termeni de trei subgrafe interzise [12] . Cografele divizate sunt  exact grafice de prag , iar graficele de permutare divizate  sunt exact grafice de interval ale căror complemente sunt, de asemenea, interval [13] . Numărul cocromatic al graficelor împărțite este 2.

Clică maximă și set independent maxim

Fie G  un grafic divizat descompus într-o clică C și o mulțime independentă I . Atunci orice clică maximă din graficul împărțit fie coincide cu C , fie este o vecinătate a unui vârf din I . Astfel, într-un grafic divizat, este ușor să găsiți clica maximă și, în plus, mulțimea independentă maximă . Orice grafic divizabil trebuie să aibă una dintre următoarele afirmații [14] :

  1. Există un vârf x în I astfel încât C ∪ { x } este complet. În acest caz, C ∪ { x } este o clică maximă și I  este o mulțime independentă maximă.
  2. Există un vârf x în C astfel încât I ∪ { x } este o mulțime independentă. În acest caz, I ∪ { x } este o mulțime independentă maximă și C  este o clică maximă.
  3. C este cea mai mare clică și I cel mai mare set independent. În acest caz, G are o descompunere unică ( C , I ) într-o clică și o mulțime independentă, C este o clică maximă, iar I este o mulțime independentă maximă.

Alte probleme de optimizare care sunt NP-complete pe familii mai generale de grafice, inclusiv colorarea , sunt rezolvate pur și simplu pe grafice divizate.

Secvențe de grade

Una dintre marile proprietăți ale graficelor împărțite este că ele pot fi recunoscute doar după secvențele lor de grade de vârf . Fie d 1 ≥ d 2 ≥ … ≥ d n  succesiunea de grade de vârf ale graficului G și m  cea mai mare valoare a lui i pentru care d i ≥ i  - 1. Atunci G este un grafic divizat dacă și numai dacă

Dacă acest lucru este adevărat, atunci cele m vârfuri cu cele mai mari grade formează o clică maximă G , iar vârfurile rămase formează o mulțime independentă [15] .

Numărarea graficelor divizate

Royle [16] a arătat că graficele divizate cu n vârfuri corespund unu la unu anumitor familii Sperner . Folosind acest fapt, el a găsit o formulă pentru numărul de grafice împărțite (neizomorfe) cu n vârfuri. Pentru valori mici ale lui n , începând de la n = 1, aceste numere sunt

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... secvența OEIS A048194 .

Această enumerare a fost dovedită anterior de Tyszkiewicz și Chernyak [17] .

Note

  1. ↑ Földes, Hammer, 1977a .
  2. ↑ Földes, Hammer, 1977b .
  3. ↑ Tyshkevich, Chernyak, 1979 .
  4. ↑ Földes și Hammer Földes, Hammer, 1977a a dat o definiție mai generală în care graficele pe care le numesc splittable includ, de asemenea, grafice bipartite (adică, grafice împărțite în două seturi independente) și complemente ale graficelor bipartite (adică, grafice care pot fi descompuse în două ). clicuri). Földer și Hammer Földes, Hammer, 1977b dau definiția dată aici și utilizată în literatura ulterioară, de exemplu Brandstädt, Le și Spinrad Brandstädt, Le, Spinrad, 1999 , Definiția 3.2.3, p. 41
  5. ↑ Földes, Hammer, 1977a ; Golumbic, 1980 , Teorema 6.3, p. 151.
  6. ↑ Pinar Heggernes, Dieter Kratsch. Algoritmi de recunoaștere de certificare în timp liniar și subgrafe induse interzise // Nordic Journal of Computing. - 2007. - T. 14 .
  7. ↑ Golumbic, 1980 , Teorema 6.1, p. 150.
  8. ↑ Földes, Hammer, 1977a ; Golumbic, 1980 , Teorema 6.3, p. 151; Brandstädt, Le, Spinrad, 1999 , Teorema 3.2.3, p. 41.
  9. ↑ McMorris, Shier, 1983 ; Voss, 1985 ; Brandstädt, Le, Spinrad, 1999 , Teorema 4.4.2, p. 52.
  10. ↑ Bender, Richmond, Wormald, 1985 .
  11. ↑ Chudnovsky, Robertson, Seymour, Thomas, 2006 .
  12. ↑ Földes, Hammer, 1977b ; Golumbic, 1980 , Teorema 9.7, p. 212.
  13. ↑ Brandstädt, Le, Spinrad, 1999 , Corolarul 7.1.1 p. 106 și Teorema 7.1.2 p. 107.
  14. ↑ Hammer, Simeone, 1981 ; Golumbic, 1980 , Teorema 6.2, p. 150.
  15. ↑ Hammer, Simeone, 1981 ; Tyshkevici, 1980 ; Tyshkevich, Melnikov, Kotov, 1981 ; Golumbic, 1980 , Teorema 6.7 și Corolarul 6.8, p. 154; Brandstädt, Le, Spinrad, 1999 , Teorema 13.3.2, p. 203. Merris, 2003 o analiză suplimentară a secvenței de grade a graficelor împărțite.
  16. ↑ Royle, 2000 .
  17. ↑ Tyshkevich, Chernyak, 1990 .

Literatură

Lectură suplimentară