Homeomorfismo (teoría de grafos)

En la teoría del gráfico, dos gráficos G{displaystyle G. y G.{displaystyle G. son homeomorfo si hay un isomorfismo gráfico de alguna subdivisión G{displaystyle G. to some subdivision of G.{displaystyle G.. Si los bordes de un gráfico se consideran como líneas dibujadas de un vértice a otro (como suelen ser representados en ilustraciones), entonces dos gráficos son homeomórficos entre sí en el sentido gráfico-teorético precisamente si son homeomorfos en el sentido topológico.

Subdivisión y suavizado

En general, una subdivisión de un gráfico G (a veces conocida como expansión) es un gráfico resultante de la subdivisión de aristas en G. La subdivisión de algún borde e con puntos finales {u,v } produce un gráfico que contiene un nuevo vértice w, y con un conjunto de aristas reemplazando e por dos nuevas aristas, {u,w } y {w,v }.

Por ejemplo, el borde e, con puntos finales {u,v }:

Did you mean:

can be subdivided into two edges, <in₁ and e₂, connecting to a new vertex w:

La operación inversa, suavizar o suavizar un vértice w con respecto al par de aristas (e₁, e₂) incidente en w, elimina ambos bordes que contienen w y reemplaza (e₁, e₂) con un nuevo borde que conecta los otros puntos finales del par. Aquí se enfatiza que sólo se pueden suavizar los vértices de grado 2 (es decir, bivalentes).

Did you mean:

For example, the simple connected graph with two edges, <in₁ {u,w } and e₂ {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 una Problema NP completo.

Subdivisiones baricéntricas

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 n^ésima subdivisión baricéntrica sea la subdivisión baricéntrica de la n−1.ª subdivisión baricéntrica del gráfico. La segunda subdivisión es siempre un gráfico simple.

Incrustar en una superficie

Did you mean:

It is evident that subdividing a graph preserves planarity. Kuratowski 's theorem states that

un gráfico finito es plano si y sólo si contiene ningún subgrafo homeomorfo a K₅ (grafo completo en cinco vértices) o K_3,3 (grafo bipartito completo en seis vértices, tres de los cuales se conectan a cada uno de los otros tres).

De hecho, un gráfico homeomorfo a K₅ o K_3,3 se llama subgrafo de Kuratowski..

Una generalización, siguiendo el teorema Robertson-Seymour, afirma que para cada entero g, hay un finito obstrucción de gráficos L()g)={}Gi()g)}{displaystyle L(g)=left{G_{i}{(g)}right} tal que un gráfico H es incrustable en una superficie de género g si H no contiene ninguna copia homeomórfica de ninguno de los Gi()g){displaystyle G_{i} {g)}}. Por ejemplo, L()0)={}K5,K3,3}{displaystyle L(0)=left{K_{5},K_{3,3}right} consta de los subgrafos de Kuratowski.

Ejemplo

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 de los borde interior de H, entonces G′ y H′ tienen un dibujo gráfico similar:

Did you mean:

Therefore, there exists an isomorphism between ' and H&m#39;, meaning G and H are homeomorphic.