1 L L E G E I X I C O M P R È N 1 Si entre dos punts del mapa, la carretera que els uneix no és recta, sinó que té 4 revolts pronunciats, quantes arestes són necessàries per assenyalar-les al graf? I N T E R P R E TA 2 Classifica les matrius que apareixen al text, segons la forma i la posició dels seus elements. R E F L E X I O N A 3 Diem que un camí és simple quan no passa dues vegades pel mateix vèrtex. Si considerem un graf amb 5 vèrtexs, quin és el nombre màxim d’arestes que té un camí simple? A P L I C A 4 Donades les matrius següents, dibuixa un graf que les tingui com a matrius d’adjacència. 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 graf següent i calcula el nombre de camins la longitud dels quals sigui de tres arestes que hi ha entre el vèrtex 2 i el vèrtex 4. 1 2 3 4 Quan programem un GPS perquè ens indiqui una ruta en un mapa amb diferents punts de destinació i el s possibles camins per arribar -hi , el navegador ho interpreta amb un graf en què el s vèrtexs representen el s l locs i les arestes, el s camins que el s uneixen . A qu e st a s i tu a c i ó e s p o t d e s c r i u re amb u n a ma t r i u d’adjacència d’ordre n, en què n és el nombre de vèr - t e x s q u e t é e l g ra f i c a d a e l e m e n t ai j é s e l n omb re d’arestes que van des del vèrtex i al vèrtex j. La matriu d’adjacència corresponent al graf del mapa seria : M 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 =f p L’element aij de la matriu elevada al quadrat expressa el nombre de camins de 2 are st e s qu e exi st ei xen entre el vèrtex i i el vèrtex 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 Pe r e xemp l e , h i h a un c amí d e du e s a re st e s d e s d e l vèr t ex a al vèr t ex d i tres camins de dues arest es des del vèr t ex b al vèr t ex b. M 3 expre ssar i a el s camins d e tre s are st e s , M 4 el s d e 4 arestes, i així successivament. D’ aqu e st a man era , e l nav egador cal cul a to t s e l s camins possibl es i , sumant l es longitud s de l es arest es, obté el camí més curt. De la mateixa manera , determina el camí més ràpid sumant els temps de cada aresta . M AT E M ÀT I Q U E S E N E L M Ó N R E A L 238776_02_p62_para_que_sir ven? b c d a Calcular una ruta òptima entre dos llocs diferents 34
RkJQdWJsaXNoZXIy