Grafic moștenit la distanță

În teoria graficelor, un grafic moștenit de distanță (sau un grafic complet separabil ) [1] este un grafic în care distanțele din orice subgraf generat conectat sunt aceleași ca în graficul original. Astfel, orice subgraf generat moștenește distanțele graficului mai mare.

Graficele moștenite la distanță au fost denumite și studiate pentru prima dată de Howorka [2] , deși pentru o clasă echivalentă de grafice s-a arătat deja în 1970 de către Olaru și Sachs că clasa conține grafice perfecte [3] .

Se știe de ceva vreme că grafurile moștenite de distanță constituie clasa grafurilor de intersecție [4] , dar modelul de intersecție nu a fost cunoscut până când a fost dat de Gioan și Paul ( Gioan, Paul 2012 ).

Definiție și descriere

Definiția inițială a unui graf moștenit de distanță este un grafic G astfel încât, dacă oricare două vârfuri u și v aparțin unui subgraf generat conex H din G , atunci cea mai scurtă cale care conectează u și v în G trebuie să fie în subgraful H , deci distanța dintre u și v în H va fi aceeași ca și în G .

Graficele moștenite la distanță pot fi descrise în mai multe alte moduri echivalente: [5]

Relația cu alte familii de grafice

Orice grafic moștenit de distanță este perfect [2] , mai precis, un grafic complet ordonabil [8] . Orice graf moștenit de distanță este, de asemenea, un graf par , un graf în care oricare două căi dintre aceeași pereche de vârfuri sunt simultan fie pare, fie impare [9] . Orice grad par al unui graf moștenit de distanță G (adică un graf G 2 i format prin conectarea perechilor de vârfuri la o distanță care nu depășește 2 i în G ) este un graf cordal [10] .

Orice grafic moștenit de distanță poate fi reprezentat ca un grafic al intersecțiilor coardelor într-un cerc, adică ca un grafic cerc . Acest lucru poate fi arătat prin construirea unui grafic prin adăugarea de vârfuri suspendate, „gemeni” și „gemeni”, formând astfel la fiecare pas un set de acorduri reprezentând graficul. Adăugarea unui vârf atârnător corespunde cu adăugarea unei coarde aproape de sfârșitul unei coarde existente, astfel încât noul acord să intersecteze doar acel acord. Adăugarea unui „geamăn” corespunde înlocuirii unui acord cu două acorduri paralele care intersectează același set de acorduri. Adăugarea unui „geamăn” corespunde înlocuirii unui acord cu două acorduri care se intersectează aproape paralele care intersectează același set de alte acorduri.

Un grafic moștenit de distanță este bipartit dacă și numai dacă nu are triunghiuri . Un grafic bipartit moștenit de distanță poate fi construit dintr-un singur vârf adăugând numai vârfuri și gemeni suspendați, deoarece orice geamăn formează un triunghi, iar adăugarea unui vârf și gemeni suspendați păstrează bipartitatea.

Graficele care pot fi construite dintr-un singur vârf adăugând vârfuri suspendate și creând „gemeni” fără a crea „gemeni” sunt cazuri speciale de grafice ptoleemie și includ grafice bloc . Graficele care pot fi create dintr-un singur vârf prin crearea de gemeni și gemeni, dar fără a adăuga vârfuri suspendate, sunt cografe , care sunt astfel moștenite la distanță. Cografele sunt exact uniunea disjunctă a grafurilor moștenite de distanță cu diametrul 2. O vecinătate a oricărui vârf al unui graf moștenit de distanță este un cograf. Închiderea tranzitivă a unui grafic direcționat format prin alegerea oricărui set de orientări ale marginilor oricărui arbore este moștenită de distanță. Cazul special în care arborele este orientat departe de un vârf formează o subclasă de grafuri moștenite de distanță cunoscute sub denumirea de grafuri trivial perfecte , care sunt numite și cografe cordale [11] .

Algoritmi

Graficele moștenite de distanță pot fi recunoscute și descompuse într-o succesiune de vârfuri suspendate și operații de dublare în timp liniar [12] .

