În teoria grafurilor, un graf se numește cordal dacă fiecare dintre ciclurile sale , care au patru sau mai multe muchii, are o coardă (o muchie care conectează două vârfuri ale ciclului, dar nu face parte din aceasta).
O definiție echivalentă este dacă orice ciclu fără acorduri are cel mult trei margini. Cu alte cuvinte, un graf cordal este un graf fără cicluri generate de lungime mai mare de trei.
Graficele cordale sunt un subset de grafice perfecte . Ele sunt uneori numite și grafice ciclic rigide [1] sau grafice triangulate . (Cel din urmă termen este uneori folosit în mod eronat pentru triangularea plană. Vezi graficele planare maxime .) [2]
O ordine de excludere perfectă într-un grafic este ordinea vârfurilor graficului astfel încât pentru fiecare vârf v , v și vecinii lui v care sunt după v în ordinea formează o clică . Un grafic este cordal dacă și numai dacă are o ordine de excludere perfectă [3]
Rose, Lucker și Tarjan (1976) [4] (vezi, de asemenea, Habib, McConnell, Paul, Vienneno (2000) [5] ) au arătat că ordinea perfectă de eliminare a unui graf cordal poate fi găsită eficient folosind un algoritm cunoscut sub numele de lățimea lexicografică. prima cautare . Acest algoritm împarte vârfurile graficului într-o secvență de mulțimi. Inițial, secvența constă dintr-un singur set care conține toate vârfurile. Algoritmul din buclă selectează vârful v din cea mai veche mulțime din secvența care conține vârfurile neselectate încă și împarte fiecare mulțime S a secvenței în două mai mici - unul este format din vecinii vârfului v din S , celălalt include toate vârfurile rămase. Când procesul de împărțire este efectuat pentru toate nodurile, toate mulțimile șirului conțin câte un vârf și formează o secvență inversă ordinii perfecte de eliminare.
Deoarece atât căutarea lexicografică pe lățimea întâi, cât și verificarea dacă o ordine este o excepție perfectă se pot face în timp liniar, este posibil să recunoaștem un grafic de acorduri în timp liniar. Problema sandwich pe un graf cordal este NP-complet [6] , în timp ce problema grafului test pe un graf cordal are complexitate în timp polinomial [7] .
Setul tuturor ordinelor de excludere perfecte ale unui graf cordal poate fi considerat drept cuvintele de bază ale unui antimatroid . Chandran și colab .. [8] au folosit această conexiune cu antimatroizii ca parte a unui algoritm pentru a enumera eficient toate ordinele de excludere perfecte pentru un anumit graf cordal.
O altă aplicație pentru ordinea perfectă a eliminării este găsirea clicei maxime a unui graf cordal în timp polinomial, în timp ce pentru graficele generale aceeași problemă este NP-complet (un graf cordal poate avea doar liniar multe clicuri cele mai mari , în timp ce graficele non-cordale pot avea exponențial multe dintre ele). Pentru a obține o listă cu toate cele mai mari clicuri ale unui graf cordal, este suficient să găsiți ordinea perfectă de eliminare, să construiți o clică pentru fiecare vârf v din toate vârfurile învecinate în ordine după v și să verificați dacă clica rezultată este cea mai mare.
Cea mai mare clică care are dimensiunea maximă este clica maximă și, deoarece graficele de acorduri sunt perfecte, dimensiunea acestei clici este egală cu numărul cromatic al graficului de acorduri. Graficele de acorduri sunt bine ordonate - colorarea optimă poate fi obținută folosind algoritmul de colorare greedy , luând vârfurile în ordine inversă până la eliminarea perfectă. [9]
În orice graf , un separator de vârfuri este un set de vârfuri a căror eliminare face ca graficul rămas să fie deconectat. Un separator este minim dacă nu conține un subset care este și separator. Conform teoremei lui Dirac [1] , graficele cordale sunt grafice în care fiecare separator minim este o clică. Dirac a folosit această caracteristică pentru a demonstra că graficele de acorduri sunt perfecte .
O familie de grafuri de acorduri poate fi definită ca un set de grafuri ale căror vârfuri pot fi împărțite în trei submulțimi nevide A , S și B , astfel încât A ∪ S și S ∪ B formează ambele subgrafe generate de acorduri , S este o clică, și nu există margini care să conecteze A și B. _ Astfel, acestea sunt grafice care permit partiționarea recursivă în subgrafe mai mici folosind clicuri. Din acest motiv, grafurile cordale sunt uneori numite grafuri descompuse . [zece]
O altă caracteristică a graficelor cordale [11] folosește arbori și subarborele lor.
Dintr-un set de subarbori ai unui arbore, se poate determina un grafic subarboresc - un grafic de intersecție , al cărui vârf corespunde unui subarbore și o muchie conectează doi subarbori dacă au una sau mai multe muchii comune. Gavril a arătat că graficele subarbore sunt exact grafice cordale.
Reprezentarea graficelor cordale ca un grafic de intersecție subarboresc formează o descompunere a graficului în copaci cu o lățime a arborelui cu o lățime mai mică decât dimensiunea celei mai mari clicuri a graficului. Descompunerea oricărui graf G în arbori poate fi considerată ca o reprezentare a grafului G ca un subgraf al grafului cordal. Descompunerea unui grafic în arbori este, de asemenea, un arbore de unire în algoritmul de propagare a încrederii .
Graficele cu intervale sunt grafice de intersecție subarbore , un caz special de arbori. Astfel, graficele de intervale sunt o subfamilie de grafice de acorduri.
Graficele divizate sunt ambele cordale în sine și sunt complemente ale graficelor cordale. Bender, Richmond și Wormald (1985) [12] au arătat că, pe măsură ce n tinde spre infinit, fracția graficelor cordale cu n vârfuri care sunt împărțite tinde spre unu.
Graficele Ptolemeu sunt grafice care sunt atât cordale, cât și moștenite la distanță . Graficele cvasi-prag sunt o subclasă de grafice ptolemeice care sunt atât cordale, cât și cograf . Graficele bloc sunt o altă subclasă de grafice ptolemeice în care oricare două mai mari clicuri au cel mult un vârf comun. Un caz special sunt morile , care au același vârf pentru orice pereche de clicuri.
Graficele strict cordale sunt grafice care sunt cordale și nu conțin un n-soare ( n ≥ 3) ca subgrafe generate.
Arborii K sunt grafice de acorduri ale căror mai mari clicuri și cei mai mari separatori de clicuri au toate aceeași dimensiune. [13] Graficele Apollonius sunt grafice planare maxime de acorduri sau, echivalent, 3-arbori planari. [13] Graficele maxime exterioare sunt o subclasă de 2 arbori și, prin urmare, de asemenea, cordale.
Graficele cordale sunt o subclasă de grafice perfecte bine-cunoscute . Alte superclase de grafuri cordale includ grafuri cordale slabe, grafuri fără găuri impare și grafuri fără găuri pare . De fapt, graficele cordale sunt exact grafice, atât fără găuri pare, cât și fără găuri impare (vezi gaura în teoria grafurilor).
Orice graf cordal este contractat , adică un graf în care orice ciclu periferic este un triunghi, deoarece ciclurile periferice sunt un caz special al unui ciclu generat. Graficele contractate pot fi formate din sume de clicuri de grafice de acorduri și grafice de acorduri maxime. Astfel, grafurile contractate includ grafurile planare maxime . [paisprezece]