Grafo cubico

Nel campo matematico della teoria dei grafi, un grafo cubico è un grafo in cui tutti i vertici hanno grado tre. In altre parole un grafo cubico è un grafo 3-regolare. I grafi cubici sono chiamati anche grafi trivalenti.

Un grafo bicubico è un grafo bipartito cubico.

Nel 1932, Ronald M. Foster cominciò a raccogliere esempi di grafi simmetrici cubici, creando il primo nucleo dell'archivio del censimento Foster (Foster census).^[1] Molti ben noti grafi individuali sono cubici e simmetrici, compresi il grafo dei servizi, il grafo di Petersen, il grafo di Heawood, il grafo di Möbius-Kantor, il grafo di Pappus, il grafo di Desargues, il grafo di Nauru, il grafo di Coxeter, il grafo di Tutte-Coxeter, il grafo di Dyck, il grafo di Foster e il grafo di Biggs-Smith. William Thomas Tutte classificò i grafi cubici simmetrici in base al più piccolo numero integrale s tale che ogni due sentieri orientati di lunghezza s possono essere mappati l'uno con l'altro esattamente in base a una simmetria del grafo. Egli mostrò che s è al massimo 5 e fornì esempi di grafi con ogni possibile valore di s da 1 a 5.^[2]

I grafi cubici semisimmetrici includono il grafo di Gray (il più piccolo grafo cubico semisimmetrico), il grafo di Ljubljana e la 12-gabbia di Tutte.

Il grafo di Frucht è uno dei più piccoli grafi cubici senza simmetrie: possiede soltanto un unico automorfismo di grafo, l'identità di automorfismo.

Secondo il teorema di Brooks ogni grafo cubico diverso dal grafo completo K₄ può essere colorato al massimo con tre colori. Perciò, ogni grafo cubico diverso da K₄ ha un insieme indipendente di almeno n/3 vertici, dove n è il numero di vertici del grafo: ad esempio, la più grande classe di colore in una 3-colorazione ha almeno altrettanti vertici.

Secondo il teorema di Vizing ogni grafo cubico ha bisogno di tre o di quattro colori per una colorazione degli spigoli. Una 3-colorazione degli spigoli è nota come colorazione di Tait e forma una partizione degli spigoli del grafo in tre accoppiamenti perfetti. Per il teorema della colorazione delle linee di König ogni grafo bicubico ha una colorazione di Tait.

I grafi cubici senza ponti che non hanno una colorazione di Tait sono noti come snark. Essi includono il grafo di Petersen, il grafo di Tietze, gli snark di Blanuša, lo snark dei fiori, lo snark con la doppia stella, lo snark di Szekeres e lo snark di Watkins. C'è un numero infinito di snark distinti.^[3]

I grafi cubici sorgono naturalmente nella topologia in parecchi modi. Ad esempio, se si considera un grafo come un complesso di celle unidimensionale, i gradi cubici sono generici in quanto la maggior parte delle mappe annesse a una cella sono disgiunte dallo 0-scheletro del grafo. Anche i grafi cubici sono formati in tre dimensioni come i grafi dei poliedri semplici, poliedri quali il dodecaedro regolare con la proprietà che queste tre facce s'incontrino ad ogni vertice.

Un'incorporazione dei grafi (embedding) su una superficie bidimensionale può essere rappresentata come una struttura di grafi cubici conosciuta come mappa codificata dei grafi. In questa struttura, ogni vertice di un grafo cubico rappresenta una bandiera dell'incorporazione, un triplo reciprocamente incidente di un vertice, uno spigolo e una faccia della superficie. I tre vicini di ogni bandiera sono le tre bandiere che si possono ottenere da essa cambiando uno dei membri di questo triplo mutuamente incidente e lasciando gli altri due membri immutati.^[4]

