En teoría de grafos , dos grafos y son homeomorfos si existe un isomorfismo de grafos desde alguna subdivisión de a alguna subdivisión de . Si se piensa en los bordes de un grafo como líneas dibujadas de un vértice a otro (como se representan habitualmente en los diagramas), entonces dos grafos son homeomorfos entre sí en el sentido de la teoría de grafos precisamente si sus diagramas son homeomorfos en el sentido topológico . [1]
En general, una subdivisión de un grafo G (a veces conocida como expansión [2] ) es un grafo resultante de la subdivisión de aristas en G. La subdivisión de alguna arista e con extremos { u , v } produce un grafo que contiene un nuevo vértice w y con un conjunto de aristas que reemplaza a e por dos nuevas aristas, { u , w } y { w , v }. Para las aristas dirigidas, esta operación reservará su dirección de propagación.
Por ejemplo, la arista e , con extremos { u , v }:
se puede subdividir en dos aristas, e 1 y e 2 , que se conectan a un nuevo vértice w de grado -2, o de grado de entrada -1 y de grado de salida -1 para la arista dirigida:
Determinar si para los grafos G y H , H es homeomorfo a un subgrafo de G , es un problema NP-completo . [3]
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 los otros puntos finales del par. Aquí, se enfatiza que solo los vértices de grado -2 (es decir, 2-valentes) pueden suavizarse. El límite de esta operación se realiza por el grafo que no tiene más vértices de grado -2.
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:
La subdivisión baricéntrica subdivide cada arista del grafo. Esta es una subdivisión especial, ya que siempre da como resultado un grafo bipartito . Este procedimiento puede repetirse, de modo que la n- ésima subdivisión baricéntrica sea la subdivisión baricéntrica de la n -1.ª subdivisión baricéntrica del grafo. La segunda subdivisión de este tipo es siempre un grafo simple .
Es evidente que al subdividir un grafo se conserva 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, que se desprende del teorema de Robertson-Seymour , afirma que para cada entero g , existe un conjunto finito de grafos de obstrucción tales que un grafo H es integrable en una superficie de género g si y solo si H no contiene ninguna copia homeomorfa de ninguno de los . 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 externos de G y H′ es el gráfico creado por la subdivisión del borde interno 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 homeomorfos.
Los siguientes gráficos mixtos son homeomorfos. Se muestra que las aristas dirigidas tienen una punta de flecha intermedia.
El nombre surge porque y son homeomorfos como grafos si y solo si son homeomorfos como espacios topológicos
Definición 20. Si se añaden algunos nuevos vértices de grado 2 a algunas de las aristas de un grafo G , el grafo resultante H se denomina expansión de G .
