Omeomorfismo (teoria dei grafi)

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.

Premessa

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.

Esempio

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.

Considerazione di complessità

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.

Bibliografia

• Jay Yellen, Jonatan L. Gross: Graph Theory and Its Applications, Chapman & Hall / CRC, (2005) 2nd edition, ISBN 978-1-58488-505-4

Voci correlate

• Teoria dei grafi
• Minore (teoria dei grafi)

Collegamenti esterni

• (EN) Eric W. Weisstein, Omeomorfismo, su MathWorld, Wolfram Research.