Clase 17 - SIS - Practica de Laboratorio 04
2
GRAFOS Observaciones: 1. En los grafos interesa recorrer las aristas para llegar de un vértice a otro. 2. Se llama camino o ruta entre dos vértices, a y b, a toda sucesión de aristas que conectan a con b, siendo la longitud del camino el número de aristas que lo componen. 3. Las potencias de la matriz de adyacencia de un grafo permiten conocer el número de caminos existentes entre cualquier par de vértices de una determinada longitud. 4. La matriz de adyacencia M de un grafo indica si existe o no una arista entre cada par de vértices. 5. La matriz M 2 indica el número de caminos de longitud 2 entre dos vértices cualesquiera. De la misma forma, la matriz M 3 indica el número de caminos de longitud 3 y así sucesivamente. 6. También se puede establecer si existe o no un camino, no importa la longitud, entre dos vértices cualesquiera con la matriz B = M + M 2 + M 3 + … + M n-1 . (n el número de vértices) EJERCICIOS 1. Sean los grafos siguientes: Escriba la matriz de adyacencia asociada a los grafos A y B de la figura anterior. 2. Hallar cuántos caminos de longitud 2 y 3 conectan cada par de vértices del grafo siguiente: 3. Entre los cuatros pueblos A, B, C y D se establece una línea de autobuses tal como viene representada en el siguiente grafo: a) Escribe su matriz de adyacencia R. b) Da un significado a las matrices R 2 y R 3 .
Transcript of Clase 17 - SIS - Practica de Laboratorio 04
GRAFOS
Observaciones:
1. En los grafos interesa recorrer las aristas para llegar de un vértice a otro.
2. Se llama camino o ruta entre dos vértices, a y b, a toda sucesión de aristas que conectan a con b, siendo la longitud del camino el número de aristas que lo componen.
3. Las potencias de la matriz de adyacencia de un grafo permiten conocer el número de
caminos existentes entre cualquier par de vértices de una determinada longitud.
4. La matriz de adyacencia M de un grafo indica si existe o no una arista entre cada par de vértices.
5. La matriz M2 indica el número de caminos de longitud 2 entre dos vértices cualesquiera.
De la misma forma, la matriz M3 indica el número de caminos de longitud 3 y así sucesivamente.
6. También se puede establecer si existe o no un camino, no importa la longitud, entre dos
vértices cualesquiera con la matriz B = M + M2 + M3 + … + Mn-1 . (n el número de vértices)
EJERCICIOS
1. Sean los grafos siguientes:
Escriba la matriz de adyacencia asociada a los grafos A y B de la figura anterior.
2. Hallar cuántos caminos de longitud 2 y 3 conectan cada par de vértices del grafo siguiente:
3. Entre los cuatros pueblos A, B, C y D se establece una línea 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.
4. A, B, C y D son cuatro plazas de una ciudad. El grafo siguiente indica cómo están 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+ M
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. Además, que b no está conectada con ningún vértice, y c no lo e stá con d, y sin embargo d está conectado con todos los demás.
6. Desarrollar el algoritmo de la multiplicación de dos matrices en MATLAB
7. Adaptar el algoritmo de la pregunta anterior para desarrollar la multiplicación boolena
Sean y matrices booleanas.
