Grafic acordal

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
O buclă (neagră) cu două șiruri (verzi). În ceea ce privește această parte, graficul este acord. Cu toate acestea, eliminarea unei margini verzi ar duce la un grafic non-acord. De fapt, cealaltă margine verde cu trei margini negre ar forma o buclă de patru lungimi fără șiruri.

În câmpul matematic al teoriei graficelor , un grafic este acord dacă fiecare dintre ciclurile sale de patru sau mai multe vârfuri are o coardă , care este o margine care nu face parte din ciclu, dar conectează două dintre vârfurile acestuia din urmă. În mod echivalent, fiecare buclă indusă din grafic ar trebui să aibă cel mult trei noduri. Grafele acordurilor pot fi, de asemenea, caracterizate ca grafice care au ordonări de eliminare perfecte, cum ar fi grafice în care fiecare separator minim este o fisură și ca grafice de intersecție a subarborilor unui copac. Uneori se numesc grafice cu circuite rigide [1] sau grafuri triangulate . [2]

Grafele acordurilor sunt un subset de grafice perfecte . Acestea pot fi recunoscute în timp polinomial , iar mai multe probleme care sunt dificile în alte clase de grafice, cum ar fi colorarea graficelor, pot fi rezolvate în timp polinomial când intrarea este corală. Lățimea arborelui unui grafic arbitrar poate fi caracterizată prin dimensiunea fisurilor din graficele chordale care îl conțin.

Eliminare perfectă și recunoaștere eficientă

O ordonare perfectă de eliminare într-un grafic este o ordonare a vârfurilor graficului astfel încât, pentru fiecare vârf v , v și vecinii lui v care apar după v în ordine, să formeze o fisură . Un grafic este acord dacă și numai dacă are o ordonare perfectă de eliminare. [3]

Rose, Lueker și Tarjan (1976) (vezi și Habit și colab. (2000) ) arată că o ordonare perfectă de eliminare a unui grafic chordal poate fi găsită eficient folosind un algoritm cunoscut sub numele de căutare lexicografică . Acest algoritm menține o partiție a vârfurilor grafului într-o succesiune de seturi; inițial această secvență constă dintr-un singur set cu toate vârfurile. Algoritmul alege în mod repetat un vârf v din primul set din secvența care conține vârfurile care nu au fost alese anterior și împarte fiecare set S al secvenței în două subseturi mai mici, primul constând din vecinii lui v în S și al doilea care constă a non-vecinilor. Când acest proces de împărțire a fost efectuat pentru toate vârfurile, secvența seturilor are un singur vârf pentru fiecare set, în sens invers unei ordine de eliminare perfectă.

Deoarece atât acest proces de căutare lexicografică în amplitudine, cât și procesul de verificare dacă o ordonare este de eliminare perfectă pot fi realizate în timp liniar, este posibil să se recunoască graficele chordale în timp liniar. Problema sandvișului grafic pe graficele acordelor este NP-completă, [4] în timp ce problema graficului sondei pe graficele acordurilor are complexitate polinomială în timp. [5]

Setul tuturor ordonărilor de eliminare perfecte ale unui grafic chordal poate fi modelat ca cuvintele de bază ale unui antimatroid ; Chandra și colab. (2003) folosesc această conexiune cu antimatroizi ca parte a unui algoritm pentru a enumera eficient toate ordonările de eliminare perfecte ale unui grafic acordal dat.

Fisuri maxime și colorare a graficului

O altă aplicație a ordonărilor de eliminare perfectă este de a găsi o clică a unui grafic chordal în timp polinomial, în timp ce aceeași problemă pentru graficele generale este NP-completă . Mai general, un grafic acordal poate avea doar un număr liniar de fisuri maxime , în timp ce graficele non-corale pot avea un număr exponențial. Pentru a enumera toate fisurile maxime ale unui grafic de coarde, găsim pur și simplu o ordine de eliminare perfectă, formăm o fisură pentru fiecare vârf v împreună cu vecinii lui v care sunt ulterioare lui v în ordinea de eliminare perfectă și verificăm dacă fiecare dintre rezultatele rezultate fisurile sunt maxime.

Cea mai mare fisură maximă este o fisură maximă și, din moment ce graficele acordurilor sunt perfecte, dimensiunea fisurii este egală cu numărul cromatic al graficului acordal. Graficele acordurilor sunt perfect sortabile : o colorare optimă poate fi obținută prin aplicarea unui algoritm de colorare lacom pe vârfuri în inversul unei ordonări perfecte de eliminare. [6]

Separatoare minime

În orice grafic, un separator de vârf este un set de vârfuri a căror îndepărtare lasă graficul rămas deconectat; un separator este minim dacă nu are un subset propriu, care este, de asemenea, un separator. Conform teoremei lui Dirac (1961) , graficele acordurilor sunt grafice în care fiecare separator minim este o fisură; Dirac a folosit această caracterizare pentru a demonstra că graficele acordurilor sunt perfecte .

Familia graficelor acordurilor poate fi definită inductiv ca graficele ale căror vârfuri pot fi împărțite în trei subseturi A , S și B ne-goale, astfel încât A ∪ S și S ∪ B formează ambele subgrafe acordate induse , S este o fisură și nu există margini de la A la B. Adică sunt graficele care au o descompunere recursivă în subgrafe mai mici prin intermediul separatorilor de fisuri. Din acest motiv, graficele acordurilor au fost uneori numite și grafice descompozabile . [7]

