Construya el gráfico más pequeño homeomórfico para un gráfico dado suavizando

Question

La clase de homeomorfismo $ \mathcal{H}(G) $ de una gráfica $G$ es el conjunto de clases de isomorfismos de grafos que son topológicamente homeomorfos para $G$. Es natural preguntar: ¿Hay un representante "más pequeño" en la clase de homeomorfismo? Si es así, ¿cómo encontrarlo? Desafortunadamente, no encontré ningún resultado útil sobre este problema después de una búsqueda rápida en Google.

Sin embargo, guiado por la intuición, tengo la siguiente hipótesis:

El gráfico más pequeño homeomorfo a un gráfico se obtiene suavizando cada oído máximo.

En esta publicación intento esbozar una prueba, pero hay un vacío en la prueba, así que no sé si mi hipótesis es realmente correcta. Agradecería a cualquiera por señalar mis errores y llenar el vacío.

Advertencia: esta sería una publicación larga

Primero, aclaremos algo de terminología. El término "oído" significa cosas diferentes en diferentes libros de texto de teoría de grafos. En esta publicación, adoptamos la siguiente definición:

Definición 1

Una oreja en un gráfico es:

• un ciclo cuyos vértices todos excepto posiblemente uno son de grado $2$, o
• un camino cuyos vértices internos son de grado $2$.

Una oreja máxima es una oreja que no es un subgrafo adecuado de una oreja más grande. De manera equivalente, un oído máximo es uno de los siguientes:

• un ciclo que es un componente completo conectado por sí solo
• un ciclo en el que exactamente un vértice es de grado $ \geq 3 $, mientras que todos los demás vértices son de grado $2$
• un camino en el que todos los vértices internos son de grado $2$, mientras que ambos vértices finales son de grado $ \neq 2 $

Dos operaciones comunes que preservan la topología en los gráficos son subdividir y suavizar:

Definición 2

Subdividir un borde significa reemplazarlo por una oreja. Más precisamente, dejemos$e = uv$ ser una ventaja.

Si $u = v$, luego subdividiendo el bucle propio $e$ significa reemplazarlo por un ciclo $C$y $u = v$ se convierte en un vértice en $C$, que puede o no tener grado $2$, dependiendo de si $e$ está aislado.

Por otro lado, si $u \neq v$, luego subdividiendo $e$ significa reemplazarlo por un camino $P$y $u, v$ convertirse en los vértices finales de $P$.

Subdividir un gráfico significa realizar una secuencia de subdivisión en los bordes.

Definición 3

Alisar una oreja significa reemplazarla por un solo borde. Más precisamente, dejemos$C$ ser un oído.

Si $C$ es un ciclo, luego suavizar $C$ significa reemplazarlo por un bucle automático $e$y el vértice de grado $ \neq 2 $ en $C$ se convierte en el único vértice incidente en $e$ (si todos los vértices en $C$ son de grado $2$, simplemente elija cualquier vértice).

Por otro lado, si $C$ es en realidad un camino $P$, luego suavizando $P$ significa reemplazarlo por un borde sin bucle $e$, y los vértices finales de $P$ convertirse en los vértices finales de $e$.

Suavizar un gráfico significa realizar una secuencia de suavizado en los oídos.

A continuación, tenemos el siguiente resultado clásico sobre topología de gráficos:

Teorema 1

Dos gráficos son homeomórficos si y solo si uno de ellos puede obtenerse de una secuencia de operaciones de subdivisión y suavizado en el otro.

Prueba: Vea esta publicación .

Teorema 2

Dejar $G$ y $H$ser dos grafos homeomorfos. Entonces$ |V(G)| = |V(H)| $ si y solo si $ |E(G)| = |E(H)| $.

Bosquejo de la prueba: Subdividir (o suavizar) siempre aumenta (o disminuye) el número de vértices y aristas en el mismo número.$\square$

A la luz del Teorema 2, podemos definir un orden en la clase de homeomorfismo de un gráfico:

Definición 4

Dejar $ \mathcal{H}(G) $ ser la clase de homeomorfismo de un gráfico $G$. Definir el orden$\preceq$ en $ \mathcal{H}(G) $ por: $$ G_1 \preceq G_2 \iff |V(G_1)| \leq |V(G_2)| $$ para cualquier $ G_1, G_2 \in \mathcal{H}(G) $.

Si $ G_1 \preceq G_2 $ y $ G_2 \preceq G_1 $, entonces denotamos $ G_1 \sim G_2 $.

El orden $\preceq$es un preorden total, lo que significa que es transitivo y dos gráficos homeomorfos cualesquiera son comparables. Desafortunadamente, no es un pedido total, ya que$ G_1 \sim G_2 $ No implica $ G_1, G_2 $ son isomorfos, incluso a través del teorema 2 implica $ |E(G_1)| = |E(G_2)| $.

Teorema 3

Cualquier gráfico sin vértice aislado se puede descomponer de forma única en una unión de bordes disjuntos de oídos máximos.

Bosquejo de la prueba:

Dejar $G$ser un gráfico sin vértice aislado. Definir la relación$R$ en $E(G)$ por: $$ eRf \iff \exists \text{ ear } C \subseteq{G} \text{ s.t. } e, f \in E(C) $$ para cualquier $ e, f \in E(G) $.

Entonces $R$ es una relación de equivalencia en $E(G)$, en el que cada clase de equivalencia contiene los bordes de exactamente un oído máximo. Así,$R$ induce una descomposición de $G$en una unión de bordes disjuntos de orejas máximas. Por el contrario, dicha descomposición debe ser inducida por$R$, por lo que la descomposición es única. $\square$

Con base en la descomposición anterior, podemos definir lo siguiente:

Definición 5

Una gráfica sin vértice aislado se llama suave si cada oreja máxima tiene una longitud $1$. Para un gráfico$G$ sin vértice aislado, el gráfico suave obtenido al suavizar cada oído máximo en $G$ se denota como $ \text{Smooth} (G) $.

El término "gráfico suave" no es estándar, pero no pude encontrar ningún término existente para dicho gráfico, así que lo invento yo mismo.

Teorema 4

Dejar $G$ ser un gráfico suave sin vértice aislado y $ H \in \mathcal{H}(G) $, entonces $ G \preceq H $. Además,$ G \sim H $ si y solo si $H$ es un gráfico suave.

Bosquejo de la prueba:

Según el teorema 1, $H$ puede obtenerse de una secuencia de operaciones de subdivisión y suavizado en $G$. Cada paso de las operaciones solo puede cambiar una oreja máxima a otra oreja máxima de longitud posiblemente diferente.

Por otro lado, en un gráfico suave, todas las orejas máximas ya tienen la longitud más corta posible (es decir, $1$), por lo que cualquier secuencia de subdivisión y suavizado nunca podrá disminuir más el número de vértices. Así,$ |V(G)| \leq |V(H)| $ y la igualdad se mantiene si y solo si $H$ es suave. $\square$

La siguiente afirmación se basa en la intuición, pero no sé cómo demostrarlo. Es donde se encuentra la brecha de toda mi prueba.

Reclamación 0

Dejar $G$ y $H$Ser dos gráficos suaves sin vértice aislado. Si son homeomorfos, entonces son isomorfos.

Finalmente, asumiendo la afirmación anterior, podemos probar la hipótesis principal:

Hipótesis principal

Suponga que la afirmación 0 es correcta y deje $G$ser un gráfico sin vértice aislado. Entonces$ \text{Smooth} (G) $ es el gráfico más pequeño único en $ \mathcal{H} (G) $ con respecto al pedido $ \preceq $.

Prueba:

El hecho de que $ \text{Smooth} (G) \preceq H $ para todos $ H \in \mathcal{H} (G) $ se sigue del teorema 4.

Para probar la singularidad, dejemos $ H \in \mathcal{H} (G) $ ser tal que $ \text{Smooth} (G) \sim H $. Ya que$ \text{Smooth} (G) $ es suave y $ H \in \mathcal{H} (\text{Smooth} (G)) $, por el teorema 4, $H$es suave también. El reclamo 0 entonces implica$H$ es isomorfo a $ \text{Smooth} (G) $. $\square$

Preguntas:

1. ¿Es correcta la Reclamación 0? ¿Cómo probarlo?
2. Incluso si la afirmación 0 es incorrecta, ¿mi hipótesis principal sigue siendo correcta?
3. ¿Hay otros errores en mi prueba?
4. ¿Existe un término mejor para los gráficos en los que cada oído máximo tiene una longitud? $1$, que no sean "gráficos suaves"?

Answer 1

Tu prueba me parece correcta. No veo por qué asume que el gráfico no tiene vértices aislados, ¿hace alguna diferencia en alguna parte? Además, "gráfico suave" parece ser un nombre elegante para un gráfico sin vértices de grado dos. (Más precisamente, los únicos vértices de grado dos son vértices aislados con un bucle).

Daré una prueba de su reclamo. Podemos suponer que las gráficas en cuestión están conectadas y que tienen al menos un borde. A cualquier gráfico$G$, asociar un gráfico de color de vértice $Ear(G)$ de la siguiente manera:

• Los vértices de $Ear(G)$ corresponden a los oídos en la descomposición única de $G$en oídos máximos. Son de color azul y rojo según si la oreja es un camino o un ciclo.
• Dos vértices son adyacentes si las orejas correspondientes tienen un vértice común; si tienen dos vértices comunes, dibujamos dos aristas paralelas. (Esto solo puede suceder si las orejas correspondientes son caminos).

Hay que hacer dos observaciones que están más o menos implícitas en su demostración del Teorema 4:

1. Si $G$ y $H$ son homeomorfos, entonces $Ear(G)$ y $Ear(H)$son isomorfos, y el isomorfismo conserva los colores de los vértices. Esto se sigue del teorema 1 después de comprobar que tanto el suavizado como la subdivisión conservan$Ear(G)$.
2. Si $G$ es suave, luego (sin tener en cuenta el color) $Ear(G)$es solo el gráfico lineal de$G$, definido apropiadamente para gráficos con bucles y múltiples bordes.

Convenientemente, un teorema de Whitney establece que si las gráficas lineales de dos gráficas simples conectadas son isomórficas, entonces las gráficas mismas son isomorfas, excepto si las gráficas son el triángulo$K_3$ y la garra $K_{1,3}$. Tenga en cuenta que el triángulo no es liso. En el caso de los gráficos con bucles y bordes paralelos, la situación es más complicada (aunque no terriblemente, según este artículo * en el que solo pude encontrar un enlace de pago; curiosamente, el nombre de Whitney está mal escrito en el título) , pero en nuestro caso, la coloración de vértices y el Teorema 4 nos dan suficiente información para reconstruir de forma única el gráfico original. Probablemente pueda resolver esto usted mismo, pero le daré los detalles para que esté completo.

Entonces suponga que $G$ y $H$ son suaves y eso $Ear(G)$ y $Ear(H)$son isomorfos. Primero, tratamos con bucles: estos corresponden precisamente a los vértices rojos de$Ear(G)$ y $Ear(H)$. De ello se deduce que si denotamos por$G'$ y $H'$ los gráficos obtenidos al eliminar los bucles en $G$ y $H$, entonces $Ear(G')$ y $Ear(H')$ se obtienen eliminando los vértices rojos de $Ear(G)$ y $Ear(H)$; en particular, son isomorfos. Ahora basta con demostrar que$G'$ y $H'$ son isomorfos, ya que entonces las posiciones de los bucles están determinadas unívocamente por $Ear(G)$: un vértice en $G'$ tiene un bucle si y solo si hay un borde incidente que es adyacente a un vértice rojo en $Ear(G)$, o si $G'$ consta de este único vértice (ya que asumimos que nuestras gráficas tienen al menos una arista).

Por tanto, podemos suponer que $G$ y $H$no contienen bucles. Ahora solo tenemos que cuidar los bordes paralelos. Si dos aristas son paralelas en$G$, luego por nuestra construcción los vértices correspondientes en $Ear(G)$están conectados por dos bordes paralelos. Más generalmente, dos o más bordes paralelos en$G$ corresponden a una camarilla en $Ear(G)$en el que cada borde se duplica. Cada vértice en$Ear(G)$ está contenido en un máximo único como "doble camarilla" (potencialmente de tamaño uno), y al contraer estas camarillas y reemplazar los bordes paralelos recién formados por unos simples, obtenemos el gráfico lineal del gráfico simple subyacente $G$. Dado que esto también funciona al revés (es decir, desde el gráfico simple y$Ear(G)$ podemos recuperarnos $G$), podemos asumir que $G$ y $H$ son simples.

Así que hemos terminado con el teorema de Whitney, ¿verdad? Bueno, no tan rápido. Podría suceder que después de dejar bucles y bordes paralelos de$G$ y $H$, nos queda un triángulo y $K_{1,3}$: después de todo, un triángulo con bordes doblados es liso. Pero esto está descartado por el Teorema 4: el original$G$ y $H$tenía el mismo número de vértices, y dejar bordes no cambia eso. Entonces$G$ y $H$ son de hecho isomorfos.

^{* Tenga en cuenta que, por lo que puedo decir, la noción de gráfico lineal utilizada en el artículo es diferente de la utilizada aquí, en que los vértices correspondientes a los bordes paralelos todavía están conectados con un solo borde.}