¿Existe una estructura monoide en el conjunto de caminos de un grafo?

Question

Dado un grafo G, y el conjunto de caminos en G llamado Path _G .

¿Existe una estructura monoide en Path _G ? ¿Será la concatenación la fórmula de multiplicación? aunque no esté definida para algunos caminos?
¿Y la identidad?

Answer 1

La respuesta de Eric es correcta, pero hay mucho más que decir aquí.

En primer lugar, no es necesario empezar con un gráfico para que esto funcione; podemos empezar con un dígrafo arbitrario. Por desgracia, el término "dígrafo" es un poco ambiguo, así que prefiero llamar a estas cosas quivers . Básicamente significa "dígrafo, posiblemente con bucles, posiblemente con múltiples aristas".

Ahora a cada carcajada $X$ podemos asignar una categoría $\mathrm{Path}(X)$ de la siguiente manera: los objetos son sólo $X$ -los morfismos son secuencias componibles de $X$ -morfismos, la composición es por concatenación de secuencias, y las identidades son secuencias vacías.

Este proceso es functorial: dado un morfismo de quivers $$f:X \rightarrow Y,$$ obtenemos el correspondiente morfismo de categorías (es decir, un functor) $$\mathrm{Path}(f) : \mathrm{Path}(X) \rightarrow \mathrm{Path}(Y).$$ En otras palabras, tenemos un functor $$\mathrm{Path} : \mathbf{Quiv} \rightarrow \mathbf{Cat}.$$ Resulta ser conjunta a la izquierda con el functor subyacente del carcaj $\mathbf{Cat} \rightarrow \mathbf{Quiv}.$ Esto demuestra que el functor subyacente del quiver preserva los límites, y que $\mathrm{Path}$ preserva los colímetros.

Por tanto, la construcción de la "categoría de caminos" también puede denominarse construcción de la "categoría libre en un carcaj".

Supongamos ahora que $S$ es un conjunto. Entonces hay un monoide libre en $S$ , que se suele denominar $S^*$ . Se puede definir como el conjunto de todas las palabras finitas del alfabeto $S$ . Pero tenga en cuenta que $S^*$ no es sólo un monoide; en realidad es un involutivo monoide, con involución dada por inversión de palabras. La involución satisface $$(ab)^\dagger = b^\dagger a^\dagger, \qquad 1^\dagger = 1.$$

Los monoides involutivos deberían llamarse realmente "monoides daga", en mi opinión, porque también hay monoides dotados de una involución $x \mapsto \overline{x}$ Satisfaciendo a $$\overline{xy} = \overline{x}\overline{y}, \qquad \overline{1} = 1,$$ y parece injusto que no sean "monoides involutivos" según la definición habitual.

En fin, de forma similar, $\mathrm{Path}(X)$ no es sólo una categoría; de hecho, siempre es una categoría de daga . (¡Esta es una buena terminología!)

Además, $\mathrm{Path}(f)$ juega bien con la estructura de la daga. Por lo tanto, obtenemos un functor $$\mathrm{Path} : \mathbf{Quiv} \rightarrow \mathbf{DagCat}.$$ Ten cuidado: el functor anterior no es conjunto a la izquierda con el functor olvidadizo $\mathbf{DagCat} \rightarrow \mathbf{Quiv}$ .

Por último, hay que tener en cuenta que $\mathrm{Path}$ generaliza la construcción del monoide libre. Es así:

• dado un conjunto $S$ podemos construir un carcaj $\dot{S}$ con un objeto, y un morfismo para cada elemento de $S$ .

• dado un monoide $M$ podemos construir una categoría $\mathbb{B}M$ con un objeto, y un morfismo para cada elemento de $M$ . La composición de morfismos viene dada por la operación de multiplicación de $M$ el morfismo de identidad viene dado por $1_M$ .

Está claro que $$\mathrm{Path}(\dot{S}) \cong \mathbb{B}(S^*).$$ Por lo tanto, ya que $\mathbb{B}$ es una incrustación de categorías, podemos escribir $$S^* \cong \mathbb{B}^{-1}(\mathrm{Path}(\dot{S}))$$ y así obtener monoides libres como un caso especial del $\mathrm{Path}$ construcción.

Answer 2

No, en un monoide la multiplicación siempre está definida, así que $\mathrm{Path}_G$ no forma un monoide bajo concatenación. Sin embargo, sí forma un categoría con un objeto para cada vértice. El conjunto de morfismos entre dos vértices es entonces sólo el conjunto de caminos entre ellos, y esto funciona perfectamente porque sólo se necesita poder componer morfismos cuando son caminos que se pueden concatenar. Los morfismos de identidad son los caminos de longitud $0$ que comienzan en un vértice y luego no van a ninguna parte.

Answer 3

