Omeomorfismo (teoria dei grafi)
Da Wikipedia, l'enciclopedia libera
Due grafi G e H si dicono omeomorfi se e solo se esiste un isomorfismo tra due loro suddivisioni di spigoli G' e H'.
In maniera equivalente, si possono definire omeomorfi due grafi G e H se e solo se possono essere ottenuti da uno stesso grafo K mediante due sequenze (finite) di suddivisioni elementari di spigoli.
Per suddivisione elementare di spigoli di un grafo si intende un'operazione che modifica un suo spigolo {u,v} in due spigoli {u,w} e {w,v} incidenti in un nuovo vertice w. Questa operazione si può descrivere anche come inserimento di un nuovo nodo in uno spigolo.
Per suddivisione di spigoli di un grafo si intende sia l'operazione consistente in una o più suddivisioni elementari, che il grafo ottenuto con tale manovra.
Esaminiamo i due grafi seguenti per constatare che sono omeomorfi.
G 
H 
Chiamiamo G' il grafo ottenuto da G suddividendo ciascuno degli spigoli aventi un vertice di grado 2 (spigoli "esterni") e H' il grafo ottenuto da H suddividendo il suo spigolo avente i due estremi di grado 3 (spigolo "interno"). Questi due grafi hanno una stessa raffigurazione:
G', H' 
Quindi, evidentemente, esiste un isomorfismo tra G' e H' (in effetti ne esistono due) e, di conseguenza, per la seconda delle definizioni date, G e H sono omeomorfi.
Consideriamo la seconda definizione equivalente. Eliminando da G l'unico vertice di grado 2 e da H quattro dei suoi vertici di grado 2 scelti in modo da mantenere il carattere di grafo semplice, si individua un grafo K con due vertici di grado 3 e due di grado 2, dal quale si possono ottenere per suddivisione i grafi G e H. Anche in questo modo si può quindi affermare l'omeomorfismo tra G e H.
Dati due grafi G e H, si pone il problema di stabilire se H sia omeomorfo ad un sottografo di G. Tale problema si dimostra essere NP-completo.
- Jay Yellen, Jonatan L. Gross: Graph Theory and Its Applications, Chapman & Hall / CRC, (2005) 2nd edition, ISBN 978-1-58488-505-4
- Teoria dei grafi
- Minore (teoria dei grafi)
- (EN) Eric W. Weisstein, Omeomorfismo, su MathWorld, Wolfram Research.
Wikiwand in your browser!
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.
