b'\n_START_ARTICLE_\nOmeomorfismo (teoria dei grafi)\n_START_PARAGRAPH_\nDue grafi G e H si dicono omeomorfi se e solo se esiste un isomorfismo tra due loro suddivisioni di spigoli G\' e H\'._NEWLINE_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.\n_START_SECTION_\nPremessa\n_START_PARAGRAPH_\nPer 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\xc3\xb2 descrivere anche come inserimento di un nuovo nodo in uno spigolo._NEWLINE_Per suddivisione di spigoli di un grafo si intende sia l\'operazione consistente in una o pi\xc3\xb9 suddivisioni elementari, che il grafo ottenuto con tale manovra.\n_START_SECTION_\nEsempio\n_START_PARAGRAPH_\nEsaminiamo i due grafi seguenti per constatare che sono omeomorfi._NEWLINE_G _NEWLINE_H _NEWLINE_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:_NEWLINE_G\', H\' _NEWLINE_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._NEWLINE_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\xc3\xb2 quindi affermare l\'omeomorfismo tra G e H.\n_START_SECTION_\nConsiderazione di complessit\xc3\xa0\n_START_PARAGRAPH_\nDati 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.'