En la teoría de grafos , dos grafos y son homeomorfos si hay un isomorfismo de grafo desde alguna subdivisión de a alguna subdivisión de . Si se piensa que los bordes de un gráfico son 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 teórico de gráficos precisamente si son homeomórficos en el sentido en que el término se utiliza en topología . [1]
En general, una subdivisión de un gráfico G (a veces conocido como un expansión [2] ) es un gráfico resultante de la subdivisión de bordes 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 aristas nuevas, { u , w } y { w , v }.
Por ejemplo, el borde e , con extremos { u , v }:
se puede subdividir en dos aristas, e 1 y e 2 , conectando a un nuevo vértice w :
La operación inversa, suavizando o suavizando un vértice w con respecto al par de aristas ( e 1 , e 2 ) que inciden 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 solo se pueden suavizar los vértices de grado dos (es decir, 2-valentes).
Por ejemplo, el gráfico simple conectado con dos aristas, e 1 { u , w } ye 2 { w , v }:
tiene un vértice (a saber, w ) que se puede suavizar, lo que da como resultado:
Determinar si para las gráficas G y H , H es homeomórfico a una subgrafía 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 manera que el n º subdivisión barycentric es la subdivisión barycentric del n -1 º subdivisión barycentric de la gráfica. La segunda subdivisión de este tipo es siempre un gráfico simple .
Es evidente que la subdivisión de un gráfico conserva la planitud. El teorema de Kuratowski establece que
De hecho, un gráfico homeomorfo para K 5 o K 3,3 se llama subgrafo de Kuratowski .
Una generalización, que sigue del teorema de Robertson-Seymour , afirma que para cada entero g , hay un conjunto de gráficas de obstrucción finita tal que una gráfica H se puede incrustar en una superficie de género g si y solo si H no contiene ninguna copia homeomórfica de cualquier del . Por ejemplo, consta de los subgrafos de Kuratowski.
En el siguiente ejemplo, el gráfico G y el gráfico H son homeomórficos.
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 homeomorfos.
El nombre surge porque y son homeomorfos como gráficos si y solo si son homeomorfos como espacios topológicos
Definición 20. Si algunos de los nuevos vértices de grado 2 se añaden a algunos de los bordes de un gráfico G , la gráfica resultante H se denomina expansión de G .