Teoria algebrica dei grafi
# Teoria algebrica dei 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.

## Branche della teoria algebrica dei grafi

### Usare l'algebra lineare

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. Aspetti degli spettri dei grafi sono stati usati nell'analisi della sincronizzabilità delle reti.

### Usare la teoria dei gruppi

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). 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.

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 (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.

### Studiare le invarianti dei grafi

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 è $t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$. 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.