Deoarece graficele moștenite de distanță sunt perfecte, unele probleme de optimizare pot fi rezolvate în timp polinomial, deși aceste probleme sunt NP-grele pentru clase mai generale de grafice. Astfel, este posibil în timp polinomial să găsim clica maximă sau mulțimea independentă într-un grafic moștenit de distanță sau să găsim colorarea optimă a acesteia [13] . Deoarece graficele moștenite de distanță sunt grafice circulare, ele moștenesc algoritmi de timp polinomial pentru graficele circulare. De exemplu, se poate determina în timp polinomial lățimea arborelui oricărui grafic circular și, prin urmare, orice grafic moștenit de distanță [14] [15] . În plus, lățimea clicei a oricărui grafic moștenit de distanță nu depășește trei [16] . În consecință, conform teoremei lui Courcelle , pentru multe probleme de pe aceste grafice există algoritmi eficienți bazați pe programare dinamică [17] [18] .

Alte probleme de optimizare ale graficelor moștenite la distanță pot fi rezolvate eficient folosind algoritmi special concepuți pentru astfel de grafice. După cum au arătat de Atri și Moscarini [19] , o mulțime dominantă conexă minimă (sau, echivalent, un arbore care se întinde cu numărul maxim posibil de frunze) poate fi găsită în timp polinomial pe grafice moștenite de distanță. Graficul hamiltonian sau calea hamiltoniană a oricărui grafic moștenit de distanță poate fi găsit în timp polinomial [20] [21] .

Note

  1. ↑ Hammer, Maffray, 1990 .
  2. ↑ 12 Howorka , 1977 .
  3. ↑ Olaru și Sachs au arătat α-perfecțiunea graficelor în care orice ciclu de lungime cinci sau mai mult are o pereche de diagonale care se intersectează ( Sachs, 1970 , Teorema 5). Potrivit lui Lovász ( Lovász 1972 ), α-perfecțiunea este o formă echivalentă a definiției graficelor perfecte.
  4. ^ McKee, McMorris, 1999 .
  5. ↑ Howorka (1977 ); Bandelt, Mulder (1986 ); Hammer, Maffray (1990 ); Brandstädt, Le, Spinrad (1999 ), Teorema 10.1.1, p. 147.
  6. ↑ Gioan, Paul (2012 ). O descompunere strâns legată este utilizată pentru vizualizarea graficelor de către Epstein, Goodrich și Meng ( Eppstein, Goodrich, Meng (2006 )) și (pentru graficele bipartite moștenite la distanță) de Hui , Schaefer, Štefankovič (2004 )).
  7. ↑ Oum, 2005 .
  8. ↑ Brandstädt, Le, Spinrad, 1999 , p. 70–71, 82.
  9. ↑ Brandstädt, Le, Spinrad, 1999 , p. 45.
  10. ↑ Brandstädt, Le, Spinrad, 1999 , p. 164 Teorema 10.6.14.
  11. ↑ Cornelsen, Di Stefano, 2005 .
  12. ↑ Damiand, Habib, Paul (2001 ); Gioan, Paul (2012 ). Înainte de aceasta, granița fusese stabilită de Hammer și Maffray (1990 ), dar Damiand a descoperit o eroare în raționament.
  13. ↑ Cogis și Thierry Cogis, Thierry (2005 ) au prezentat un algoritm direct simplu pentru găsirea de seturi independente ponderate maxime în grafice moștenite de distanță bazat pe descompunerea graficului în vârfuri suspendate și vârfuri duble, corectând o încercare anterioară a unui astfel de algoritm de către Hammer și Maffray. ( Hammer, Maffray) (1990 )). Deoarece graficele moștenite de distanță sunt bine ordonate, ele pot fi colorate optim în timp liniar folosind algoritmul de ordonare perfectă LexBFS și aplicând o colorare greedy .
  14. ↑ Kloks, 1996 .
  15. ↑ Brandstädt, Le, Spinrad, 1999 , p. 170.
  16. ↑ Golumbic, Rotics, 2000 .
  17. ↑ Courcelle, Makowski, Rotics, 2000 .
  18. ↑ Espelage, Gurski, Wanke, 2001 .
  19. ↑ D'Atri, Moscarini, 1988 .
  20. ↑ Hsieh, Ho, Hsu, Ko, 2002 .
  21. ↑ Müller, Nicolai, 1993 .

Literatură

Link -uri