Grafic dublu de acorduri

Un graf nedirecționat G este dual cordal dacă hipergraful său maxim al clicei este un hypertree . Numele provine de la faptul că un graf este cordal dacă și numai dacă hipergraful său maxim de clic este dual cu un hiperarbore. Aceste grafice au fost inițial definite de vecinătatea maximă și au un număr de descrieri diferite [1] [2] [3] . Spre deosebire de graficele de acorduri, proprietatea cordalității duale nu este moștenită, adică subgrafele generate ale unui graf de acorduri duale nu sunt neapărat cordale duale (în sensul moștenirii, graficele de acorduri duale sunt exact succesorii graficelor strict de acorduri) și un graficul dual cordal nu este perfect în general . Graficele duale de acorduri au apărut inițial sub denumirea de HT-graphs [4] [5] [6] .

Descriere

Graficele dual cordale sunt grafice clicuri ale grafurilor cordale [7] [8] , adică grafice de intersecție ale clicurilor maxime ale grafurilor cordale.

Următoarele proprietăți sunt echivalente cu [1] [2] [9] [5] [6] :

De asemenea, din condiția unui hipergraf de vecinătate închisă rezultă că un graf este dual cordal dacă și numai dacă pătratul său este cordal și hipergraful său de vecinătate închisă are proprietatea Helly .

Articolul lui De Caria și Gutirrez [11] descrie grafurile duale de acorduri în termeni de proprietăți ale separatorilor. S-a arătat în articolul lui Breshard [12] că graficele duale cordale sunt exact graficele de intersecție ale hipercuburilor maxime ale graficelor complexelor cubice aciclice.

Structura și utilizarea algoritmică a graficelor dublu cordale au fost date de Marina Moscarini [13] . Acestea sunt grafice cordale care sunt simultan și dual cordale.

Recunoaștere

Graficele duale de acorduri pot fi recunoscute în timp liniar, iar ordonarea vecinătății maxime a unui grafic de acorduri duale poate fi găsită în timp liniar [2] [4] .

Complexitatea problemelor

În timp ce problemele de bază, cum ar fi găsirea setului maxim independent , a clicei maxime , a colorării și a acoperirii clicei, rămân NP-complete pentru graficele cu acorduri duale, unele variante ale setului dominant Steiner și ale problemei arborelui sunt rezolvate efectiv pentru graficele cu acorduri duale (dar cele independente). dominația rămâne NP-completă ) [2] [5] [6] . A se vedea Branstadt, Chepoy și Dragan [14] pentru utilizarea proprietăților graficelor duale de acorduri pentru problemele arborelui de acoperire și Branstadt, Leitert și Rautenbach [15] pentru algoritmul de dominanță a vârfurilor și a marginilor în timp liniar.

Note

  1. ↑ 1 2 Andreas Brandstädt, Feodor Drăgan, Victor Chepoi, Vitaly Voloshin. Dually Chordal Graphs // Note de curs în informatică . - 1993. - T. 790 . — S. 237–251 .
  2. ↑ 1 2 3 4 Andreas Brandstädt, Victor Chepoi, Feodor Drăgan. Utilizarea algoritmică a structurii hypertree și a ordonărilor maxime de vecinătate // Matematică aplicată discretă . - 1998. - T. 82 . — p. 43–77 . - doi : 10.1016/s0166-218x(97)00125-x .
  3. ↑ Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Clasele grafice: un sondaj. - Monografii SIAM despre matematică discretă și aplicații, 1999. - ISBN 0-89871-432-X .
  4. ↑ 1 2 Feodor Drăgan. Centrele de grafice și proprietatea Helly (în rusă). — Ph.D. teză, Universitatea de Stat din Moldova, Moldova, 1989.
  5. ↑ 1 2 3 Feodor Drăgan, Chiril Prisăcaru, Victor Chepoi. Probleme de locație în grafice și proprietatea Helly // Matematică discretă. (Moscova) . - 1992. - T. 4 . — p. 67–73 . ; F. F. Drăgan, K. F. Prisakar, V. D. Chepoy. Probleme de locație pe grafice și proprietatea Helly  // Diskret. Mat.. - 1992. - V. 4 , nr. 4 . — p. 67–73 . ; Fedor Fedorovici Drăgan. Centrele în grafice și proprietatea Helly. - Minsk: Academia de Științe a BSSR. Institutul de Matematică, 1989. - (Rezumatul autorului Candidatului la Științe Fizice și Matematice: 01.01.09).
  6. ↑ 1 2 3 Feodor Drăgan. Grafice HT: centre, dominație r conectată și arbori Steiner // Calcul. sci. J. al Moldovei (Chişinău) . - 1993. - T. 1 . — S. 64–83 .
  7. ↑ Marisa Gutierrez, Oubina. Caracterizări metrice ale graficelor cu intervale adecvate și ale graficelor Tree-Clique  // Journal of Graph Theory . - 1996. - T. 21 . — S. 199–205 . - doi : 10.1002/(sici)1097-0118(199602)21:2<199::aid-jgt9>3.0.co;2-m .
  8. ↑ Jayme L. Szwarcfiter, Claudson F. Bornstein. Clique Graphs of Chordal and Path Graphs // SIAM Journal on Discrete Mathematics . - 1994. - T. 7 . — S. 331–336 . - doi : 10.1137/s0895480191223191 .
  9. ↑ Andreas Brandstädt, Feodor Drăgan, Victor Chepoi, Vitaly Voloshin. Dually Chordal Graphs // SIAM Journal on Discrete Mathematics . - 1998. - T. 11 . — S. 437–455 . - doi : 10.1137/s0895480193253415 .
  10. ↑ Conceptul de ordonare a cartierului maxim nu este banal, în articol (Brandstädt, Dragan, Chepoi, Voloshin, 1998, pp. 440-442) este nevoie de 2 pagini.
  11. ↑ Pablo De Caria, Marisa Gutierrez. On Minimal Vertex Separators of Dually Chordal Graphs: Properties and Characterizations // Matematică aplicată discretă . - 2012. - T. 160 . — S. 2627–2635 . - doi : 10.1016/j.dam.2012.02.022 .
  12. ↑ Bostjan Bresar. Grafice de intersecție ale hipercuburilor maxime // European Journal of Combinatorics . - 2003. - T. \u003d 24 . — S. 195–209 . - doi : 10.1016/s0195-6698(02)00142-7 .
  13. ↑ Marina Moscarini. Grafice dublu Chordal, arbori Steiner și dominație conectată  // Rețele. - 1993. - T. 23 . — p. 59–69 . - doi : 10.1002/net.3230230108 .
  14. ↑ Andreas Brandstädt, Victor Chepoi, Feodor Drăgan. Arbori de aproximare a distanței pentru graficele cordale și dual chordal // Journal of Algorithms . - 1999. - T. 30 . — S. 166–184 . - doi : 10.1006/jagm.1998.0962 .
  15. ↑ Andreas Brandstädt, Arne Leitert, Dieter Rautenbach. Seturi dominante eficiente și dominante de margine pentru grafice și hipergrafe // Note de curs în informatică . - 2012. - T. 7676 . — S. 267–277 .

Literatură