En este post voy a presentar otro grupo de conceptos de la teoría de grafos, ligados a la noción de camino --la metáfora obvia es un mapa de carreteras. El significado usual de camino es una vía, una ruta, por la que se transita para ir de un lugar geográfico a otro --quizá pasando por otros lugares. El significado es tan básico que su definición sale sobrando. En teoría de grafos
Un camino es una sucesión de aristas de manera que, a excepción de la primera, el segundo vértice de una es el primer vértice de la siguiente.
Una definición alternativa sería
Un camino es una sucesión de vértices $v_0,v_1,v_2,\ldots,v_n$ de manera que $v_{i-1}$ es adyacente de $v_i$, para $i=1,2,\ldots,n$
Al igual que las nociones básicas de vértice, arista, y adyacencia están basadas en la metáfora geométrica del poliedro, los de camino, ciclo, y conexidad conviene asociarlos a la metáfora geográfica de un mapa de carreteras.
A partir de la definición de camino se definen varios otros conceptos:
Longitud de un camino: número de aristas que lo componen.
Camino simple: es un camino en que todas sus vértices son diferentes (no repite vértices).
Teorema: Si $u,v$ son vértices de un grafo $G$ y hay un camino de $a$ a $b$, entonces hay un camino simple de $a$ a $b$.
Demostración
Por hipótesis existe un camino entre $a$ y $b$. Elegimos el de longitud más corta, digamos $a,v_1,v_2,\ldots,v_n,b$. Si este camino no fuera simple, ello significaría --por definición-- que un vértice se repite, digamos el $v_k$ y el $v_m$, con $k<m$. Entonces, eliminando los vértices intermedios $v_{k+1}, v_{k+2}\ldots,v_{m-1}$, tenemos un camino entre $a$ y $b$ más corto que el mínimo. Contradicción.
Ciclo: es un camino que empieza y acaba en el mismo vértice.
Ciclo simple: es un ciclo en que todos sus vértices son diferentes (no repite vértices.
Problema: Sea $G$ un grafo de la amistad (friendship graph), es decir, si $u,v$ son dos vértices distintos de $G$ entonces existe exactamente un vértice $z$ adyacente a $u$ y $v$. Demostrar que $G$ no tiene ciclos de longitud 4.
Solución
Si un tal ciclo existiera en $G$, entonces $G$ no cumpliría la condición de la amistad. (Sean $t,u,v,w,t$ los vértices del ciclo. Entonces $v$ y $t$ tienen a dos vértices adyacentes en común: $u$ y $w$.)
Grafo conexo: Es un grafo que tiene un camino entre cualquiera dos de sus vértices.
Teorema: Si $G$ es un grafo conexo, entonces existe un camino simple entre cualesquiera dos vértices de $G$.
Demostración: Se deja al lector (Sugerencia: verl teorema arriba demostrado.)
Ejercicio
Construir un grafo cuyos vértices son las 3-cadenas de ceros y unos y sus aristas representan la relación "difieren al menos en tres posiciones" (Por ejemplo, existe una arista entre 000 y 110.)
Los saluda
jmd