¿Cociente de un gráfico?

Question

Quiero entender cociente de un gráfico (también llamado gráfico cociente) Mi profesor dice que los términos cociente de un gráfico y un módulo de un gráfico deberían ser sinónimos (aunque el módulo de un gráfico devuelve algo inesperado). He encontrado esto definición sobre el gráfico del cociente

"Dejemos $G = (V, E)$ sea un gráfico. Sea una relación de equivalencia sobre $V$ . El gráfico del cociente de $G$ con respecto a es un gráfico cuyo conjunto de vértices es el conjunto cociente $V/$ y dos clases de equivalencia $[u]$ , $[v]$ forman una arista si $uv$ forma una arista en $G$ ."

¿Qué es el cociente de la gráfica?

1. Qué es el conjunto de cocientes $V/\sim$ ?

   1.1. En comparación, el conjunto de cocientes en números enteros como $\mathbb Z\ /\text{ division}$ consiste en las clases de cociente sobre los restos. Lo que equivale a "restos" ¿con gráficos?

   1.2. ¿Qué son las clases de equivalencia de un grafo?

2. ¿Cómo se define el cociente para un dígrafo?

Answer 1

Intentaré iluminar la definición que has citado con un ejemplo. Considere este gráfico del mapa del metro de Viena:

Por Usuario:Mi amigo - Obra propia, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=7684906enter descripción de la imagen aquí

Los vértices de este gráfico son las estaciones.

Definir una relación de equivalencia en el conjunto de vértices por

$v_1 \sim v_2 \mbox{ iff } v_1 \mbox{ is on the same subway line (e.g. U1, U2,...) as } v_2$ .

En este caso, tenemos que modificar ligeramente el gráfico y tratar las estaciones en las que se puede cambiar de línea (por ejemplo, Westbahnhof) como dos vértices diferentes, pero conectados, es decir, Westbahnhof-U3 y Westbahnhof-U6 (puedes pensar en ellos como diferentes andenes de metro en lugar de estaciones).

Entonces hay exactamente cinco clases de equivalencia (tantas como líneas de metro). Estas clases de equivalencia son conjuntos de estaciones, por ejemplo

$$[\mbox{Heiligenstadt}]= \{\mbox{Heiligenstadt, Spittelau-U4, Friedensbrücke,}\dots\}.$$

Cada parada de una línea determinada es un miembro de la clase de equivalencia asociada a esta línea.

La definición de las aristas en el cociente (que $[u][v]$ si $uv$ ) garantiza lo siguiente: Para dos clases de equivalencia de aristas dadas (es decir, líneas de metro), si hay una estación en la que se puede cambiar entre estas líneas (por ejemplo, Westbahnhof-U3 y Westbahnhof-U6), entonces estas clases de equivalencia están conectadas.

El gráfico resultante describe la conectividad de las líneas de metro, no las paradas.

El resultado es un gráfico en el que U1 tiene una arista con U2, U3 y U4; U2 tiene una arista con U2, U3 y U4; U3 tiene una arista con U1, U2, U4, U6; U4 tiene una arista con U1, U2, U3 y U6; U6 tiene una arista con U3 y U4. Debería ser así, excepto que el $5$ representa a U6.

Por Hafenbar de Wikipedia en alemán, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=15737112

Obsérvese que las clases de equivalencia no tienen por qué estar conectadas, como ocurre en este caso.

En el caso de los grafos dirigidos, no puedo dar más información, pero supongo que la definición de las aristas (dirigidas) se traslada al caso no dirigido.

Answer 2

Nos remitimos a la lista enumerada a continuación sobre ¿Cuál es el cociente de la gráfica?

1. Qué es el conjunto de cocientes $V/\sim$ ?

   1.1. En comparación, el conjunto de cocientes en números enteros como $\mathbb Z\ /\text{ division}$ consiste en el cociente de los residuos. Lo que equivale a "restos" ¿con gráficos?

   1.2. ¿Qué son las clases de equivalencia de un grafo?

2. ¿Cómo se define el cociente para un dígrafo?

---

(1.) ¿Cuál es el conjunto cociente $V/\sim$ ?

