Cograf

În teoria grafurilor, un cograf , sau un graf reductibil suplimentar , sau un graf liber de P 4 ,  este un graf care poate fi obținut dintr-un graf cu un singur vârf K 1 prin operații de adunare și unire de graf . Astfel, o familie de cografe este cea mai mică clasă de grafuri care conține K 1 și este închisă sub complement și uniune.

Cographele au fost descoperite independent de mai mulți autori începând cu anii 1970. Cele mai vechi mențiuni pot fi găsite în Young [1] , Lerchs [2] , Zainsche [3] și Sumner [4] . Aceste grafice au fost numite D*-graphs [1] , grafice Dacey ereditare (după munca lui James C. Dacey, Jr. asupra rețelelor ortomodulare . Vezi Sumner [4] ) și grafice cu doi descendenți ai lui Barlet și Ury [ 5] .

Consultați cartea lui Brandstedt, Lie și Spinrad [6] pentru o discuție mai detaliată a cografelor, inclusiv a faptelor prezentate aici.

Definiție și descriere

Orice cograf poate fi construit urmând următoarele reguli:

  1. Orice vârf al unui graf este un cograf;
  2. Dacă  este un cograf, atunci complementul său este, de asemenea, un cograf;
  3. Dacă și  sunt cografe, atunci uniunea lor disjunctă este, de asemenea, un cograf.

Mai multe alte descrieri ale cografelor pot fi date. Printre ei:

Toate graficele complete , graficele bipartite complete, graficele de prag și graficele Turan sunt cografe. Orice cograf este un grafic de comparabilitate perfectă moștenit de distanță .

Codetrees

Un arbore de cod  este un arbore ale cărui vârfuri interne sunt etichetate cu 0 și 1. Orice arbore de coduri T definește un cograf G care are frunzele lui T ca vârfuri, iar un subarboresc înrădăcinat la T corespunde unui subgraf generat în G definit de un set de frunze descendente. acest top:

O modalitate echivalentă de a construi un cograf dintr-un codificator este aceea că două vârfuri sunt conectate printr-o muchie dacă și numai dacă strămoșul cel mai puțin comun al frunzelor corespunzătoare este etichetat cu 1. În schimb, orice cograf poate fi reprezentat de un codificator în acest fel. Dacă solicităm ca toate etichetele de pe toate căile de la rădăcină la frunze să se alterneze, o astfel de reprezentare va fi unică [7] .

Proprietăți computaționale

Un cograf poate fi recunoscut în timp liniar și o reprezentare coderee poate fi construită folosind descompunerea modulară [10] , rafinarea descompoziției [11] , sau descompunerea divizată [12] . Odată ce codificatorul a fost construit, multe probleme familiare ale teoriei grafurilor pot fi rezolvate prin parcurgerea codificatorului de jos în sus.

De exemplu, pentru a găsi clica maximă într-un cograf, calculăm, mergând de jos în sus, clica maximă din fiecare subgraf reprezentată de un subarboresc al codificatorului. Pentru fiecare vârf etichetat 0, clica maximă este clica maximă primită de la descendenții vârfului. Pentru un vârf etichetat 1, clica maximă va fi uniunea clicurilor calculată pentru descendenții vârfului, iar dimensiunea acestei clici este suma mărimii clicurilor. Astfel, luând alternativ dimensiunea maximă și însumând valorile pentru fiecare vârf al codificatorului, vom calcula dimensiunea maximă a clicei și, alegând alternativ clica maximă și concatenând, vom construi clica maximă în sine. O abordare similară de jos în sus permite obținerea mulțimii independente maxime , a numărului cromatic , a acoperirii maxime a clicei și a existenței unei căi hamiltoniene în timp liniar. De asemenea, se pot folosi cotrees pentru a determina în timp liniar dacă două cografe sunt izomorfe .

Dacă H  este un subgraf generat al unui cograf G , atunci H însuși este un cograf. Un codificator pentru H poate fi obținut prin eliminarea unora dintre frunzele codificatorului pentru G și apoi îmbinând vârfurile care au un singur copil. Din teorema arborelui lui Kruskal rezultă că relația care trebuie generată de un subgraf este o bună cvasi-ordine pe cografe [13] . Deci, dacă o familie de cografe (cum ar fi cografele plane ) este închisă sub operația de construire a unui subgraf generat, atunci are un număr finit de subgrafe interzise generate . Din punct de vedere computațional, aceasta înseamnă că verificarea dacă un graf aparține unei astfel de familii se poate face în timp liniar folosind o parcurgere de jos în sus a codificatorului grafului dat.

Note

  1. ↑ 1 2 3 Jung, 1978 .
  2. ↑ Lerchs, 1971 .
  3. ↑ Seinsche, 1974 .
  4. ↑ 12 Sumner , 1974 .
  5. ↑ Burlet, Uhry, 1984 .
  6. ↑ Brandstädt, Le, Spinrad, 1999 .
  7. ↑ 1 2 Corneil, Lerchs, Burlingham, 1981 .
  8. ↑ Courcelle, Olariu, 2000 .
  9. ↑ Bose, Buss, Lubiw, 1998 .
  10. ↑ Corneil, Perl, Stewart, 1985 .
  11. ↑ Habib, Paul, 2005 .
  12. ↑ Gioan, Paul, 2008 .
  13. ↑ Damaschke, 1990 .

Literatură

Link -uri