Contar los caminos dirigidos en un determinado grafo dirigido

Question

Quiero averiguar cuántos caminos simples dirigidos desde $s$ a $t$ están en el siguiente grafo dirigido $G=(V,E)$ .

$$\begin{align} V=&\{s, v_1, v_2,\ldots, v_n, t\}, \quad n=2k, k \in \mathbb{N} \\ E=&\{ (s, v_1), (s, v_2), \\ &\;(v_1,v_3), (v_1,v_4), (v_2,v_3),(v_2,v_4), \\ &\;(v_3,v_5), (v_3,v_6), (v_4,v_5), (v_4,v_6), \\ &\;\ldots, \\ &\;(v_{n-5},v_{n-3}), (v_{n-5},v_{n-2}), (v_{n-4},v_{n-3}), (v_{n-4},v_{n-2}), \\ &\;(v_{n-3},v_{n-1}), (v_{n-3},v_{n}), (v_{n-2},v_{n-1}), (v_{n-2},v_{n}), \\ &\;(v_{n-1},t), (v_{n},t) \} \end{align}$$

En mi opinión, hay $n$ caminos dirigidos. ¿Es eso cierto?

Answer 1

Para cada vértice del gráfico, el nivel del vértice es la longitud del camino dirigido más corto desde $s$ a ese vértice. Así que $s$ tiene nivel $0$ , $v_{2l-1}$ & $v_{2l}$ tienen nivel $l$ y $t$ tiene nivel $k+1$ . Obsérvese que cada camino dirigido desde $s$ a $t$ contienen exactamente un vértice de cada nivel.

Dejemos que $s=u_0 \to u_1 \to u_2 \to\ldots \to u_k \to u_{k+1}=t$ sea un camino dirigido. Obsérvese que $u_i$ tiene nivel $i$ . Para cada $u_i$ ( $0\le i \le k-1$ ), siempre hay dos posibles vértices de nivel $i+1$ y $(u_i,u_{i+1})$ es siempre una arista dirigida en $G$ . Además sólo hay una opción después de $u_k$ . Por lo tanto, el número de estos caminos es $2^k$ .

---

También he pensado en la propuesta de bof de considerar caminos no dirigidos. Aquí hay una prueba.

Tenga en cuenta que para una ruta no dirigida $s=u_0\to u_1\to u_2\to\ldots \to u_r \to u_{r+1}=t$ hay a lo sumo un movimiento posible hacia atrás en cada $u_i$ y si $u_{i+1}$ se obtiene mediante un movimiento hacia atrás, $u_{i+1}$ debe ir a $u_{i+2}$ con un movimiento único hacia adelante. Entonces, no podemos hacer otro movimiento hacia atrás, por lo que tenemos que realizar otro movimiento hacia adelante. Llamemos a tal secuencia de retroceso-seguido-por-adelante-dos veces un bucle . Obsérvese que no se pueden hacer dos bucles consecutivos.

Obsérvese también que si no estamos en un vértice en el que se acaba de realizar un movimiento hacia atrás, siempre hay dos opciones posibles para avanzar (salvo que se esté en $v_{2k-1}$ o $v_{2k}$ donde el único movimiento hacia adelante es ir a $t$ ). Por lo tanto, nuestro camino puede ser representado por una secuencia binaria de longitud $k+1$ , donde $0$ es un movimiento hacia adelante y $1$ es un bucle, tal que la secuencia comienza con dos $0$ y no hay dos $1$ se producen sucesivamente.

Hay $F_{k+1}$ tales secuencias binarias (ya que la eliminación de los dos $0$ al principio, se encuentra en la situación de este pregunta ). Aquí $F_k$ es el $k^\text{th}$ Número de Fibonacci con $F_0=0$ y $F_1=1$ . Hay $k$ movimientos hacia adelante, cada uno con dos opciones (recordando que el movimiento final hacia adelante sólo tiene una opción posible). Esto le da un factor $2^k$ . Por lo tanto, hay $2^kF_{k+1}$ caminos no dirigidos de $s$ a $t$ .