Teoria algebrică a grafurilor

Teoria algebrică a grafurilor este o ramură a matematicii în care se aplică metode algebrice la problemele despre grafuri. Aceasta este în contrast cu abordările geometrice, combinatoriale sau algoritmice. Există trei ramuri principale ale teoriei algebrice a grafurilor, care implică utilizarea algebrei liniare, utilizarea teoriei grupurilor și studiul invarianților grafurilor.

Ramuri ale teoriei algebrice a grafurilor

Utilizând algebra liniară

Prima ramură a teoriei algebrice a grafurilor implică studiul grafurilor cu ajutorul algebrei liniare. Studiază în special spectrul matricii de adiacență sau matricea laplaciană a unui graf (această parte a teoriei algebrice a grafurilor este numită și teoria spectrală a grafurilor). Pentru graful lui Petersen, de exemplu, spectrul matricii de adiacență este (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Mai multe teoreme leagă proprietățile spectrului de alte proprietăți ale grafului. Ca exemplu simplu, un graf conex cu diametrul D va avea cel puțin D+1 valori distincte în spectrul său.^[1] Aspecte ale spectrelor de grafuri au fost utilizate în analizarea sincronizării rețelelor.

Utilizând teoria grupurilor

A doua ramură a teoriei algebrice a grafurilor implică studiul grafurilor în conexiune cu teoria grupurilor, în particular grupurile de automorfisme și teoria geometrică a grupurilor. Accentul este pus pe diferite familii de grafuri în funcție de simetrie (cum ar fi grafurile simetrice, grafurile nod-tranzitive, grafurile muchie-tranzitive, grafurile distanță-tranzitive, grafurile distanță-regulate și grafurile tare regulate) și de relațiile de incluziune dintre aceste familii. Unele dintre aceste categorii de grafuri sunt suficient de răsfirate încât să se poată întocmi liste de grafuri. Conform teoremei lui Frucht, toate grupurile pot fi reprezentate drept grupul de automorfisme al unui graf conex (într-adevăr, al unui graf cubic).^[2] O altă legătură cu teoria grupurilor este că, fiind dat orice grup, pot fi generate grafuri simetrice cunoscute sub numele de grafuri Cayley, iar acestea au proprietăți legate de structura grupului.^[1]

Un graf Cayley pentru grupul altern A₄, formând un tetraedru trunchiat în trei dimensiuni. Toate grafurile Cayley sunt nod-tranzitive, dar unele grafuri nod-tranzitive (cum ar fi graful lui Petersen) nu sunt grafuri Cayley.

O colorare proprie a nodurilor grafului lui Petersen cu 3 culori, numărul minim posibil. Conform polinomului cromatic, există 120 de astfel de colorări cu 3 culori.

Această a doua ramură a teoriei algebrice a grafurilor este legată de prima, deoarece proprietățile de simetrie ale unui graf sunt reflectate în spectrul său. În particular, spectrul unui graf foarte simetric, cum ar fi graful lui Petersen, are puține valori distincte^[1] (graful lui Petersen are 3, care este minimul posibil, având în vedere diametrul său). Pentru grafurile Cayley, spectrul poate fi legat direct de structura grupului, în particular de caracterele sale ireductibile.^[1]^[3]

Studiind invarianții grafului

A treia ramură a teoriei algebrice a grafurilor se referă la proprietățile algebrice ale invarianților grafurilor, și în special la polinomul cromatic, polinomul Tutte și invarianții de noduri. Polinomul cromatic al unui graf numără, de exemplu, numărul de colorări proprii ale nodurilor. Pentru graful lui Petersen acest polinom este $t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$ .^[1] În particular, aceasta înseamnă că graful lui Petersen nu poate fi colorat propriu cu una sau două culori, dar poate fi colorat în 120 de moduri diferite cu 3 culori. Multe lucrări în acest domeniu al teoriei algebrice a grafurilor au fost motivate de încercările de a demonstra teorema celor patru culori. Cu toate acestea, există încă multe probleme deschise, cum ar fi caracterizarea grafurilor care au același polinom cromatic sau a determina care polinoame sunt cromatice.

Vezi și

Note

^ ^a ^b ^c ^d ^e Biggs, Norman (1993), Algebraic Graph Theory (ed. 2nd), Cambridge University Press, ISBN 0-521-45897-8, Zbl 0797.05032
^ Frucht, R. (1949), „Graphs of Degree 3 with given abstract group”, Can. J. Math., 1 (4), pp. 365–378, doi:10.4153/CJM-1949-033-6 
^ *Babai, L (1996), „Automorphism groups, isomorphism, reconstruction”, În Graham, R; Grötschel, M; Lovász, L, Handbook of Combinatorics, Elsevier, pp. 1447–1540, ISBN 0-444-82351-4, Zbl 0846.05042, arhivat din original la 11 iunie 2010, accesat în 27 martie 2009

Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, Graduate Texts in Mathematics, 207, Springer, ISBN 0-387-95220-9, Zbl 0968.05002 .

[biggs-1] Biggs, Norman (1993), Algebraic Graph Theory (ed. 2nd), Cambridge University Press, ISBN 0-521-45897-8, Zbl 0797.05032

[2] Frucht, R. (1949), „Graphs of Degree 3 with given abstract group”, Can. J. Math., 1 (4), pp. 365–378, doi:10.4153/CJM-1949-033-6 

[babai-3] *Babai, L (1996), „Automorphism groups, isomorphism, reconstruction”, În Graham, R; Grötschel, M; Lovász, L, Handbook of Combinatorics, Elsevier, pp. 1447–1540, ISBN 0-444-82351-4, Zbl 0846.05042, arhivat din original la 11 iunie 2010, accesat în 27 martie 2009

[1]

[2]

[3]