¿Hay un dígrafo libre asociado a un gráfico?

Question

Un poco de fondo: Un grafo G es, por supuesto, un conjunto de vértices V(G) y un conjunto múltiple de bordes, que son desordenadas pares de (no necesariamente distintos) vértices. Decimos que dos vértices v_1, v_2 son adyacentes si {v_1, v_2} es una arista. Un grafo dirigido, o dígrafo es esencialmente la misma cosa, excepto que los bordes están ahora de pares ordenados. Los bigramas de tener un lugar agradable categórica interpretación.

Un gráfico homomorphism es exactamente lo que debe ser, de manera categórica, si usted piensa de gráficos como "conjuntos con una adyacencia de la estructura". Es un mapa f: V(G) \rightarrow V(H) es un homomorphism si v_1, v_2 \V(G) adyacentes implica f(v_1), f(v_2) adyacentes. La noción de homomorphism para gráficos es esencialmente el mismo; si hay un borde de v_1 a v_2, entonces hay un borde de f(v_1) a f(v_2). Tomando estas definiciones como morfismos, podemos definir las categorías de los gráficos y de los bigramas.

A menudo en la teoría de grafos (especialmente cuando álgebra lineal métodos entran en juego), es más fácil trabajar con un dígrafo que un gráfico, y por lo que nos suele orientar a los bordes de forma arbitraria. Pero esto no es muy natural...

Hay un olvidadizo functor de la categoría de los bigramas a la categoría de gráficos. ¿Este functor tiene un adjunto? (Se me olvida que es la izquierda y qué es derecha.) Ahora que lo pienso, es lo obvio (reemplazar cada arista por un par de bordes, uno en cada dirección), un adjunto, y si es así ¿hay una manera de cambiar las categorías, de modo que simples gráficos son llevados a simple bigramas?

Answer 1

Me gusta usar las siguientes definiciones, que dan un no estándar de la definición de grafo no dirigido, pero producen particularmente agradable categorías.

Un grafo dirigido es un par de conjuntos V y E, junto con dos mapas de s, t : E -> V. Llame a la categoría de estos DirGraph.

Un grafo no dirigido es un par de conjuntos V y E, junto con dos mapas de s, t : E -> V, además de un mapa de r : E -> E tal que r^2 = 1, sr = t y tr = s. Llame a la categoría de estos UndirGraph.

La interpretación de los gráficos debe ser obvia. Para un grafo no dirigido, de un borde es una órbita bajo r de un elemento de E. tenga en cuenta que hay dos tipos de bucles-órbitas de tamaño 1 o 2.

Podemos representar las categorías de gráficos y espontáneos gráficos como las categorías de presheaves en dos categorías de Directorios y Undir respectivamente (cada uno tiene dos objetos correspondientes a la V y E y un pequeño número de morfismos). Hay una inclusión functor i : Dir -> Undir lo que induce a una restricción functor UndirGraph -> DirGraph; esta es su duplicación functor. Se ha adjoints en ambos lados (izquierdo y derecho Kan extensión). La izquierda adjunto es su "olvidadizo" functor DirGraph -> UndirGraph. El derecho adjoint es otro functor DirGraph -> UndirGraph que a grandes rasgos envía un grafo dirigido G el grafo no dirigido G' con los mismos vértices donde un borde entre v y w en G' es un par de aristas en G, uno de v a w y otro de w a v.

Así que con estas definiciones, no sólo los "olvidadizos" functor tienen derecho adjoint, pero su derecho adjoint también tiene derecho adjuntos.

Answer 2

Al menos, si uno se toma la etiqueta de gráficos (LGrphs) y la etiqueta de los bigramas el functor que usted sugiere, dicen D, es derecho medico adjunto del olvidadizo functor que voy a llamar a la U. Hay una canónica de la transformación natural UD -> Id_{LGrphs} que sólo se derrumba el duplicado de los bordes a los que vinieron. Para una etiqueta dígrafo Q y una etiqueta gráfico de G la bijection en hom-establece, a continuación, envía un mapa UQ -> G para la elevación único Q -> DG que envía cada dirigida borde de Q para el borde correspondiente de la dirección apropiada que levanta la asignación procedente de UQ -> G. supongo que cuando usted acaba de definir morfismos en términos de adyacencia o dirigida de adyacencia y los bordes son indistinguibles, entonces es todavía bien.

Y el comentario a tu pregunta indica que no puede haber una izquierda adjuntos, así que no hay libre dígrafo sólo un cofree uno.