Grafic strict de acorduri

Un graf nedirecționat G se numește strict cordal dacă este cordal și orice ciclu de lungime pară ( ) din G are o coardă impară , adică o muchie care conectează două vârfuri ale ciclului la o distanță impară (>1) unul de celălalt. [1] .

Descriere

Graficele strict cordale sunt descrise de graficele interzise ca fiind grafice care nu conțin un ciclu generat de mai mult de trei lungimi sau un n -sun ( ) ca subgraf generat [2] [3] [4] . n -Soarele este un graf cordal cu 2n vârfuri împărțite în două submulțimi și astfel încât fiecare vârf w i din W are exact doi vecini, u i și . n -Soarele nu poate fi strict cordal, deoarece ciclul ... nu are acorduri ciudate.

Graficele strict cordale pot fi descrise ca grafice care au o ordine strictă de eliminare perfectă, o ordine a vârfurilor astfel încât vecinii oricărui vârf care vin mai târziu în ordine formează o clică și astfel încât pentru oricare , dacă al i -lea vârf din ordine este adiacente la k -th și l -th vârfuri , și j -th și k -th vârfuri sunt adiacente, atunci ambele j -th și l -th vârfuri trebuie să fie adiacente [3] [5] .

Un graf este strict cordal dacă și numai dacă oricare dintre subgrafele sale generate are un vârf simplu, adică un vârf ai cărui vecini sunt ordonați liniar după ordinea de includere [3] [6] . De asemenea, un grafic este strict cordal dacă și numai dacă este cordal și orice ciclu de lungime cinci sau mai mare are un triunghi cu 2 corzi, adică un triunghi format din două acorduri și o margine a ciclului [7] .

Un graf este strict cordal dacă și numai dacă oricare dintre subgrafele sale generate este un graf cordal dual [8] .

Graficele strict cordale pot fi descrise în termeni de numărul de subgrafe complete cărora le aparține o muchie [9] . O altă descriere este dată în lucrarea lui De Caria și McKee [10] .

Recunoaștere

Este posibil să se determine dacă un grafic este strict cordal în timp polinomial prin căutarea în mod repetat și eliminarea unui vârf simplu. Dacă acest proces elimină toate vârfurile graficului, atunci graficul trebuie să fie strict cordal. În caz contrar, procesul nu găsește un subgraf fără un vârf simplu, iar în acest caz graficul original nu poate fi strict cordal. Pentru un graf strict cordal, ordinea în care vârfurile sunt îndepărtate în acest proces se numește ordine strictă de eliminare perfectă [3] .

Sunt cunoscuți algoritmi alternativi care pot determina dacă un graf este strict cordal și, dacă da, pot construi o ordine strictă de eliminare perfectă mai eficient, în timp, pentru un graf cu n vârfuri și m muchii [11] [12] [13] .

Subclase

O subclasă importantă (bazată pe filogenie ) este clasa k - grade de frunze , adică grafice formate din frunzele unui copac prin conectarea a două frunze cu o margine dacă distanța în copac nu depășește k . Un grad de frunză este un grafic care este un grad k -frunză pentru unele k . Deoarece gradele graficelor strict cordale sunt strict cordale și arborii sunt strict cordale, rezultă că gradele frunzelor sunt strict cordale. Ele formează propria lor subclasă de grafuri puternic cordale, care la rândul lor include grafurile cluster ca puteri de 2 foi [14] . O altă subclasă importantă de grafice strict cordale sunt graficele de intervale . Branstedt, Hudt, Mancini și Wagner [15] au arătat că graficele de interval și o clasă mai mare de căi direcționate ale rădăcinii sunt puteri ale frunzelor.

Probleme algoritmice

Deoarece graficele puternic cordale sunt atât cordale , cât și dual cordale , diferite probleme NP-complete, cum ar fi problema seturilor independente , problema clicei , colorarea , problema acoperirii clicei , mulțimea dominantă și problema arborelui minimal Steiner pot fi rezolvate eficient pentru graficele puternic cordale. Problema izomorfismului grafului este GI-complet [16] pentru grafurile strict cordale [17] . Căutarea ciclurilor hamiltoniene rămâne o problemă NP-completă pentru graficele divizate strict cordale [18] .

Note

  1. ↑ Brandstädt, Le, Spinrad, 1999 , p. 43, Definiția 3.4.1.
  2. ↑ Chang, 1982 .
  3. ↑ 1 2 3 4 Farber, 1983 .
  4. ↑ Brandstädt, Le, Spinrad, 1999 , p. 112, Teorema 7.2.1.
  5. ↑ Brandstädt, Le, Spinrad, 1999 , p. 77, Teorema 5.5.1.
  6. ↑ Brandstädt, Le, Spinrad, 1999 , p. 78, Teorema 5.5.2.
  7. ↑ Dahlhaus, Manuel, Miller, 1998 .
  8. ↑ Brandstädt, Drăgan, Chepoi, Voloshin, 1998 , p. 444, corolarul 3.
  9. ^ McKee, 1999 .
  10. ↑ De Caria, McKee, 2014 .
  11. ↑ Lubiw, 1987 .
  12. ↑ Paige, Tarjan, 1987 .
  13. ↑ Spinrad, 1993 .
  14. ↑ Nishimura, Ragde, Thilikos, 2002 .
  15. ↑ Brandstädt, Hundt, Mancini, Wagner, 2010 .
  16. ↑ Articolul introduce o nouă clasă de completitate - Graph Isomorphism completeness
  17. ↑ Uehara, Toda, Nagoya, 2005 .
  18. ↑ Müller, 1996 .

Literatură