Grafo poliedrico
grafo non orientato formato da vertici e spigoli di un poligono convesso Da Wikipedia, l'enciclopedia libera
grafo non orientato formato da vertici e spigoli di un poligono convesso Da Wikipedia, l'enciclopedia libera
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.
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]
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]
Duijvestijn 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 è:
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
