Camino (Teoría de Grafos)
Un camino en un grafo es una secuencia de vértices conectados por aristas donde ningún vértice se repite, y representa una ruta a través del grafo.
Definition
Un camino en un grafo es una ruta de un vértice a otro que sigue aristas sin revisitar ningún vértice, un recorrido sin retroceder a un lugar donde ya se ha estado. Formalmente, un camino es una secuencia de vértices distintos $v_0, v_1, \ldots, v_k$ tal que cada par consecutivo $\{v_i, v_{i+1}\}$ es una arista; la longitud del camino es $k$, un camino cerrado ($v_0 = v_k$) es un ciclo, y un grafo es conexo si existe un camino entre cada par de vértices. La distancia $d(u,v)$ es la longitud del camino más corto de $u$ a $v$; el diámetro de $G$ es $\max_{u,v} d(u,v)$ y la circunferencia es la longitud del ciclo más corto, con los caminos más cortos encontrados mediante el algoritmo de Dijkstra (pesos no negativos) o el de Bellman-Ford (permite pesos negativos, detecta ciclos negativos).
Example
En un grafo de mapa de ciudad, un camino de Casa a Escuela podría ir Casa, Biblioteca, Parque, Escuela, visitando cada lugar exactamente una vez. En un grafo con vértices $\{1,2,3,4\}$ y aristas $\{12,23,34,14\}$, el camino $1$-$2$-$3$-$4$ tiene longitud $3$ y es Hamiltoniano (visita cada vértice exactamente una vez). El problema P frente a NP se conecta estrechamente aquí: encontrar un camino Hamiltoniano es NP-completo, mientras que encontrar un camino Euleriano (recorriendo todas las aristas una vez) se resuelve en tiempo polinomial, y encontrar el camino más corto está en P, una dicotomía que muestra cómo ligeros cambios en las restricciones alteran dramáticamente la dificultad algorítmica.
Key Insight
Encontrar el camino más corto entre dos vértices es uno de los problemas más importantes en la teoría de grafos, resuelto por algoritmos como los de Dijkstra y Bellman-Ford. En la teoría algebraica de grafos, el número de caminatas de longitud $k$ de $u$ a $v$ es igual a la entrada $(u,v)$ de $A^k$ (la $k$-ésima potencia de la matriz de adyacencia), conectando el conteo de caminos con el álgebra lineal.