L E E Y C O M P R E N D E 1 Si entre dos puntos del mapa, la carretera que los une no es recta, sino que tiene 4 curvas pronunciadas, ¿cuántas aristas son necesarias para señalarlas en el grafo? I N T E R P R E TA 2 Clasifica las matrices que aparecen en el texto, según su forma y la posición de sus elementos. R E F L E X I O N A 3 Decimos que un camino es simple cuando no pasa dos veces por el mismo vértice. Si consideramos un grafo con 5 vértices, ¿cuál es el número máximo de aristas que tiene un camino simple? A P L I C A 4 Dadas las matrices siguientes, dibuja un grafo que las tenga como matrices de adyacencia. a) 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 f p b) 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 f p 5 Considera el siguiente grafo y calcula el número de caminos cuya longitud sea de tres aristas que hay entre el vértice 2 y el vértice 4. 1 2 3 4 Cuando programamos un GPS para que encuentre una ruta en un mapa con diferentes puntos de destino y los posibles caminos para l legar a cada uno, el navegador lo interpreta como un grafo donde los vértices representan los lugares, y las ari stas, los caminos que los unen . Est a situación se pu ede de scr i bir con una matr i z de adyacencia de orden n, donde n es el número de vértices que tiene el grafo y cada elemento aij es el número de ari stas que van del vértice i al vértice j. La matriz de adyacencia correspondiente al grafo del mapa sería : M 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 =f p El elemento aij de la matriz elevada al cuadrado expresa el número de caminos de 2 aristas que existen entre el vértice i y el vértice j. M 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 2 1 1 1 1 3 1 0 1 1 2 1 1 0 1 1 2 = = f f f p p p Por e j emp l o , hay un cami n o d e do s a r i st a s d e s d e e l v é r t i c e a a l v é r t i c e d y t re s c am i n o s d e d o s a r i st a s desde el vér tice b al vér tice b. M 3 expre sar í a lo s camino s de tre s ar i st as , M 4 lo s de 4 aristas, y así sucesivamente. De esta manera, el navegador calcula todos los caminos posibles y, sumando las longitudes de aristas, obtiene el camino más corto. De igual modo determina el camino más rápido, sumando los tiempos de cada arista . M AT E M ÁT I C A S E N E L M U N D O R E A L 238776_02_p62_para_que_sir ven? b c d a 1 Para calcular la ruta óptima entre dos lugares 34
RkJQdWJsaXNoZXIy