En teoría de grafos , dos grafos y son homeomórficos si hay un isomorfismo de grafos desde alguna subdivisión de hasta alguna subdivisión de . Si los bordes de un gráfico se consideran líneas dibujadas de un vértice a otro (como generalmente se representan en las ilustraciones), entonces dos gráficos son homeomórficos entre sí en el sentido de la teoría de grafos, precisamente si son homeomórficos en el sentido topológico . . [1]
En general, una subdivisión de un gráfico G (a veces conocida como expansión [2] ) es un gráfico resultante de la subdivisión de aristas en G. La subdivisión de alguna arista e con puntos finales { u , v } produce un gráfico que contiene un nuevo vértice w , y con un conjunto de aristas que reemplaza e por dos nuevas aristas, { u , w } y { w , v }.
Por ejemplo, la arista e , con puntos finales { u , v }:
se puede subdividir en dos aristas, e 1 y e 2 , conectándose a un nuevo vértice w de grado -2:
La operación inversa, suavizar o suavizar un vértice w con respecto al par de aristas ( e 1 , e 2 ) incidentes en w , elimina ambas aristas que contienen w y reemplaza ( e 1 , e 2 ) con una nueva arista que conecta el otros puntos finales del par. Aquí se enfatiza que sólo se pueden suavizar los vértices de grado -2 (es decir, bivalentes).
Por ejemplo, el gráfico conexo simple con dos aristas, e 1 { u , w } y e 2 { w , v }:
tiene un vértice (es decir, w ) que se puede suavizar, lo que da como resultado:
Determinar si para los gráficos G y H , H es homeomorfo a un subgrafo de G , es un problema NP-completo . [3]
La subdivisión baricéntrica subdivide cada borde del gráfico. Esta es una subdivisión especial, ya que siempre da como resultado un gráfico bipartito . Este procedimiento se puede repetir, de modo que la enésima subdivisión baricéntrica sea la subdivisión baricéntrica de la n −1ra subdivisión baricéntrica del gráfico. La segunda subdivisión de este tipo es siempre un gráfico simple .
Es evidente que subdividir un gráfico preserva la planaridad . El teorema de Kuratowski establece que
De hecho, un grafo homeomorfo a K 5 o K 3,3 se llama subgrafo de Kuratowski .
Una generalización, derivada del teorema de Robertson-Seymour , afirma que para cada entero g , existe un conjunto finito de gráficos de obstrucción tal que un gráfico H es incrustable en una superficie de género g si y sólo si H no contiene ninguna copia homeomórfica de ningún del . Por ejemplo, consta de los subgrafos de Kuratowski.
En el siguiente ejemplo, el gráfico G y el gráfico H son homeomorfos.
Si G′ es el gráfico creado por la subdivisión de los bordes exteriores de G y H′ es el gráfico creado por la subdivisión del borde interior de H , entonces G′ y H′ tienen un dibujo gráfico similar:
Por lo tanto, existe un isomorfismo entre G' y H' , lo que significa que G y H son homeomórficos.
El nombre surge porque y son homeomórficos como gráficos si y solo si son homeomórficos como espacios topológicos
Definición 20. Si se agregan algunos nuevos vértices de grado 2 a algunas de las aristas de un gráfico G , el gráfico resultante H se llama expansión de G.
