Loading AI tools
branca della matematica in cui si applicano metodi algebrici a problemi concernenti i grafi Da Wikipedia, l'enciclopedia libera
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.
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.
La seconda branca della teoria algebrica dei grafi coinvolge lo studio dei grafi in connessione con la teoria dei gruppi, particolarmente i gruppi di automorfismo 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]
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]
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
