Homeomorfismo (teoría de grafos)

En teoría de grafos , dos grafos $G$ y $G'$ son homeomorfos si existe un isomorfismo de grafos a partir de alguna subdivisión de $G$ a alguna subdivisión de $G'$ Si las aristas de un grafo se consideran líneas trazadas 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 ]}

Subdivisión y suavizado

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 una arista e con extremos { u , v } produce un grafo que contiene un nuevo vértice w y un conjunto de aristas que reemplaza a e por dos nuevas aristas, { u , w } y { w , v }. Para aristas dirigidas, esta operación debe preservar su dirección de propagación.

Por ejemplo, la arista e , con extremos { u , v }:

se puede subdividir en dos aristas, e ₁ y e ₂ , que se conectan a un nuevo vértice w de grado -2, o grado de entrada -1 y 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 ]}

Reversión

La operación inversa, que consiste en suavizar un vértice w con respecto al par de aristas ( e₁ _,e₂ ₎ incidentes en w , elimina ambas aristas que contienen w y reemplaza ( e₁ , e₂ ) por una nueva arista que conecta los otros extremos del par. Cabe destacar que solo se pueden suavizar _{los vértices}_degrado -2 (es decir, bivalentes). El límite de esta operación se alcanza cuando el grafo ya no contiene vértices de grado -2.

Por ejemplo, el grafo simple conexo con dos aristas, e ₁ { u , w } y e ₂ { w , v }:

tiene un vértice (a saber, w ) que se puede suavizar, lo que da como resultado:

Subdivisiones baricéntricas

La subdivisión baricéntrica subdivide cada arista del grafo. Esta es una subdivisión especial, ya que siempre resulta en 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-ésima subdivisión baricéntrica del grafo. La segunda subdivisión de este tipo siempre es un grafo simple .

Incrustaciones en una superficie

Es evidente que subdividir un grafo preserva la planaridad . El teorema de Kuratowski establece que

Un grafo finito es planar si y solo si no contiene ningún subgrafo homeomorfo a K ₅ ( grafo completo de cinco vértices) o K _3,3 ( grafo bipartito completo de seis vértices, tres de los cuales se conectan con cada uno de los otros tres).

De hecho, un grafo homeomorfo a K ₅ o K _3,3 se denomina 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 obstrucciones de grafos. $L(g)=\left\{G_{i}^{(g)}\right\}$ de tal manera que un grafo H es incrustable en una superficie de género g si y solo si H no contiene ninguna copia homeomórfica de ninguno de los $G_{i}^{(g)\!}$ . Por ejemplo, $L(0)=\left\{K_{5},K_{3,3}\right\}$ consta de los subgrafos de Kuratowski.

Ejemplo

En el siguiente ejemplo, el grafo G y el grafo H son homeomorfos.

Gráfico G

Gráfico H

Si G′ es el grafo creado por la subdivisión de las aristas exteriores de G y H′ es el grafo creado por la subdivisión de la arista interior de H , entonces G′ y H′ tienen un dibujo de grafo similar:

Gráfico G′ , H′

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

Gráficos mixtos

Los siguientes grafos mixtos son homeomorfos. Se muestra que las aristas dirigidas tienen una punta de flecha intermedia.

Gráfico G

Gráfico H

Véase también

Referencias

↑ Archdeacon, Dan (1996), "Teoría topológica de grafos: una revisión", Surveys in graph theory (San Francisco, CA, 1995) , Congressus Numerantium, vol. 115, pp. 5–54 , CiteSeerX 10.1.1.28.1728 , MR 1411236 , El nombre surge porque $G$ y $H$ son homeomorfos como grafos si y solo si son homeomorfos como espacios topológicos
↑ Trudeau, Richard J. (1993). Introducción a la teoría de grafos . Dover. pág. 76. ISBN 978-0-486-67870-2. Recuperado el 8 de agosto de 2012 . Definición 20. Si se agregan algunos vértices nuevos de grado 2 a algunas de las aristas de un grafo G , el grafo resultante H se llama una expansión de G .
↑ El problema más comúnmente estudiado en la literatura, bajo el nombre de problema de homeomorfismo de subgrafos, es si una subdivisión de H es isomorfa a un subgrafo de G. El caso en que H es un ciclo de n vértices es equivalente al problema del ciclo hamiltoniano y, por lo tanto, es NP-completo. Sin embargo, esta formulación solo es equivalente a la pregunta de si H es homeomorfo a un subgrafo de G cuando H no tiene vértices de grado dos, porque no permite suavizado en H. Se puede demostrar que el problema planteado es NP-completo mediante una pequeña modificación de la reducción del ciclo hamiltoniano: agregar un vértice a cada uno de H y G , adyacente a todos los demás vértices. Por lo tanto, la ampliación de un vértice de un grafo G contiene un subgrafo homeomorfo a un grafo rueda de ( n + 1), si y solo si G es hamiltoniano. Para la dificultad del problema de homeomorfismo de subgrafos, véase, por ejemplo, LaPaugh, Andrea S .; Rivest, Ronald L. (1980), "El problema del homeomorfismo de subgrafos", Journal of Computer and System Sciences , 20 (2): 133– 149, doi : 10.1016/0022-0000(80)90057-4 , hdl : 1721.1/148927 , MR 0574589 .

Lecturas adicionales

Yellen, Jay; Gross, Jonathan L. (2005), Teoría de grafos y sus aplicaciones , Matemáticas discretas y sus aplicaciones (2.ª ed.), Chapman & Hall/CRC, ISBN 978-1-58488-505-4

[1] Archdeacon, Dan (1996), "Teoría topológica de grafos: una revisión", Surveys in graph theory (San Francisco, CA, 1995) , Congressus Numerantium, vol. 115, pp. 5–54 , CiteSeerX 10.1.1.28.1728 , MR 1411236 , El nombre surge porque $G$ y $H$ son homeomorfos como grafos si y solo si son homeomorfos como espacios topológicos

[2] Trudeau, Richard J. (1993). Introducción a la teoría de grafos . Dover. pág. 76. ISBN 978-0-486-67870-2. Recuperado el 8 de agosto de 2012 . Definición 20. Si se agregan algunos vértices nuevos de grado 2 a algunas de las aristas de un grafo G , el grafo resultante H se llama una expansión de G .

[3] El problema más comúnmente estudiado en la literatura, bajo el nombre de problema de homeomorfismo de subgrafos, es si una subdivisión de H es isomorfa a un subgrafo de G. El caso en que H es un ciclo de n vértices es equivalente al problema del ciclo hamiltoniano y, por lo tanto, es NP-completo. Sin embargo, esta formulación solo es equivalente a la pregunta de si H es homeomorfo a un subgrafo de G cuando H no tiene vértices de grado dos, porque no permite suavizado en H. Se puede demostrar que el problema planteado es NP-completo mediante una pequeña modificación de la reducción del ciclo hamiltoniano: agregar un vértice a cada uno de H y G , adyacente a todos los demás vértices. Por lo tanto, la ampliación de un vértice de un grafo G contiene un subgrafo homeomorfo a un grafo rueda de ( n + 1), si y solo si G es hamiltoniano. Para la dificultad del problema de homeomorfismo de subgrafos, véase, por ejemplo, LaPaugh, Andrea S .; Rivest, Ronald L. (1980), "El problema del homeomorfismo de subgrafos", Journal of Computer and System Sciences , 20 (2): 133– 149, doi : 10.1016/0022-0000(80)90057-4 , hdl : 1721.1/148927 , MR 0574589 .

[ 1 ]

[ 2 ]

[ 3 ]