En este video, vamos a familiarizarnos con una de las herramientas básicas con las que cuenta un ingeniero para modelar problemas de transporte en una ciudad, los grafos. Comenzaremos por definir lo qué es un grafo y establecer la relación que existe entre esta herramienta y las redes de transporte que queremos modelar. Luego, haremos algunas definiciones necesarias para trabajar con grafos, distinguiendo algunos tipos de estos e introduciendo los conceptos de incidencia y adyacencia. Comencemos por definir lo que es un grafo. Un grafo o, informalmente, una red se puede definir como una herramienta matemática formada por un conjunto de nodos o vértices conectados por arcos o aristas. Miremos cómo se vería, entonces, un grafo. Tomemos, en primer lugar, un conjunto "N" de nodos, estos nodos se conectan entre sí mediante arcos formando un conjunto "A" como se ilustra en la figura. Estos arcos pueden tener o no tener dirección, en caso de poseerla, podemos representarlos usando flechas como en esta figura. Diremos que "G" de "N, A" corresponde al grafo formado por los nodos del conjunto "N" y los arcos del conjunto "A". Diremos que un arco que posee dirección es un arco dirigido, un arco dirigido se representa como una flecha conectando un nodo cola con un nodo cabeza. Como decíamos en la introducción, los grafos son útiles para modelar redes de transporte. ¿Qué relación existe, entonces, entre un grafo y una red de transporte? Una red de transporte puede ser entendida como un grafo donde los nodos corresponden a las intersecciones y los arcos a las calles que conectan estas intersecciones. Veamos un ejemplo, miremos una sección de la red vial de la ciudad de Santiago. Para modelar esta red usando un grafo definimos, en primer lugar, un conjunto de nodos de forma que coincidan con las intersecciones. A continuación, construimos el conjunto de arcos conectando estos nodos. Como las calles poseen el sentido de marcha, vamos a utilizar arcos dirigidos. Por ejemplo, este corredor de acá que posee sentido hacia la derecha en el dibujo se puede modelar con estos arcos. Por su parte, un corredor bidireccional como el que se indica se puede modelar usando pares de arcos dirigidos, así. Siguiendo con este procedimiento, el conjunto completo de arcos para esta red vial quedaría así. Esta representación de la ciudad nos permite modelar diferentes situaciones. Por ejemplo, una ruta entre dos nodos puede ser modelada como una secuencia de arcos, como se ilustra. Un grafo cuyos arcos poseen dirección como el que construimos recién es conocido como "grafo dirigido". Como las calles de una red vial pueden poseer sentido de marcha, en este curso trabajaremos, por lo general, con este tipo de grafos. En muchas situaciones necesitamos agregar más información a nuestro grafo. Por ejemplo, en el grafo de la red vial antes descrita, para predecir las rutas que utilizan los usuarios vamos a necesitar considerar los tiempos de viaje a través de los arcos. Definimos, entonces, un grafo ponderado como un grafo cuyos arcos poseen asociado un valor escalar como, por ejemplo, un costo "c i j" para cada arco "i, j". Por ejemplo, este es un grafo ponderado con un costo de tres unidades para ir de "uno" a "dos", de cuatro unidades para ir de "uno" a "tres", y de una unidad para ir del nodo "dos" al nodo "tres". Cabe notar que estos costos pueden representar tiempos de viajes, distancias, costos monetarios o cualquier combinación de estos u otros elementos según lo que se pretenda modelar. Para poder trabajar con grafos es necesario hacer algunas definiciones adicionales que nos permitirán modelar el movimiento de los usuarios sobre la red vial. La primera definición tiene que ver con la incidencia de un arco en un nodo. Se dice que un arco incide en un nodo dado si este nodo corresponde a la cola o la cabeza del arco. En palabras sencillas, un arco incide en un nodo si este arco toca al nodo con uno de sus extremos. Por su parte, se dice que dos arcos son adyacentes si comparten alguno de sus extremos, sin importar si este es cola o cabeza. Diremos, además, que dos no son adyacentes si existe un arco que posea a uno de ellos como cola y al otro como cabeza. En palabras sencillas, dos nodos son adyacentes si se encuentran conectados en forma directa por un arco. Veamos una ilustración para entender mejor estas relaciones. Por ejemplo, sobre qué nodos incide el arco "uno, dos". Como mencioné antes, un arco incide sobre sus nodos cola y cabeza, por lo tanto, el arco "uno, dos" incide sobre los nodos "uno" y "dos". Veamos, ahora, el concepto de adyacencia entre nodos. Por ejemplo, ¿qué nodos son adyacentes al nodo "dos"? Los nodos adyacentes a "dos" son los nodos que se podrían alcanzar desde "dos" a través de un arco sin importar el sentido de éste. Es decir, los nodos adyacentes de "dos" son los nodos "uno" y "cuatro". Veamos ahora el concepto de adyacencia en arcos. Por ejemplo, ¿qué arcos son adyacentes al arco "uno, dos"? Los arcos adyacentes de "uno, dos" son los arcos que inciden en el nodo "uno" o en el nodo "dos", es decir, los arcos adyacentes de "uno, dos" son "uno, tres", "uno, cuatro" y "dos, cuatro". Resumamos lo aprendido en la clase de hoy. Un grafo se define como un conjunto de nodos y un conjunto de arcos cuyos extremos conectan los nodos de este conjunto. Los grafos son una herramienta muy importante para la modelación de redes de transporte. Usualmente, los nodos pueden representar intersecciones y los arcos vías que conectan a estas intersecciones. Existen diferentes tipos de grafo, un grafo puede ser dirigido o no dirigido, dependiendo de si sus arcos poseen, o no, dirección. Además, los grafos pueden poseer información adicional asociada a sus arcos. Se conoce como grafo ponderado a aquel cuyos arcos poseen un costo asociado. Las relaciones entre nodos y arcos dentro de un grafo dan lugar a los conceptos de adyacencia e incidencia que guardan relación con la existencia de conexiones directas entre estos elementos. Eso fue todo por hoy, nos vemos en la próxima clase.