Como se explica en Respuesta de Eric wofsey podemos ver el gráfico $G$ como una categoría con $\mathrm{Path}_G$ como su conjunto de morfismos, y la simple concatenación de caminos como composición - obsérvese que con esta definición, la composición de dos caminos puede no ser una camino en el sentido habitual de la teoría de grafos, sino un caminar . En este caso, debemos definir $\mathrm{Path}_G$ para incluir todos los ámbitos de $G$ y no simplemente caminos, y es entonces un conjunto infinito. Si modificamos ligeramente la definición de composición, podemos restringir $\mathrm{Path}_G$ para que sólo contenga caminos adecuados, y obtener un groupoid (en lugar de un monoide, como pide la pregunta).

Un grupo no es un caso especial ni una generalización de un monoide. Es una generalización de un grupo (como lo es un monoide, pero en una dirección diferente). La composición en un groupoide no es (necesariamente) una operación binaria - es una función parcial. Al igual que un monoide puede definirse como una categoría con un objeto, un grupoide puede definirse como una categoría (pequeña) en la que cada morfismo es un isomorfismo . Estas definiciones también hacen evidente que un grupo es un caso especial de estos dos conceptos, ya que un grupo es una categoría de un objeto (por lo tanto, un monoide) en la que cada morfismo es un isomorfismo (por lo tanto, un grupoide).

Ahora bien, para definir un groupoide utilizando los caminos de un grafo, tenemos que ser capaces de componer dos caminos y obtener un camino propio (que posiblemente sea más pequeño que la concatenación de los dos). Consideremos dos caminos $\alpha$ y $\beta$ , desde el vértice $u$ al vértice $v$ y de $v$ a $w$ respectivamente. Dejemos que la trayectoria $\alpha$ sea dada por $u = u_0, u_1, \ldots, u_m = v$ y, del mismo modo, dejemos que $\beta$ sea $v = v_0, v_1, \ldots, v_n = w$ . Sea $i \ge 0$ sea el menor número entero para el que $u_i = v_j$ para algunos $j$ entre $0$ y $n$ . Así, $u_i = v_j$ es el primer vértice de $\alpha$ que es común a la ruta $\beta$ . Definir $\alpha \circ \beta$ para ser el camino $u = u_0, u_1, \ldots, u_i = v_j, v_{j+1}, \ldots, v_m = w$ , de $u$ a $w$ . Entonces $\alpha \circ \beta$ no tiene vértices repetidos, y por lo tanto es un camino propio desde $u$ a $w$ . Tenga en cuenta que si $\alpha$ y $\beta$ no tienen vértices comunes, excepto $v$ Esta composición es una mera concatenación. Además, si $u = w$ entonces $\alpha \circ \beta$ es la ruta "vacía" de $u$ a sí mismo.

Ejemplo

Aquí, $\alpha$ es el camino $u = u_0, u_1, u_2, u_3, u_4 = v$ , de $u$ a $v$ y $\beta$ es el camino $v = v_0, v_1, v_2, v_3, v_4, v_5, v_6 = w$ , de $v$ a $w$ . El primer vértice de $\alpha$ que es común a $\beta$ es $u_2 = v_4$ (así $i = 2$ y $j = 4$ en la definición). Por lo tanto, la composición $\alpha \circ \beta$ es el camino $u = u_0, u_1, u_2 = v_4, v_5, v_6 = w$ , de $u$ a $w$ . Se trata, por tanto, de un camino de longitud $4$ mientras que $\alpha$ y $\beta$ son caminos de longitud $4$ y $5$ respectivamente. El concatenación de $\alpha$ y $\beta$ por otro lado, es un paseo de longitud $9$ (uno que va de $u$ a $v$ en cuatro pasos, y de $v$ a $w$ en cinco pasos, revisando los vértices $v_2 = u_3$ y $v_4 = u_2$ en el camino).

Podemos imponer una estructura de grupo en $\mathrm{Path}_G$ considerándola como una categoría con vértices para los objetos, caminos para los morfismos, y con la composición de estos morfismos como se ha definido anteriormente. Esta composición es asociativa, y para cada camino, hay un camino inverso. La inversa del camino $v_0, v_1, \ldots, v_n$ del vértice $v_0$ al vértice $v_n$ es el camino $v_n, v_{n-1}, \ldots, v_0$ de $v_n$ a $v_0$ . El morfismo de identidad de un vértice $u$ es la ruta vacía de $u$ a sí mismo.

En el ejemplo anterior, $\alpha^{-1}$ es el camino $v = u_4, u_3, u_2, u_1, u_0 = u$ , de $v$ a $u$ y $\beta^{-1}$ es $w = v_6, v_5, \ldots, v_1, v_0 = v$ , de $w$ a $v$ . Su composición $\beta^{-1} \circ \alpha^{-1}$ es $w = v_6, v_5, v_4 = u_2, u_1, u_0 = u$ , de $w$ a $u$ (como $v_4 = u_2$ es el primer vértice de $\beta^{-1}$ común a $\alpha^{-1}$ ). Tenga en cuenta que $\beta^{-1} \circ \alpha^{-1} = (\alpha \circ \beta)^{-1}$ como era de esperar.