Teoria algebrica dei grafi

branca della matematica in cui si applicano metodi algebrici a problemi concernenti i grafi

La teoria algebrica dei grafi è una branca della matematica in cui si applicano metodi algebrici a problemi concernenti i grafi. Ciò è in contrasto con l'approccio geometrico, combinatorio o algoritmico. Ci sono tre branche principali della teoria algebrica dei grafi, che implicano l'uso dell'algebra lineare, l'uso della teoria dei gruppi e lo studio delle invarianti dei grafi.

Un grafo altamente simmetrico, il grafo di Petersen, che è transitivo sui vertici, simmetrico, transitivo sulla distanza e regolare sulla distanza. Ha diametro 2. Il suo gruppo di automorfismo ha 120 elementi, ed è infatti il gruppo simmetrico .

Branche della teoria algebrica dei grafi modifica

Usare l'algebra lineare modifica

La prima branca della teoria algebrica dei grafi coinvolge lo studio dei grafi in connessione con l'algebra lineare. In particolare, essa studia lo spettro della matrice delle adiacenze, o matrice laplaciana di un grafo (questa parte della teoria algebrica dei grafi è chiamata teoria spettrale dei grafi). Per il grafo di Petersen, ad esempio, la matrice delle adiacenze è (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Parecchi teoremi collegano le proprietà dello spettro ad altre proprietà dei grafi. Come esempio semplice, un grafo connesso di diametro D avrà almeno D+1 valori distinti nel suo spettro.[1] Aspetti degli spettri dei grafi sono stati usati nell'analisi della sincronizzabilità delle reti.

Usare la teoria dei gruppi modifica

La seconda branca della teoria algebrica dei grafi coinvolge lo studio dei grafi in connessione con la teoria dei gruppi, particolarmente i gruppi di automorpfismo e la teoria geometrica dei gruppi. L'attenzione è posta su varie famiglie di grafi basati sulla simmetria (come i grafi simmetrici, i grafi transitivi sui vertici, i grafi transitivi sugli spigoli, i grafi transitivi sulla distanza, i grafi regolari sulla distanza e i grafi fortemente regolari), e sulle relazioni di inclusione tra queste famiglie. Alcune di queste categorie di grafi sono abbastanza sparse perché possano essere stilate liste di grafi. Per il teorema di Frucht, tutti i gruppi possono essere rappresentati come il gruppo di automorfismo di un grafo connesso (in realtà, di un grafo cubico).[2] Un'altra connessione con la teoria dei gruppi è che, dato un qualsiasi gruppo, possono essere generati grafi simmetrici conosciuti come i grafi di Cayley, e questi hanno proprietà collegate alla struttura del gruppo.[1]

 
Un grafo di Cayley per il gruppo alternato A4, che forma un a tetraedro troncato in tre dimensioni. Tutti i grafi di Cayley sono transitivi sui vertici, ma alcuni grafi transitivi sui vertici (come il grafo di Petersen) non sono grafi di Cayley.
 
Una colorazione esatta dei vertici del grafo di Petersen con 3 colori, il numero minimo possibile. Secondo il polinomio cromatico, ci sono 120 colorazioni del genere con 3 colori.

Questa seconda branca della teoria algebrica dei grafi è collegata alla prima, poiché le proprietà di simmetria di un grafo sono riflesse nel suo spettro. In particolare, lo spettro di un grafo altamente simmetrico, come il grafo di Petersen, ha pochi valori distinti[1] (il grafo di Petersen ha 3, che è il minimo possibile, dato il suo diametro). Per i grafi di Cayley, lo spettro può essere collegato direttamente alla struttura del gruppo, in particolare ai suoi caratteri irriducibili.[1][3]

Studiare le invarianti dei grafi modifica

Infine, la terza branca della teoria algebrica dei grafi concerne le proprietà algebriche delle invarianti dei grafi, e specialmente il polinomio cromatico, il polinomio di Tutte e le invarianti dei nodi. Il polinomio cromatico di un grafo, per esempio, conta il numero delle sue colorazioni esatte dei vertici. Per il grafo di Petersen, questo polinomio è  .[1] In particolare, questo significa che il grafo di Petersen non può essere colorato esattamente con uno o due colori, ma può essere colorato in 120 modi diversi con 3 colori. Gran parte del lavoro in quest'area della teoria algebrica dei grafi era motivata dai tentativi di provare il teorema dei quattro colori. Tuttavia, ci sono ancora molti problemi aperti, come caratterizzare i grafi che hanno lo stesso polinomio cromatico e determinare quali polinomi sono cromatici.

Note modifica

  1. ^ a b c d e Biggs, Norman, Algebraic Graph Theory, 2ª ed., Cambridge, Cambridge University Press, 1993, ISBN 0-521-45897-8.
  2. ^ R. Frucht, Graphs of Degree 3 with given abstract group, «Canad. J. Math.», 3, 1949.
  3. ^ L. Babai, Automorphism groups, isomorphism, reconstruction (ps), in R. Graham, M. Groetschel e L. Lovasz (a cura di), Handbook of Combinatorics, Elsevier, 1996. URL consultato il 22 febbraio 2014 (archiviato dall'url originale l'11 giugno 2010).

Bibliografia modifica

  • Chris Godsil e Gordon Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207, New York, Springer-Verlag, 2001.

Voci correlate modifica

Altri progetti modifica

Controllo di autoritàGND (DE1201434165
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica