Homeomorfismo gráfico

Dos gráficos y son homeomorfos si hay un isomorfismo de alguna subdivisión del gráfico y alguna subdivisión del gráfico [1] . Si los bordes de un gráfico se entienden como segmentos que conectan vértices (como suele dibujarse en las ilustraciones), entonces dos gráficos son homeomorfos en el contexto de la teoría de grafos cuando son homeomorfos en el sentido topológico .

Subdivisión y exclusión

En general, una subdivisión de un grafo G (a veces se usa el término extensión [2] o subdivisión ) es un grafo obtenido dividiendo aristas en G. Dividir una arista e con vértices finales { u , v } da un gráfico que contiene un nuevo vértice w y dos aristas { u , w } y { w , v } en lugar de la arista e [1] .

Por ejemplo, borde e con extremos { u , v }:

se puede dividir en dos aristas, e 1 y e 2 :

La operación inversa, eliminando el vértice w con aristas incidentes ( e 1 , e 2 ), reemplaza ambas aristas adyacentes al vértice w ( e 1 , e 2 ) con una nueva arista que conecta los extremos del par. Debe enfatizarse que esta operación es aplicable solo a vértices que inciden con exactamente dos aristas.

Por ejemplo, un gráfico conexo simple con dos aristas e 1 { u , w } y e 2 { w , v }:

tiene un vértice (llamado w ) que se puede excluir, lo que da como resultado:

Determinar si un grafo H es homeomorfo a un subgrafo G es un problema NP-completo [3] .

Subdivisiones baricéntricas

La subdivisión baricéntrica divide cada borde del gráfico. Este es un tipo especial de subdivisión que siempre da un gráfico bipartito . Este procedimiento se puede repetir para que la subdivisión baricéntrica n-ésima sea la subdivisión baricéntrica de la subdivisión n-1 . La segunda división de este tipo es siempre un gráfico simple .

Incrustación en una superficie

Es obvio que la subdivisión del gráfico conserva la planaridad. El teorema de Pontryagin-Kuratovsky establece que

un grafo finito es plano si y solo si no contiene un subgrafo homeomorfo a K 5 ( grafo completo con cinco vértices ), o K 3,3 ( grafo bipartito completo con seis vértices, tres de los cuales están conectados a cada uno de los restantes Tres).

De hecho, un grafo homeomorfo a K 5 o K 3,3 se llama subgrafo de Kuratowski .

La generalización que sigue del teorema de Robertson-Seymour establece que para cualquier número entero g existe un conjunto obstructivo finito de gráficos tal que el gráfico H es incrustable en una superficie de género g si y solo si H no contiene una copia homeomorfa a algún gráfico . Por ejemplo, consta de subgrafos de Kuratovsky.

Ejemplo

En el siguiente ejemplo, los gráficos G y H son homeomorfos.

GRAMO H

Si el gráfico G' se crea subdividiendo los bordes exteriores del gráfico G y el gráfico H' se crea subdividiendo los bordes interiores del gráfico H, entonces G' y H' tienen representaciones gráficas similares:

g', h'

Por lo tanto, existe un isomorfismo entre los gráficos G' y H', lo que significa que G y H son homeomorfos.

Véase también

Notas

  1. ↑ 1 2 Yablonsky, 1986 , pág. 225.
  2. ↑ Trudeau, 1993 , pág. 76, Definición 20.
  3. ↑ Un problema más ampliamente estudiado en la literatura llamado "problema de homeomorfismo de subgrafo" pregunta si una subdivisión de un gráfico H es isomorfa a un subgrafo G. Si H es un ciclo con n vértices, el problema es equivalente a encontrar un ciclo hamiltoniano y, por lo tanto, es NP-completo. Sin embargo, esta formulación solo es equivalente a preguntar si un grafo H es homeomorfo a un subgrafo G cuando H no contiene vértices de grado dos, ya que esto no permite una excepción en H. Se puede demostrar que el problema dado es NP-completo modificando ligeramente el ciclo hamiltoniano: agregamos un vértice cada uno en H y G adyacentes a todos los demás vértices. Entonces el grafo G aumentado en un vértice contiene un subgrafo homeomorfo a una rueda con ( n  + 1) vértices si y solo si G es hamiltoniano. Para conocer la complejidad del problema del homeomorfismo de subgrafos, consulte el artículo de LaPaugh y Rivest ( LaPaugh, Rivest 1980 ).

Literatura