¿Existe una estructura similar a la de un gráfico pero que incluya un sentido de dirección, como norte, oeste, este, sur?

Question

Entiendo que los gráficos no tienen ninguna noción de "enfrentamiento" es decir, un sentido de las direcciones relativas o cardinales. Usando un gráfico convencional, no es posible decir "ir a la izquierda en el vértice A", hasta donde yo entiendo.

Sin embargo, me pregunto si hay est cualquier estructura de este tipo, es decir, que pueda representar vértices y aristas, así como un sentido de lo que podríamos llamar dirección u orientación.

Supongamos que estoy en el vértice A. El vértice A está conectado al vértice Z, con varios vértices intermedios, algunos de los cuales tienen aristas que llevan a otro lugar. Supongamos que tengo prohibido nombrar los vértices/aristas intermedios. ¿Cómo puedo describir el camino de A a Z?

Answer 1

Si quieres que sólo haya una forma de "ir a la izquierda" (etc) en un vértice determinado, lo que buscas es un autómata Por ejemplo, una máquina de estado finito.

Se trata de una estructura con estados (vértices) y transiciones con nombre, y un mapa $\{\mathrm{states}\} \times \{\mathrm{transitions}\} \rightarrow \{\mathrm{states}\}$ . Es decir, en cualquier estado, si especificas la siguiente transición (por ejemplo, "ir a la izquierda") te lleva al siguiente estado apropiado. (Si no quieres que haya una forma de ir a la izquierda en un estado determinado, simplemente harías que la transición fuera al mismo estado).

Esto podría representarse mediante un gráfico dirigido con vértices para los estados y aristas etiquetado por las transiciones, de forma que en cada vértice haya precisamente una arista de salida para cada transición. Entonces, para especificar un camino que comienza en cualquier vértice, basta con nombrar el vértice de inicio y la secuencia de transiciones y esto especifica de forma única un camino.

---

Si sólo desea registrar en qué dirección va una arista, sin duda puede hacer un gráfico etiquetado (quizás uno dirigido) donde las etiquetas son direcciones, pero esto suena menos a lo que quieres.

Answer 2

Una posibilidad es utilizar un sistema de rotación . Dado que ese enlace es un poco técnico, aquí hay una manera un poco más básica de pensar en un sistema de rotación que puede ser más adecuado para sus propósitos. Un sistema de rotación es una función $\Phi$ que asigna a cada vértice $v \in V(G)$ una secuencia ordenada formada por todos los vecinos de $v$ en $G$ . Se suele pensar que un sistema de rotación representa una incrustación de un gráfico en una superficie determinada, de modo que si $\Phi(v) = (v_1, v_2, \dots, v_i)$ , entonces las aristas $(v,v_1),(v,v_2),\dots, (v, v_i)$ se incrustan en ese orden en el sentido de las agujas del reloj alrededor de $v$ en la superficie.

A continuación, hay un par de maneras de definir trayectorias utilizando el sistema de rotación para $G$ :

1. Un camino puede describirse mediante una secuencia formada por dos vértices y números enteros. Por ejemplo, $(u,v,1,4)$ podría describir el camino en $G$ empezando por el borde $(u,v)$ seguido de la arista $(v,w)$ es decir $1$ borde en el sentido de las agujas del reloj de $(u,v)$ en $v$ y, por último, la arista que es $4$ bordes en el sentido de las agujas del reloj de $(v,w)$ en $w$ .

2. O bien, podrías pensar en el primer elemento $u$ de $\Phi(v)$ como un vértice especial, por lo que se podría pensar en $(u,v)$ como orientado al "norte", digamos. Entonces, un camino podría describirse como un vértice junto con una secuencia de enteros. Por ejemplo, $(u,1,4,2)$ podría representar el camino que comienza en $u$ , pasando al primer elemento $v$ en la secuencia $\Phi(u)$ entonces el cuarto elemento $w$ en $\Phi(v)$ y finalmente el segundo elemento de $\Phi(w)$ .