Grafo poliedrico
Nell'ambito della teoria dei grafi, un grafo poliedrico è un grafo non orientato formato dai vertici e dagli spigoli di un poligono convesso. In altri temini, è un grafo planare connesso su 3 vertici.
Caratterizzazione modifica
Il diagramma di Schlegel di un poliedro convesso rappresenta i suoi vertici e spigoli rispettivamente come punti e segmenti del piano euclideo, suddividendo un poligono convesso in poligoni convessi più piccoli. Essendo privo di segmenti che si intersecano in uno o più punti (incroci), ogni grafo poliedrico è anche un grafo planare. Per il teorema di Balinski, è un grafo connesso a 3 vertici.
Per il teorema di Steinitz, queste due proprietà teoriche dei grafi sono una condizione sufficienti per caratterizzare completamente i grafi poliedrici, definendoli come grafi planari connessi su 3 vertici: pertanto, per ogni grafo planare di 3 vertici, esiste un poliedro i cui vertici e spigoli formano un grafo isomorfo.[1][2] La scomposizione può essere effettuata con una tecnica di Tutte embedding.[3][4]
Cammino hamiltoniano e grado di somiglianza delle famiglie di grafi modifica
La congettura di Tait, secondo la quale ogni grafo poliedrico cubico (cioè un grafo poliedrico in cui ogni vertice è l'estremo geometrico di tre spigoli) dovrebbe possedere cammino hamiltoniano, fu smentita da un controesempio diel matematico e crittografo William Thomas Tutte, che costruì un grafo poliedrico non hamiltoniano. Se si prendono in considerazione grafi non cubici, esistono grafi poliedrici non Hamiltoniani molto più piccoli: quello con il minor numero di vertici e spigoli è il grafo Herschel a 11 vertici e 18 spigoli.[5] Inoltre, esiste anche un grafo poliedrico non hamiltoniano a 11 vertici in cui tutte le facce sono triangoli, il grafo di Goldner-Harary, che presenta tuttavia un numero di spigoli superiore.[6]
Per quanto riguarda il parametro costante shortness exponent, che misura la distanza di una famiglia di grafi dal cammino hamiltoniano, esiste una famiglia infinita di grafi poliedrici aventi α < 1, tali che la lunghezza del cammino semplice più esteso per ogni grafo di n vertici appartenente all'insieme, sia O(nα).[7]
Enumerazione combinatoria modifica
Duijvestijn fornisce un conteggio dei grafi poliedrici con un massimo di 26 spigoli.[8] Il numero di questi grafi con 6, 7, 8,... spigoli è:
- 1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1.342, 4.199, 13.384, 43.708, 144.810, ... (successione descritta col codice A002840 nel progetto OEIS).[9]
Inoltre, è possibile anche enumerare i grafi poliedrici in base al numero di vertici. Per i grafi con 4, 5, 6, ..., vertici il corrispondente numero di grafi poliedrici è:
- 1, 2, 7, 34, 257, 2.606, 32.300, 440.564, 6.384.634, 96.262.938, 1.496.225.352, ... (successione A000944 in OEIS)[10]
Casi particolari modifica
Un grafo poliedrico è il grafo di un politopo semplice se è cubico (vale a dire se ogni vertice ha tre spigoli), ed è il grafo di un politopo simpliciale (vale a dire le cui facce sono tutte semplici se è un grafo planare massimale.
I grafi di Halin sono una sottoclasse importante di grafi poliedrici, costituiti da un grafo planare ad grafo le cui foglie sono tutte connesse da un ciclo esterno.
Note modifica
- ^ Lectures on Polytopes, di Günter M. Ziegler (1995) isbn 0-387-94365-X, al capitolo 4- "Steinitz' Theorem for 3-Polytopes", p. 103.
- ^ Branko Grünbaum, Convex Polytopes, Graduate Texts in Mathematics, vol. 221, 2nd, Springer-Verlag, 2003, ISBN 978-0-387-40409-7..
- ^ W. T. Tutte, How to draw a graph, in Proceedings of the London Mathematical Society, vol. 13, 1963, pp. 743–767, DOI:10.1112/plms/s3-13.1.743, MR 0158387..
- ^ Al riguardo, si può consultare la voce Tutte embedding presente nella Wikipedia in inglese.
- ^ Grafo di Herschel, su mathworld.wolfram.com.
- ^ Goldner-Harary Graph, su mathworld.wolfram.com.
- ^ Branko Grünbaum e T. S. Motzkin, Longest simple paths in polyhedral graphs, in Journal of the London Mathematical Society, s1-37, n. 1, 1962, pp. 152–160, DOI:10.1112/jlms/s1-37.1.152..
- ^ A. J. W. Duijvestijn, The number of polyhedral (3-connected planar) graphs (PDF), in Mathematics of Computation, vol. 65, 1996, pp. 1289–1293, DOI:10.1090/S0025-5718-96-00749-1..
- ^ Successione A002840 nel progetto OEIS, su oeis.org.
- ^ Successione A000944 in OEIS, su oeis.org.
Altri progetti modifica
Wikimedia Commons contiene immagini o altri file su grafo poliedrico
Collegamenti esterni modifica
- (EN) I grafi poliedrici, su MathWorld.
