|
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 termini, è un grafo planare connesso su 3 vertici. CaratterizzazioneIl 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 grafiLa 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 combinatoriaDuijvestijn fornisce un conteggio dei grafi poliedrici con un massimo di 26 spigoli.[8] Il numero di questi grafi con 6, 7, 8,... spigoli è:
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 è:
Casi particolariUn 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. Note
Altri progetti
Collegamenti esterni
|
Portal di Ensiklopedia Dunia
