¿Existe una definición útil de los menores para los dígrafos?

Question

Para un grafo no dirigido, mi comprensión "intuitiva" de un menor es que tomo un subgrafo, divido su conjunto de vértices en conectado subconjuntos y contraer cada subconjunto en un solo vértice.

Si intento la misma definición con un grafo dirigido (=digrafo), tengo el problema de que hay una distinción entre débilmente conectado y fuertemente conectado . Aun así, vi una definición en la que conectado fue simplemente sustituido por débilmente conectado Durante mi investigación para esta pregunta, tal definición no parece ser muy útil, o al menos no coincide con mi "intuición" sobre lo que debe ser un menor para un dígrafo. Lo que no me gusta de esa definición es que podría existir más caminos dirigidos después de la contracción de los subconjuntos en vértices individuales de los que había antes.

¿Alguien ha visto una definición de menores para los dígrafos que se ajuste mejor a mi "intuición"? ¿Alguna referencia a un libro o documento (aunque no esté disponible en línea)? Por supuesto, no me importa si el concepto no se llama "menor", sólo me importa el concepto en sí.

Answer 1

En general, no existe una generalización "oficial" de la contracción de aristas a los dígrafos:

Esta es una cita del objetivos de "Nuevas Tendencias en la Teoría de Grafos Estructurales" 09/2010:

Los menores de los grafos no dirigidos se comprenden razonablemente en la actualidad, pero los menores de los grafos dirigidos no. Por ejemplo, ¿qué aristas pueden contraerse? Hay otras cuestiones fundamentales en los grafos dirigidos.

En casos más específicos, parece que los investigadores individuales tienden a elegir una definición de dígrafo menor que parece la más natural para su problema particular. Véase aquí , aquí y aquí (si tiene acceso) para tres trabajos publicados, cada uno de los cuales utiliza su propia versión del operador de contracción de bordes.

Una cosa que hay que tener en cuenta es que se puede utilizar la eliminación de vértices y aristas para crear menores del gráfico, y si se poda cuidadosamente primero se pueden contraer los vértices sin crear aristas o bucles adicionales.

Answer 2

Como parece que tengo cierta "intuición" sobre lo que "debería" ser un dígrafo menor y lo que "no debería", decidí poner a prueba mi "intuición" con algunos dígrafos. Un menor es en realidad la composición de tomar un subgrafo y "tomar un gráfico M". Como no hay confusión en lo que significa "tomar un subgrafo", sólo hay que aclarar lo de "tomar un gráfico M".

En la imagen de abajo, el dígrafo de la derecha es un gráfico M del dígrafo de la izquierda (y del dígrafo del medio), pero el dígrafo del medio no es un gráfico M del dígrafo de la izquierda (según mi "intuición", porque $a2$ no debe ser accesible desde $a3$ ).

, ,

Edición 1 Puede ser una buena idea restringir las contracciones a subconjuntos débilmente conectados, así que he modificado ligeramente la definición de un gráfico M (que pretende formalizar mi "intuición"):

Un dígrafo $G'=(V',E')$ es un gráfico M de un dígrafo $G=(V,E)$ , si existe una función suryectiva $\varphi:V \mapsto V'$ tal que

1. $\varphi^{-1}(\{v'\})$ es un subconjunto débilmente conectado de $G$ para todos $v'\in V'$ ,
2. cada paseo en $G'$ es la imagen bajo $\varphi$ de un paseo en $G$ y
3. cada imagen bajo $\varphi$ de un paseo en $G$ es un paseo en $G'$ .

Aquí un paseo por un dígrafo $G=(V,E)$ es una secuencia $v_0, v_1, \ldots, v_n$ de vértices de $V$ tal que $(v_i,v_{i+1})\in E$ . La imagen de un paseo bajo una función $\varphi$ es la secuencia de las imágenes de los vértices del paseo, donde los vértices sucesivos idénticos han sido sustituidos por un único vértice.

Esto da la siguiente definición de menor para un dígrafo:

Un dígrafo $X$ es un menor de un dígrafo $Y$ , si $Y$ contiene un subgrafo $Z$ para lo cual $X$ es un gráfico M.

Hay casos en los que esta definición permite más menores que mi "intuición":

También hay casos en los que todos los subconjuntos deben contraerse al mismo tiempo, lo que demuestra que las construcciones incrementales que contraen una arista o subconjunto a la vez no funcionan (en general) para esta definición de dígrafo menor:

Debería ser posible demostrar algunas propiedades útiles para esta definición de dígrafo menor. Sin embargo, esto no responde necesariamente a la pregunta de si esta definición de menor de un dígrafo es realmente útil.

Edición 2 La relación menor anterior no es un cuasi ordenamiento bueno, como lo demuestra el siguiente contraejemplo:

Quizá no sea tan buena idea, después de todo, restringir las contracciones a subconjuntos débilmente conectados. Pero incluso sin esta restricción, no está claro si la relación menor correspondiente sería un cuasi-ordenamiento bueno.