Grafo cubico

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
Il grafo di Petersen è un grafo cubico
Il grafo bipartito completo è un esempio di grafo bicubico

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.

Simmetria[modifica | modifica wikitesto]

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.

Colorazione e insiemi indipendenti[modifica | modifica wikitesto]

Secondo il teorema di Brooks ogni grafo cubico diverso dal grafo completo K4 può essere colorato al massimo con tre colori. Perciò, ogni grafo cubico diverso da K4 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]

Topologia e geometria[modifica | modifica wikitesto]

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]

Hamiltonicità[modifica | modifica wikitesto]

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 2n/3 (approssimativamente 1.260n) 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.276n.[10]

Altre proprietà[modifica | modifica wikitesto]

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 2n/3656 abbinamenti perfetti.[13]

Algoritmi e complessità[modifica | modifica wikitesto]

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(2n/6 + o(n)).[11] Il problema del commesso viaggiatore può essere risolto in grafi cubici nel tempo O(1.251n).[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]

Note[modifica | modifica wikitesto]

  1. ^ R. M. Foster, Geometrical Circuits of Electrical Networks, in Transactions of the American Institute of Electrical Engineers, vol. 51, n. 2, 1932, 309–317, DOI:10.1109/T-AIEE.1932.5056068.
  2. ^ W. T. Tutte, On the symmetry of cubic graphs, in Canad. J. Math, vol. 11, 1959, 621–624, DOI:10.4153/CJM-1959-057-2. URL consultato il 12 febbraio 2014 (archiviato dall'url originale il 16 luglio 2011).
  3. ^ R. Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, in American Mathematical Monthly, vol. 82, n. 3, 1975, 221–239, DOI:10.2307/2319844, JSTOR 2319844.
  4. ^ C. Paul Bonnington e Charles H. C. Little, The Foundations of Topological Graph Theory, Springer-Verlag, 1995.
  5. ^ Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 240, 1976.
  6. ^ Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.
  7. ^ M. N. Ellingham e J. D. Horton, Non-Hamiltonian 3-connected cubic bipartite graphs, in Journal of Combinatorial Theory, Series B, vol. 34, n. 3, 1983, pp. 350–353, DOI:10.1016/0095-8956(83)90046-1.
  8. ^ R.W. Robinson e N.C. Wormald, Almost all regular graphs are Hamiltonian, in Random Structures and Algorithms, vol. 5, n. 2, 1994, pp. 363–374, DOI:10.1002/rsa.3240050209.
  9. ^ David Eppstein, The traveling salesman problem for cubic graphs (PDF), in Journal of Graph Algorithms and Applications, vol. 11, n. 1, 2007, pp. 61–81, arXiv:cs.DS/0302030.
  10. ^ H. Gebauer, On the number of Hamilton cycles in bounded degree graphs (PDF), in Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08)[collegamento interrotto], 2008.
  11. ^ a b Fedor V. Fomin e Kjartan Høie, Pathwidth of cubic graphs and exact algorithms, in Information Processing Letters, vol. 97, n. 5, 2006, pp. 191–196, DOI:10.1016/j.ipl.2005.10.012.
  12. ^ Julius Peter Christian Petersen, Die Theorie der regulären Graphs (The theory of regular graphs), in Acta Mathematica, vol. 15, n. 15, 1891, pp. 193–220, DOI:10.1007/BF02392606.
  13. ^ Louis Esperet, František Kardoš, Andrew D. King, Daniel Král e Serguei Norine, Exponentially many perfect matchings in cubic graphs, in Advances in Mathematics, vol. 227, n. 4, 2011, pp. 1646–1664, DOI:10.1016/j.aim.2011.03.015.
  14. ^ Kazuo Iwama e Takuya Nakashima, An Improved Exact Algorithm for Cubic Graph TSP, in Computing and Combinatorics, Lecture Notes in Computer Science, vol. 4598, Springer-Verlag, 2007, pp. 108–117, DOI:10.1007/978-3-540-73545-8_13, ISBN 978-3-540-73544-1.
  15. ^ Paola Alimonti e Viggo Kann, Some APX-completeness results for cubic graphs, in Theoretical Computer Science, vol. 237, 1–2, 2000, pp. 123–134, DOI:10.1016/S0304-3975(98)00158-3.
  16. ^ Petr Hliněný, Crossing number is hard for cubic graphs, in Journal of Combinatorial Theory, Series B, vol. 96, n. 4, 2006, pp. 455–471, DOI:10.1016/j.jctb.2005.09.009.
  17. ^ Marek Karpinski e Richard Schmied, Approximation Hardness of Graphic TSP on Cubic Graphs, 2013, arXiv:1304.6800.

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica
Estratto da "https://it.wikipedia.org/w/index.php?title=Grafo_cubico&oldid=137294294"