Grafo poliedrico
# 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

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. La scomposizione può essere effettuata con una tecnica di Tutte embedding.

## Cammino hamiltoniano e grado di somiglianza delle famiglie di grafi

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

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^α).$

## Enumerazione combinatoria

Duijvestijn fornisce un conteggio dei grafi poliedrici con un massimo di 26 spigoli. 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).

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)

## Casi particolari

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.

