Caminos, conexidad y distancia#
Introducción#
De manera informal, los caminos, paseos y trayectorias nos ayudan a saber «cuándo se puede llegar de un vértice a otro», ya sea sin restricciones, o con algunas restricciones. En la modelación esto nos puede ayudar a determinar, por ejemplo, cómo llegar de una ciudad a otra mediante carreteras existentes entre parejas de ciudades. También nos puede decir cómo a través únicamente de conocidos es posible que una persona consiga conocer a otra.
A partir de las nociones anteriores es posible hablar de conexidad y de distancia en gráficas. La conexidad habla de cuándo sí se puede llegar de cualquier vértice a cualquier otro. La distancia habla de «qué tan rápido» es posible hacer esto.
Caminos, paseos y trayectorias#
Definición. Sea \(G\) una gráfica. Un camino es una sucesión \(v_1,v_2,\ldots, v_n\) de vértices (no necesariamente distintos) en donde \(v_iv_{i+1}\) es una arista de \(G\) para cada \(i\in\{1,\ldots,n-1\}\). Los vértices \(v_i\) son los vértices del camino y las aristas \(v_iv_{i+1}\) son las aristas del camino. A \(v_1\) le llamamos el vértice inicial y a \(v_n\) el vértice final. Decimos también que el camino comienza en \(v_1\) y termina en \(v_n\), o bien simplemente que va de \(v_1\) a \(v_n\). Este camino pasa por \(n-1\) aristas (no necesariamente distintas), así que su longitud es \(n-1\).
Ejemplo. En la siguiente gráfica se ha marcado el camino \(h,c,a,f,b,h,g\).
El vértice inicial es \(a\). El vértice final es \(g\). Algunas aristas del camino son \(fb\), \(hg\) y \(ca\). La longitud del camino es \(6\). \(\square\)
Hay que tener un poco de cuidado con los dibujos de los caminos. Por ejemplo, el dibujo anterior también podría ser el dibujo del camino \(g,h,c,a,f,b,h\). Además la definición de camino es muy flexible y permite repeticiones arbitrarias. La única condición es que de un vértice al siguiente haya una arista. De este modo, en la gráfica anterior también tenemos el camino \(a,i,d,c,a,i,a,h,c\), cuyo dibujo también es muy ambiguo. En la duda, es mejor ir directamente a leer el camino como una sucesión de vértices.
Si restringimos lo que se puede repetir en un camino obtenemos las siguientes dos nociones.
Definición. Sea \(G\) una gráfica. Un paseo es un camino con todas sus aristas distintas.
Ejemplo. En la siguiente gráfica se muestra el paseo \(e,b,h,a,g,d,c,a,i\). El vértice \(a\) se repite, pero esto no es problema. Únicamente estamos pidiendo que no se repitan las aristas.
Este es un paseo de \(e\) a \(i\) de longitud \(8\). \(\square\)
Definición. Sea \(G\) una gráfica. Una trayectoria es un camino con todos sus vértices distintos.
Ejemplo. En el ejemplo anterior teníamos al paseo \(e,b,h,a,g,d,c,a,i\). Este paseo no es una trayectoria, pues repite al vértice \(a\). Sin embargo, en la siguiente figura sí tenemos una trayectoria.
El dibujo sigue siendo un poco ambiguo, pues podría indicar la trayectoria \(e,g,h,c,a,i,b\), o bien la trayectoria inversa \(b,i,a,c,h,g,e\). Sin embargo, la abigüedad se reduce mucho pues ya nada más tenemos dos casos. \(\square\)
Propiedades básicas#
En la sección anterior ya vimos ejemplos de caminos que no son paseos y de paseos que no son trayectorias. ¿Qué pasa si comenzamos con una trayectoria? ¿Necesariamente será un paseo? Sí. Si un camino repite aristas, entonces repite vértices. En contapositiva, si no repite vértices, entonces no repite aristas. Concluimos entonces lo siguiente.
Proposición. Toda trayectoria es un paseo.
Así, de entre las nociones que hemos discutido la de «ser trayectoria» es la más restrictiva.
Es posible que tengamos un camino de \(u\) a \(v\) que no sea paseo, o que no sea trayectoria. Sin embargo, la siguiente proposición nos dice que la existencia de este camino garantiza la existencia de una trayectoria.
Proposición. Sea \(G\) una gráfica y \(u\), \(v\) dos vértices. Las siguientes tres proposiciones son equivalentes:
Existe una trayectoria de \(u\) a \(v\).
Existe un paseo de \(u\) a \(v\).
Existe un camino de \(u\) a \(v\).
Demostración. Si hay una trayectoria \(C\) de \(u\) a \(v\), entonces por la proposición anterior \(C\) también es un paseo. Y si hay un paseo \(C\) de \(u\) a \(v\), entonces por definición \(C\) es un camino. Sólo nos falta ver que si hay un camino \(C\) de \(u\) a \(v\), entonces podemos encontrar una trayectoria. Para hacer esto, procederemos por principio extremo.
Como existe un camino de \(C\) de \(u\) a \(v\), entonces existe un camino de longitud mínima de \(u\) a \(v\), digamos \(T\), cuyos vértices en orden son \(v_0,v_1,v_2,\ldots,v_n\) con \(v_0=u\) y \(v_n=v\). Observa que la longitud de \(T\) es \(n\). Afirmamos que este camino es una trayectoria. De no ser así, existirían dos subíndices \(i<j\) tales que \(v_i=v_j\). Pero entonces el camino \(T'\) cuyos vértices en orden son \(v_0,v_1,\ldots,v_{i-1},v_i,v_{j+1},\ldots,v_n\) sería un camino de \(u\) a \(v\) con longitud \(n-(j-i)<n\). Esto contradice la minimalidad de la longitud de \(T\). La contradicción salió de suponer que \(T\) no es trayectoria, así que en efecto \(T\) sí lo es.\(\square\)
Conexidad#
A partir de la noción de camino podemos decir cuándo dos vértices de una gráfica están conectados. Esto a su vez nos permitirá definir cuándo una gráfica está conectada.
Definición. Sea \(G\) una gráfica y \(u,v\) vértices de la gráfica. Diremos que \(u\) está conectado a \(v\) si existe una trayectoria que comienza en \(u\) y termina en \(v\).
La definición está dada en términos de la existencia de una trayectoria de \(u\) a \(v\). Sin embargo, por la última proposición de la sección anterior, sería totalmente equivalente dar la definición en términos de la existencia de un camino de \(u\) a \(v\), o bien de la existencia de un paseo de \(u\) a \(v\). Esta flexibilidad en la perspectiva nos ayudará a demostrar propiedadaes de la conexidad fácilmente.
Ejemplo. En la siguiente gráfica se muestra una trayectoria de \(d\) a \(f\), así que el vértice \(d\) está conectado al vértice \(f\).
Puedes verificar que, sin embargo, el vértice \(h\) no está conectado al vértice \(b\). ¿Por qué? \(\square\)
Proposición. La relación «está conectado a» es una relación de equivalencia en los vértices de la gráfica.
Demostración. Debemos ver que esta relación es reflexiva, simétrica y transitiva.
Reflexiva: Cada vértice \(v\) está conectado a sí mismo mediante la trayectoria \(v_1\) donde \(v_1=v\).
Simétrica: Si \(u\) está conectado a \(v\), es porque existe una trayectoria de la forma \(v_1, v_2, \ldots, v_n\) con \(v_1=u\) y \(v_n=v\). De esta manera, \(v_n, v_{n-1}, \ldots, v_2, v_1\) es una trayectoria de \(v\) a \(u\), y por lo tanto \(v\) está conectado a \(u\).
Transitiva: Tomemos \(u\), \(v\) y \(w\) con \(u\) conectado a \(v\) y \(v\) conectado a \(w\). Esto significa que existen trayectorias
\[v_1,v_2,\ldots,v_n\]y
\[w_1,w_2,\ldots,w_m\]con \(v_1=u\), \(v_n=w_1=v\) y \(w_m=w\).
Al concatenar las trayectorias (1) y (2) obtenemos un camino de \(u\) a \(w\):
\[v_1, v_2, \ldots v_{n-1}, v_n, w_2, w_{m-1}, w_n.\]Este camino no necesariamente es una trayectoria. Sin embargo, su existencia nos garantiza la existencia de una trayectoria de \(u\) a \(w\), así que \(u\) está conectado a \(w\). \(\square\)
Como la relación «estar conectado a» es una relación de equivalencia, entonces además de decir «\(u\) está conectado a \(v\)» también decimos «\(u\) y \(v\) están conectados».
Cuando se tiene una relación de equivalencia sobre un conjunto, éste queda partido en subconjuntos de tal manera que dentro de un mismo subconjunto todos los elementos están relacionados entre sí. A estos subconjuntos se le llaman las clases de equivalencia de la relación. En nuestro caso nos interesan estas clases de equivalencia pues podemos encontrar trayectorias entre cualesquiera dos vértices de una misma clase.
Definición. Una componente conexa de una gráfica es una clase de equivalencia de la relación «está conectado a».
Definición. Diremos que una gráfica \(G\) es conexa si tiene exactamente una componente conexa.
Ejemplo. Considera las siguientes dos gráficas:
La gráfica de la izquierda tiene tres componentes conexas, que están indicadas con los colores rojo, verde y negro de la siguiente figura. Verifica que en efecto se puede llegar de cualquier vértice a cualquiera del mismo color, pero que no se puede llegar de un vértice a uno de color distinto.
La gráfica de la derecha es conexa, pues su única componente conexa consiste de los vértices en gris. En otras palabras, se puede llegar de cualquier vértice a cualquier otro. \(\square\)
¿Cómo le podríamos hacer para determinar de manera intuitiva si una gráfica es conexa? Podemos hacer los siguientes pasos. Tomamos un vértice. Sus vecinos están en la misma componente conexa que él. Los vecinos de sus vecinos también. Continuamos sucesivamente hasta que ya no estemos agregando nuevos vértices. Si al hacer este procedimiento pasamos por todos los vértices, entonces la gráfica es conexa. Si nos faltaron vértices, estos están en una componente conexa distinta. Más adelante formalizaremos este procedimiento en términos de un algoritmo.
Distancia#
Otra noción que podemos construir a partir de la existencia de trayectorias es la de distancia en una gráfica. Muy a grandes rasgos, nos dice cuál es el mínimo número de aristas que debemos recorrer para llegar de un vértice a otro.
Definición. Sea \(G\) una gráfica conexa. La distancia entre dos vértices \(u\) y \(v\) es la mínima posible longitud de alguna trayectoria que los conecta. En símbolos, la llamaremos \(d(u,v)\).
Ejemplo. Considera la siguiente gráfica:
¿Cuál es la distancia entre los vértices \(e\) y \(f\)? Notemos que hay una trayectoria de \(e\) a \(f\) que es la siguiente: \(e,b,i,a,f\). Esta es una trayectoria de longitud \(4\). ¿Esto quiere decir que la distancia es \(4\)? No, pues hay una trayectoria más corta posible: la \(e,g,a,f\), que es de longitud \(3\) y se muestra a continución:
¿Tenemos entonces \(d(e,f)=3\)? Sí, pues se puede verificar que no es posible llegar de \(e\) a \(f\) en una trayectoria de dos o menos aristas. \(\square\)
La distancia en gráficas en efecto tiene las propiedades matemáticas necesarias para ser llamada así.
Proposición. Sea \(G\) una gráfica conexa. La distancia entre vértices en \(G\) es una métrica es decir:
Es un número real no negativo: \(d(u,v)\in \mathbb{R}^+ \cup\{0\}\).
La distancia entre dos vértices es cero si y sólo si son iguales: \(d(u,v)=0 \Leftrightarrow u=v\).
La distancia es simétrica: \(d(u,v)=d(v,u)\).
Se cumple la desigualdad del triángulo. \(d(u,w)\leq d(u,v)+d(v,w)\).
Demostración. La primera parte es inmediata, pues como la gráfica es conexa, siempre existe por lo menos una trayectoria entre cualesquiera dos vértices. Entonces, existe una trayectoria mínima y su longitud siempre es un número entero no negativo. Para que la distancia entre dos vértices \(u\) y \(v\) sea igual a cero, es necesario que exista una trayectoria de longitud cero entre ellos, es decir, una trayectoria sin aristas. Esto es posible si y sólo si \(u=v\).
Veamos que la distancia es simétrica. Supongamos que \(d(u,v)=n\) y que \(d(v,u)=m\). Así, hay una trayectoria de longitud \(n\) entre \(u\) y \(v\), digamos \(v_0,\ldots,v_n\). Notemos que \(v_n,\ldots,v_0\) es una trayectoria de longitud \(n\) entre \(v\) y \(u\). Como \(m\) es la distancia de \(v\) a \(u\), tenemos \(m\leq n\). De manera análoga, una trayectoria de longitud \(m\) de \(v\) a \(u\) al voltearla se convierte en una trayectoria de longitud \(m\) de \(u\) a \(v\). Como \(n\) es la distancia de \(u\) a \(v\), tenemos \(n\leq m\). Así, \(m=n\).
Finalmente, veamos que se cumple la desigualdad del triángulo. Supongamos que \(d(u,v)=m\) y que \(d(v,w)=n\). De este modo, hay una trayectoria \(C\) de \(u\) a \(v\) de longitud \(m\) y una \(C'\) de \(v\) a \(w\) de longitud \(n\). Al concatenar estas dos trayectorias, encontramos un camino \(C''\) de \(u\) a \(w\) de longitud \(m+n\). En caso de ser necesario, podemos recortar este camino para volverlo una trayectoria \(T\) de longitud \(k\leq m+n\). Sin embargo, \(d(u,w)\) es la longitud de una trayectoria mínima de \(u\) a \(w\), de modo que
Esto termina la demostración. \(\square\)
También es posible definir una distancia extendida para una gráfica que no necesariamente sea conexa. Si dos vértices \(u\) y \(v\) están en la misma componente conexa, definimos \(d(u,v)\) como la mínima posible longitud de una trayectoria de \(u\) a \(v\). Si \(u\) y \(v\) están en componentes distintas, entonces definimos \(d(u,v)=\infty\). Puedes verificar por tu cuenta que esta distancia extendida también cumple las propiedades de la proposición anterior, en donde para la desigualdad del triángulo entendemos \(\infty+d=\infty+\infty=\infty\), y que \(\infty\) es una distancia mayor o igual a cualquier otra.
Tarea moral#
Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.
Considera la siguiente gráfica:
¿Cuántas trayectorias hay de \(a\) a \(g\)?
¿Cuántos paseos hay de \(a\) a \(g\)?
Determina si las siguientes afirmaciones son verdaderas o falsas, dando prueba o contraejemplo respectivamente:
Sean \(u,v,w\) vértices distintos de una gráfica \(G\). Si existe un camino de \(u\) a \(w\) que pase por \(v\), entonces existe una trayectoria de \(u\) a \(w\) que pase por \(v\).
Sean \(u,v,w\) vértices distintos de una gráfica \(G\). Si existe un camino de \(u\) a \(w\) que no pase por \(v\), entonces existe una trayectoria de \(u\) a \(w\) que no pase por \(v\).
Considera la siguiente gráfica:
¿Cuáles son los dos vértices que están más alejados entre sí?
¿Cuál es la longitud de la trayectoria más grande que puedes encontrar?
Demuestra que sin importar qué arista quites, la gráfica sigue siendo conexa.
¿Será posible quitar dos aristas y que la gráfica se desconecte? Si sí, ¿de cuántas formas?
Construye una gráfica como sigue. Los vértices son los números del \(50\) al \(100\). Ponemos una arista entre dos vértices si existe un número primo que divide a ambos. Por ejemplo, hay una arista entre el 68 y el 85 pues a ambos los divide el \(17\). Encuentra algunos vértices aislados en esta gráfica para concluir que no es una gráfica conexa. ¿Cuántas componentes conexas tiene esta gráfica?
Adapta el enunciado de las propiedades de la distancia en gráficas para el caso en el que la gráfica no sea conexa, y demuestra la versión correspondiente.