El conjunto cociente es el conjunto de clases de equivalencia, en este caso $$V/\sim\;=\{[v]:v\in V\}=\{\{x\in V:v\sim x\}:v\in V\}.$$ Nótese que (en general) los términos "conjunto cociente de $X$ " y "módulo de $X$ " son equivalentes (por definición) cuando se refieren a alguna relación de equivalencia $\sim$ . Por esta razón, asumiría que el módulo de un grafo es el grafo con conjunto de vértices " $V$ modulo $\sim$ " y conjunto de aristas como se describe en su definición (de la misma manera que el cociente de un gráfico es el gráfico con conjunto de vértices "el conjunto cociente de $V$ por $\sim$ ").

El conjunto de cocientes $X/R$ es sólo una partición de $X$ que es "decidido" por $R$ . También podríamos hacerlo al revés, es decir, empezar con una partición $X=\bigcup X_i$ con $X_i\cap X_j=\emptyset$ siempre que $i\neq j$ y que $xR y$ si $\{x,y\}\subseteq X_i$ para algunos $i$ . Entonces $X/R=\{X_i\}$ . Así que de la misma manera, podríamos ver $V/\sim$ como una determinada partición del conjunto de vértices $V$ .

(1.1., 1.2.) Los "restos" son sólo las clases de equivalencia. Es decir, en un grafo cociente, los elementos $[v]=\{x\in V:v\sim x\}$ del conjunto cociente $V/\sim$ . Obsérvese que sólo son conjuntos de vértices que vienen dados por el cociente en el conjunto $V$ (no hay teoría de grafos aquí) -- esta definición no diferirá de las clases de equivalencia estándar de cualquier relación de equivalencia antigua sobre algún conjunto.

Por ejemplo, si $nRm$ si $5|(n-m)$ (como en la respuesta a la pregunta enlazada), el conjunto cociente $\Bbb{Z}/R$ es $\{[0],[1],[2],[3],[4]\}$ . En el ejemplo de la división, las clases son los conjuntos de enteros que tienen el mismo resto cuando se dividen por $5$ y en el ejemplo del gráfico, las clases son los conjuntos de vértices definidos por la relación de equivalencia $\sim$ (del que no sabemos nada).

(2.) ¿Cómo se define el cociente para un dígrafo?

La definición es la misma para un dígrafo, pero está escrita de forma más agradable en el Artículo de Wikipedia en el gráfico Quotient. Para citar:

[I]f $G$ tiene un conjunto de bordes $E$ y el conjunto de vértices $V$ y $R$ es la relación de equivalencia inducida por la partición, entonces el gráfico cociente tiene un conjunto de vértices $V/R$ y conjunto de bordes $$\{([u]_R, [v]_R) : (u, v) \in E(G)\}.$$

(Recordemos, $(x,y)$ se entiende como una arista de $x$ à $y$ en un dígrafo). Así que una arista en el cociente de $G$ existe de $[u]_R$ a $[v]_R$ si hay una arista en $G$ de cualquier vértice $u\in [u]_R$ a cualquier vértice $v\in [v]_R$ . Un ejemplo de esto se ve en esta pregunta . Aquí, la relación de equivalencia viene dada por $v\sim u$ si existe un camino desde $v$ à $u$ y un camino desde $u$ à $v$ . Por lo tanto (como se indica en la respuesta), las tres clases son $[a]=\{a,b\}$ , $[c]=\{c\}$ y $[d]=\{d,e,f,g,h\}$ . He dibujado el gráfico del cociente a continuación (disculpen los conocimientos de Paint).

En cuanto a la petición de referencia, nunca he visto la definición en ningún libro de texto de teoría de grafos que haya leído. La fuente de Wikipedia parece ser Partición de gráficos de alta calidad (Peter Sanders, Christian Schulz) ( pdf ), que sí tiene una definición que coincide con la que tú mencionas y con la que yo conocía. No he encontrado ninguna fuente que utilice "modulo" de un grafo (en este contexto) pero, como he mencionado antes, esto se debe probablemente a la intercambiabilidad de los términos cuando se describen relaciones de equivalencia (generales).

Answer 3

Destaco el comentario sobre una definición más general del gráfico de cociente y negrita la debilidad de la definición original

La definición de tu post es mala porque depende de la elección de los representantes $u$ y $v$ , por lo que no está bien definido en general. Debería ser redactado: los bordes en $V/$ son $$\{\{[u],[v]\}|\{u,v\}E\}.$$

que es igual, salvo diferencias notacionales, a la definición de la sección Quotient Graph de Wikipedia proporcionada por Szmagpie .