Homeomorfismo (teoría de grafos)
En 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 los 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 extremos { 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 }.
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 la otros puntos finales del par. Aquí, se enfatiza que solo se pueden suavizar los vértices de grado dos (es decir, 2-valentes).
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 de la n -1th subdivisión barycentric de la gráfica. La segunda subdivisión de este tipo es siempre un gráfico simple .
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 es incrustable en una superficie de género g si y solo si H no contiene una copia homeomórfica de cualquier del . Por ejemplo, consta de los subgrafos de Kuratowski.