Si sono fatte molte ricerche sull'hamiltonicità dei grafi cubici. Nel 1880, P.G. Tait congetturò che ogni grafo poliedrico cubico ha un circuito hamiltoniano. William Thomas Tutte fornì un controesempio alla congettura di Tait, il grafo di Tutte a 46 vertici, nel 1946. Nel 1971, Tutte congetturò che tutti i grafici bicubici sono hamiltoniani. Tuttavia, Joseph Horton fornì un controesempio su 96 vertici, il grafo di Horton.^[5] Più tardi, Mark Ellingham costruì altri due controesempi: i grafi di Ellingham-Horton.^[6][7] La congettura di Barnette, una combinazione ancora aperta della congettura di Tait e di quella di Tutte, afferma che ogni grafo poliedrico bicubico è hamiltoniano. Quando un grafico cubico è hamiltoniano, la notazione LCF permette di rappresentarlo concisamente.

Se un grafo cubico è scelto uniformemente in modo aleatorio fra tutti i grafi cubici con n vertici, allora è molto probabile che sia hamiltoniano: la proporzione dei grafi cubici con n vertici che sono hamiltoniani tende al limite a uno quando n va a infinito.^[8]

David Eppstein congetturò che ogni grafo cubico con n vertici ha al massimo 2^n/3 (approssimativamente 1.260ⁿ) cicli hamiltoniani distinti, e fornì esempi di grafi cubici con altrettanti cicli.^[9] Il miglior limite superiore che è stato dimostrato sul numero di distinti cicli hamiltoniani è 1.276ⁿ.^[10]

L'ampiezza del cammino di qualsiasi grafo cubico con n vertici è al massimo di n/6. Tuttavia, il miglior limite inferiore conosciuto sull'ampiezza del cammino dei grafi cubici è più piccolo, 0,082n.^[11]

Consegue dal lemma delle strette di mano, dimostrato da Eulero nel 1736 come parte del primo studio sulla teoria dei grafi, che ogni grafo cubico ha un numero pari di vertici.

Il teorema di Petersen afferma che ogni grafo privo di ponti ha un accoppiamento perfetto.^[12] Lovász e Plummer congetturarono che ogni grafo cubico privo di ponti ha un numero esponenziale di abbinamenti perfetti. La congettura è stata provata recentemente, mostrando che ogni grafo cubico privo di ponti con n vertici ha almeno 2^n/3656 abbinamenti perfetti.^[13]

Parecchi ricercatori hanno studiato la complessità degli algoritmi del tempo esponenziale limitati ai grafi cubici. Ad esempio, applicando la programmazione dinamica a una scomposizione dei cammini del grafo, Fomin and Høie mostrarono come trovare i loro massimi insiemi indipendenti nel tempo O(2^n/6 + o(n)).^[11] Il problema del commesso viaggiatore può essere risolto in grafi cubici nel tempo O(1.251ⁿ).^[14]

Parecchi importanti problemi di ottimizzazione dei grafi sono APX difficili, che significa che, sebbene abbiano algoritmi di approssimazione il cui rapporto di approssimazione è limitato da una costante, essi non hanno schemi di approssimazione del tempo polinomiali il cui rapporto di approssimazione tende a 1 a meno che P=NP. Questi includono i problemi di trovare una copertura dei vertici, un massimo insieme indipendente, un minimo insieme dominante e un taglio massimo.^[15] Il numero di incroci (il numero minimo di spigoli che si incrociano in qualsiasi raffigurazione di un grafo) di un grafo cubico è anche NP-difficile per i gradi cubici ma può essere approssimato.^[16] Si è provato che il problema del commesso viaggiatore sui grafi cubici è NP-difficile da approssimare entro un qualsiasi fattore minore di to within any 1.153/1.152.^[17]

• Wikimedia Commons contiene immagini o altri file su grafo cubico

• (EN) Eric W. Weisstein, Grafo cubico, su MathWorld, Wolfram Research.
• (EN) Gordon Royle, Cubic symmetric graphs (The Foster Census), su mapleta.maths.uwa.edu.au (archiviato dall'url originale il 23 ottobre 2011).

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica