Definición de gráfico dual

Question

Definición de gráfico dual

Matemáticas
Teoría de grafos
combinatoria
grafos planos

n901

Entiendo que el gráfico dual $G^*$ está realmente definida para un gráfico plano $G$ , es decir, un gráfico junto con una incrustación en $\mathbb{R}^2$ , en lugar de solo un gráfico plano, pero todavía tengo dificultades para entender por qué está bien definido.

Decir $G$ es $K_3$ y $K_4$ conectado por un borde $e$ , incrustado en el plano de forma natural ( $K_4$ está incrustado como un triángulo con su centro). En $G^*$ hay un bucle $l$ en el vértice correspondiente a la cara no acotada de $G$ . Debería $l$ cruz $e$ ? Si es así, ¿debería rodear $K_3$ o $K_4$ ? Creo que los "gráficos duales" resultantes son isomorfos como gráficos pero diferentes como gráficos planos, aunque los dos últimos parecen iguales si se consideran gráficos en esfera. También parece haber cierta libertad al conectar la cara ilimitada con otras caras. ¿Cuál es el algoritmo exacto para dibujar un gráfico dual?

Editar: he llegado a la conclusión de que el gráfico dual está bien definido hasta la incrustación en la esfera, aunque no puedo mostrar esto rigurosamente.

Para mayor comodidad, aquí está la parte de Combinatorial Mathematics de Douglas West sobre dual.

n901

@Morgan Rodgers Pero he visto en diferentes lugares la afirmación de que el doble dual de un gráfico conectado es en sí mismo, por lo que el dual debería ser algo más que un gráfico; de lo contrario, no tiene sentido hablar de doble dual.

Mike Earnest

G^{* *}

$G^{**}$ es en sí mismo como un gráfico, pero no como un gráfico plano.

n901

@Mike Earnest ¿Cómo define el dual de

G^{*}

$G^*$ si se da sólo como un gráfico?

Mike Earnest

@ n901 Punto justo! La única explicación que se me ocurre es que eliges cualquier incrustación para

G^{*}

$G^{*}$ y usar eso para construir

G^{* *}

$G^{**}$ , luego demuestre que cualquier incrustación para

G^{*}

$G^{*}$ da como resultado el mismo grafico

G^{* *}

$G^{**}$ . Pero no sé si esto es realmente cierto.

morgan rodgers

@MikeEarnest No, eso no es cierto.

n901

@Morgan Rodgers El texto que usamos es Combinatorial Mathematics de West, donde la declaración aparece al comienzo del capítulo 9 (pero se deja como ejercicio). También hay hilos en este foro como math.stackexchange.com/questions/1585631/…

Respuestas (2)

Definición de gráfico dual

@Morgan Rodgers Pero he visto en diferentes lugares la afirmación de que el doble dual de un gráfico conectado es en sí mismo, por lo que el dual debería ser algo más que un gráfico; de lo contrario, no tiene sentido hablar de doble dual.
$G^{**}$ es en sí mismo como un gráfico, pero no como un gráfico plano.
@Mike Earnest ¿Cómo define el dual de $G^*$ si se da sólo como un gráfico?
@ n901 Punto justo! La única explicación que se me ocurre es que eliges cualquier incrustación para $G^{*}$ y usar eso para construir $G^{**}$ , luego demuestre que cualquier incrustación para $G^{*}$ da como resultado el mismo grafico $G^{**}$ . Pero no sé si esto es realmente cierto.
@Morgan Rodgers El texto que usamos es Combinatorial Mathematics de West, donde la declaración aparece al comienzo del capítulo 9 (pero se deja como ejercicio). También hay hilos en este foro como math.stackexchange.com/questions/1585631/…

morgan rodgers · Answer 1

El dual de un gráfico plano es un gráfico, y no en sí mismo un gráfico plano; cualquier forma en que coloque el ciclo le dará un gráfico isomorfo, por lo que no importa desde este punto de vista.

En cuanto a si las opciones le darán incrustaciones equivalentes en una esfera, este no es el caso; en el ejemplo que das, tienes 4 opciones de dónde colocar el bucle; puedes ponerlo encerrando el vértice correspondiente al $K_{3}$ , o puedes ponerlo encerrando el triangulo correspondiente al $K_{4}$ , o encerrando ambos, o no encerrando ninguno. Todos son diferentes como gráficos planos, se emparejarán en dos clases separadas como incrustaciones en la esfera.

editar: después de mencionar que están usando West

En la Introducción a la teoría de grafos de West , da la siguiente definición del gráfico dual:

Definición 6.1.7: El grafo dual $G^*$ de un gráfico plano $G$ es un gráfico plano cuyos vértices corresponden a las caras de $G$ . los bordes de $G^{*}$ corresponden a los bordes de $G$ de la siguiente manera: Si $e$ es un borde de $G$ con cara $X$ de un lado y cara $Y$ por el otro, los extremos del doble filo $e^*$ uniendo los vértices $x$ , $y$ en $G^*$ correspondiente a las caras $X$ y $Y$ . El orden en el plano de las aristas incidentes a $x \in V(G^{*})$ es el orden de las aristas que delimitan la cara $X$ de $G$ en un paseo alrededor de su límite. (énfasis añadido).

Esto le da la noción que está buscando sobre dónde dibujar el bucle; Creo que sugiere que el ciclo debe contener uno de $K_{3}$ o $K_{4}$ , pero no ninguno o ambos; sin embargo, no resuelve la última parte de la ambigüedad. Esto se aborda en la observación 6.1.9 del mismo libro, pero no de manera adecuada; Creo que este es un descuido menor hecho por West.

Parece que la gente generalmente está de acuerdo en que el bucle debe cruzar el borde de conexión; en ese caso, no veo cómo es posible encerrar ambos/ninguno. Hay algunas opciones adicionales para otros bordes en $G^*$ , pero hasta ahora todos me parecen iguales (como gráficos de esfera).
Es un libro diferente, y estoy aún más confundido por esta definición... ¿Hay algún tipo de orientación coherente en los bordes? ¿Qué pasa si un borde aparece dos veces en el paseo?
Resuelve a medias dónde colocar el bucle; ya que para atravesar el límite de la cara exterior, darías la vuelta al $K_{3}$ , cruzando el puente, alrededor del $K_{4}$ , de vuelta a través del puente, los dos extremos del bucle deben estar separados, separando el $K_{3}$ y $K_{4}$ bordes a cada lado. Pero es ambiguo acerca de lo que está encerrado en el bucle. El comentario "aclarador" al que me refiero anteriormente (pero no transcribo; lo siento, el gato en mi regazo hace que sea difícil escribir) tampoco lo resuelve.
@ n901 Creo que puede tener razón, aunque según esta definición, tiene equivalencia como incrustaciones esféricas. Pero no 100% seguro.

Raul Madhavan · Answer 2

¿Debería cruzar e?

Sí, debería cruzar e. Considere el ejemplo más simple de un gráfico ABCD. En este caso, si el bucle propio a través de BC no cruza el borde de BC, no podrá replicar el gráfico original tomando el dual del dual.

Si es así, debería rodear $K_3$ o $K_4$ .

Ambos son válidos e isomorfos. Por ejemplo, independientemente de cuál rodee, puedo reconstruir el gráfico original a partir del dual de los gráficos duales correspondientes, por lo que ambos son válidos.

¿Hay un algoritmo?

¿A ver si esto ayuda?

Por supuesto que son isomorfos como gráficos, pero me preguntaba si son lo mismo que los gráficos planos, y ahora creo que la respuesta es no, pero tal vez se convierte en sí si los vemos como gráficos de esfera.
Ah, eso es interesante, no había pensado en esa incrustación (como incrustaciones en la superficie de la esfera). Ahora que lo pienso, son isomorfos como gráficos de esfera; puedes pensar en ese bucle como un círculo mayor en S2

Definición de gráfico dual

n901

n901

Mike Earnest

n901

Mike Earnest

morgan rodgers

n901

Respuestas (2)

morgan rodgers

n901

morgan rodgers

n901

morgan rodgers

morgan rodgers

Raul Madhavan

n901

Raul Madhavan

Gráficos en Cilindros

Dibujar curvas (o segmentos) que no se intersecan conectando vértices no adyacentes en un polígono regular

¿Por qué la homología no puede distinguir entre gráficos planos y no planos?

¿Cómo podemos formalizar la noción de la cara de un gráfico plano?

Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2

Número mínimo de particiones de un conjunto dada lista de números que no pueden aparecer en la misma partición

Una pregunta sobre la expectativa del número cromático

NP-completitud del problema de grafos planos no dirigidos

(Aclaración) Un gráfico con un número par de vértices tiene dos vértices con un número par de vecinos comunes

Una pregunta sobre un gráfico conexo con kkk