Graficele de intersecție ale subarborilor

Un grafic acordal cu opt vârfuri, reprezentat ca graficul de intersecție a opt sub arbori ai unui arbore cu șase noduri.

O caracterizare alternativă a graficelor acordurilor, datorită lui Gavril (1974) , implică copacii și subarborii lor.

Dintr-o colecție de subarburi dintr-un arbore, puteți defini un grafic subarborescent , care este un grafic de intersecție care are un singur vârf pentru fiecare subarborescență și o margine care leagă oricare dintre doi subarbori care se suprapun într-unul sau mai multe noduri subarborescente. Gavril arată că graficele subarborescente sunt exact grafice acorde.

O reprezentare a unui grafic acord ca o intersecție a subarburilor formează o descompunere a arborelui a graficului, cu lățimea arborelui egală cu un minus dimensiunea celei mai mari fisuri din grafic; descompunerea arborelui oricărui grafic G poate fi văzută în acest fel ca o reprezentare a lui G ca subgraf al unui grafic acordal. Descompunerea arborelui unui grafic este, de asemenea, arborele de joncțiune al algoritmului cu același nume .

Relația cu alte clase de grafice

Subclase

Graficele de intervale sunt graficele de intersecție ale subarborilor graficelor de cale , un caz special al copacilor. Prin urmare, acestea sunt o subfamilie a graficelor acordurilor.

Graficele divizate sunt grafice care sunt atât corale, cât și complementare ale graficelor corale. Bender, Richmond și Wormald (1985) au arătat că, în limita când n merge la infinit, fracțiunea graficelor coarde cu n vârfuri care sunt împărțite se apropie de una.

Graficele ptolemeice sunt grafice care sunt atât cordale, cât și la distanțe ereditare .

Graficele de cvasi-prag sunt o subclasă de grafice ptolemeice care sunt atât corale, cât și cografice . Graficele bloc sunt o altă subclasă a graficelor ptolemeice în care oricare două fisuri maxime au cel mult un vârf în comun. Un tip special sunt graficele morii de vânt , unde vârful comun este același pentru fiecare pereche de fisuri.

Graficele puternic acordate sunt grafice care sunt acorde și nu conțin niciun SU n ( n ≥3) ca subgraf indus.

Arborii K sunt grafice coordonate în care toate criticile maxime și toți separatorii maximi de fisuri au aceeași dimensiune. [8] Rețelele apoliene sunt grafice plane , sau echivalent 3-arbori planari. [8] Graficele maxime externe sunt o subclasă de 2 arbori și, prin urmare, sunt, de asemenea, corale.

Superclasă

Grafele acordurilor sunt o subclasă a graficelor perfecte bine cunoscute. Alte superclase de grafice acorde includ grafice slab acorde, grafice fără găuri impare și grafice fără găuri pare . Într-adevăr, graficele acordurilor sunt exact graficele care sunt atât fără găuri impare, cât și fără găuri pare (vezi găurile din teoria graficelor).

Fiecare grafic acordal este un grafic sugrumat , un grafic în care fiecare ciclu periferic este un triunghi, deoarece ciclurile periferice sunt un caz special al ciclurilor induse. Graficele stricte sunt grafice care pot fi formate din sumele fisurilor graficelor corale și ale graficelor plane maxime. Prin urmare, graficele strangulate includ grafice plane maxime . [9]

Completări acordate și lățimea arborelui

Dacă G este un grafic arbitrar, o completare acordală a lui G este un grafic acord care conține G ca subgraf. Lățimea arborelui lui G este cu una mai mică decât numărul de vârfuri într-o crăpătură maximă a unei corodări alese pentru a minimiza această dimensiune a fisurii. Arborii K sunt grafice la care nu se pot adăuga margini suplimentare fără a le mări lățimea arborelui la un număr mai mare decât k . Prin urmare, arborii k sunt propriile lor completări acorduale și formează o subclasă a graficului acordal. Completările de acorduri pot fi, de asemenea, utilizate pentru a caracteriza alte câteva clase conexe de grafice. [10]

Notă

  1. ^ Dirac (1961) .
  2. ^ (EN) Eric W. Weisstein, Grafic triunghiular , în MathWorld , Wolfram Research. . Cu toate acestea, rețineți că „graficele triunghiulate” se referă uneori și la graficele plane maxime .
  3. ^ Fulkerson & Gross (1965) .
  4. ^ Bodlaender, Fellows & Warnow (1992) .
  5. ^ Berry, Golumbic și Lipshteyn (2007) .
  6. ^ Maffray (2003) .
  7. ^ Peter Bartlett, Modele grafice nedirecționate: grafice chordale, grafice descompozabile, arbori de joncțiune și factorizări ( PDF ), la stat.berkeley.edu .
  8. ^ a b Patil (1986) .
  9. ^ Seymour & Weaver (1984) .
  10. ^ Parra și Scheffler (1997) .

Bibliografie

Alte proiecte

linkuri externe

Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică
Adus de la „ https://it.wikipedia.org/w/index.php?title=Grafo_cordale&oldid=104516746 ”