JESUS MENDOZA HUILLCA MATEMATICA DISCRETAS TURNO: MAANA CICLO: IV AULA:25EJERCICIOS1. Sean los grafos siguientes:
Escriba la matriz de adyacencia asociada a los grafos A y B de la figura anterior.
A=
B=2. Hallar cuntos caminos de longitud 2 y 3 conectan cada par de vrtices del grafo siguiente:
A= B^2=
C^3= Matriz B^2 hay 2 caminos de longitud 2 que comunican c con b y son: (c,d,b) y (c,a,b)Matriz C^3 hay 7 caminos de longitud 7 que comunican c con b y son: consideramos 4 (c,a,d,b) , (c,d,c,b) , (c,d,a,b) y (c,d,b,c)
3. Entre los cuatros pueblos A, B, C y D se establece una lnea de autobuses tal como viene representada en el siguiente grafo:a) Escribe su matriz de adyacencia R.b) Da un significado a las matrices R2 y R3.
r=[0 1 0 0;1 0 1 0;0 0 0 1;0 1 1 0]r=
ProductoMatrices(r,r)r^2= En la Matriz r^2 muestra los caminos de longitud 2 que comunican los pueblos unos con otros. 1 camino de longitud 2 A y A=(A,B,A) A y C=(AB,C) D y C=(D,B,C)
No tienen caminos A y B No tienen caminos D y C
ProductoMatrices(r,r)*rr^3= En la Matriz r^3 muestra los caminos de longitud 3 que comunican los pueblos unos con otros. 1 camino de longitud 3 A y D=(A,B,C,D) D y C=(D,C,D,C) 2 caminos de longitud 3 B y C=(B,A,B,C) B y C=(B,C,D,C)
No tienen caminos A y C No tienen caminos C y B
4. A, B, C y D son cuatro plazas de una ciudad. El grafo siguiente indica cmo estn comunicadas entre s. Escriba la matriz de adyacencia M asociada al grafo:
Dar un significado para las matrices M2, M2 + M, M3 y M3+M2+ MM=[0 1 1 1;1 0 0 0;0 0 0 1;1 0 0 0]M=
ProductoMatrices(M,M)M^2=
ProductoMatrices(M,M)+MM^2+M=ProductoMatrices(M,M)*MM^3=
ProductoMatrices(M,M)*M + ProductoMatrices(M,M)+MM^3+M^2+M= M^2 muestra los caminos de longitud 2 que pasan por una plaza intermedia que llevan de una plaza a otra. M^2 + M muestra el nmero de caminos para ir de una plaza a otra directamente o pasando por otra plaza intermedia. M^3 muestra los caminos de longitud 3 que pasando por dos plazas intermedias que llevan de una plaza a otra.
5. Del grafo adjunto obtener M, M2 y M3 y luego calcular B = M + M2 + M3. Deducir de B que no existen caminos entre a y c, ni entre a y d. Adems, que b no est conectada con ningn vrtice, y c no lo est con d, y sin embargo d est conectado con todos los dems.M=[0 1 0 0;0 0 0 0;1 1 0 0;0 0 1 0]M=ProductoMatrices(M,M)M^2=ProductoMatrices(M,M)*MM^3=
B=M + ProductoMatrices(M,M) + ProductoMatrices(M,M)*MB=M+M^2+M^3
No existen caminos entre a y c, ni entre a y d ya que los elementos b(a,c)=0 y b(a,d)=0. B no est conectada con ningn vrtice ya que toda su fila son 0.
6. Desarrollar el algoritmo de la multiplicacin de dos matrices en MATLABMultiplicacin de Matricesfunction res=ProductoMatrices(A,B)[fA,cA]=size(A);[fB,cB]=size(B); if cA==fB for c=1:cB for r=1:fA suma=0; for k=1:cA suma=suma + A(r,k) * B(k,c); end C(r,c)=suma; end end res=C; else error('El Numero de Filas debe ser IGUAL al Numero de Columas'); endend
7. Adaptar el algoritmo de la pregunta anterior para desarrollar la multiplicacin booleana sean y matrices booleanas.Multiplicacin de Matrices Booleanasfunction res=ProductoBoleano(A,B)[fA,cA]=size(A);[fB,cB]=size(B); if cA==fB for c=1:cB for r=1:fA suma=0; for k=1:cA if A(r,k) ==1 | A(r,k) == 0 & B(k,c) == 1 | B(k,c) == 0 suma=suma | A(r,k) & B(k,c); else error('Debe ser una Matriz Booleana'); end end C(r,c)=suma; end end res=C; else error('El Numero de Filas debe ser IGUAL al Numero de Columas'); endend
Recommended