[MÚSICA] En este video introducimos el concepto de conectividad a nivel de nodos y de grafos. Comenzaremos definiendo los conceptos de accesibilidad y conectividad a nivel de nodos. Luego, extenderemos estas ideas para definir lo que es un grafo conexo y un grafo fuertemente conexo. Comencemos entonces con los conceptos de accesibilidad y conectividad a nivel de nodos. Se dice que un nodo j está conectado con un nodo i si existe una ruta entre i y j. Diremos además que un nodo j es accesible desde i si existe una ruta dirigida de i a j. Podemos decir entonces que la accesibilidad es como la conectividad, pero considerando el sentido de los arcos. Para ilustrar estos conceptos, observemos el siguiente grafo. Miremos los nodos: dos y cinco. ¿Están conectados estos nodos? Dos nodos están conectados si existe una ruta, no necesariamente dirigida, que los une. En este caso existen muchas rutas que conectan estos nodos a nodos, incluido la ruta formada por el arco dos, cinco. Por lo tanto, podemos concluir que los nodos dos y cinco sí se encuentran conectados. Miremos nuevamente a los nodos 2 y 5. ¿Es accesible dos desde cinco? La ruta dirigida formada por el arco dos, cinco permite llegar a dos desde el nodo cinco, por lo tanto dos es accesible desde cinco. ¿Y al revés? ¿Podemos decir que cinco es accesible desde dos? Un chequeo al ojo permite concluir que no hay una ruta desde dos hasta cinco. Para demostrar esto, debemos revisar cuáles nodos son accesibles desde dos. Dos nos permite llegar a tres. Tres nos permite llegar a uno y a seis, y seis a siete. En este momento, podemos notar que no existen más nodos del grafo que se pueden alcanzar desde los nodos accesibles desde dos, que están marcados en rojo, lo que nos permite confirmar que el nodo cinco no es accesible desde dos. Definamos ahora el concepto de conexión a nivel de grafo. Se dice que un grafo es conexo si para cualquier par de nodos i, j existe una ruta, no necesariamente dirigida, desde i a j. Esta definición se puede acotar para incorporar el sentido de los arcos. Se dice, entonces, que un grafo es fuertemente conexo si para cualquier par de nodos i,j existe una ruta dirigida desde i a j. De hecho, así como la accesibilidad entre nodos puede ser entendida como conectividad que considera el sentido de los arcos, podemos también decir que un grafo fuertemente conexo es un grafo conexo donde se considera el sentido de los arcos. En otras palabras, un grafo conexo requiere conectividad entre cualquier par de nodos, mientras que un grafo fuertemente conexo requiere accesibilidad entre cualquier par de nodos. Volvamos a mirar el grafo del último ejemplo. ¿Es este grafo conexo? La respuesta es claramente sí. De hecho, basta con confirmar que un nodo cualquiera esté conectado con todos los demás. Ahora, ¿es este grafo fuertemente conexo? Recordemos que en el ejemplo anterior habíamos determinado que el nodo cinco no era accesible desde el nodo dos. Esto implica que no hay una ruta dirigida de dos a cinco, lo que quiere decir que este grafo es conexo, pero no fuertemente conexo. Miremos ahora este nuevo grafo que se obtiene al invertir el arco 4,7 del grafo anterior. Claramente este grafo es conexo, pero ¿es también fuertemente conexo? Tomémonos un minuto para para tratar de encontrar un par de nodos no accesibles. [AUDIO_EN_BLANCO] La verdad es que en este grafo todo par de nodos es accesible. Una forma de verificarlo es notando que existen dos ciclos dirigidos, conectados por un nodo. Tomemos ahora cualquier par de nodos, por ejemplo, 4 y 1. Desde el nodo 4 podemos acceder al nodo tres, siguiendo el ciclo azul y del tres podemos acceder al uno, siguiendo el ciclo rojo. De hecho, si tomamos un nodo de cada ciclo, siempre podríamos encontrar una ruta dirigida que los conecte pasando por el nodo tres. Por otra parte, si tomamos dos nodos que pertenecen al mismo ciclo, podemos formar una ruta dirigida que los conecte, simplemente siguiendo el ciclo. Con esto, podemos confirmar que todo par de nodos es accesible en esta red y que es, por lo tanto, fuertemente conexo. Resumiendo lo que hoy vimos, podemos decir que dos nodos A y B se encuentran conectados si existe una ruta entre ellos. Si además existe una ruta dirigida entre A y B, podemos decir que B es accesible desde A. Además, diremos que un grafo es conexo si todos todos los pares de nodos están conectados. Si además cualquier nodo es accesible desde todos los demás nodos, diremos que el grafo es fuertemente conexo. Eso es todo por ahora. Hasta la próxima. [AUDIO_EN_BLANCO] [AUDIO_EN_BLANCO]
