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 v0,v1,v2,…,vn de manera que vi−1 es adyacente de vi, para i=1,2,…,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,v1,v2,…,vn,b. Si este camino no fuera simple, ello significaría --por definición-- que un vértice se repite, digamos el vk y el vm, con k<m. Entonces, eliminando los vértices intermedios vk+1,vk+2…,vm−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