Práctica 5 grafos md ua - accesibilidad y conectividad

RUBÉN MARTÍNEZ VILAR
MATEMÁTICAS 1 - MATEMÁTICA DISCRETA
Prácticas con MaGraDa
Práctica 5:

PROBLEMA 3.1:

(i)

| 0 1 0 0 0 0 |
| 0 0 1 0 0 1 |
| 0 0 0 0 0 1 |
A=| 1 0 0 0 0 1 |
| 0 0 1 0 0 0 |
| 0 0 0 0 1 0 |

R(1)={1,2,3,5,6}, R(2)={2,3,5,6}, R(3)={3,5,6}, R(4)={1,2,3,4,5,6}, R(5)={3,5,6}, R(6)={3,5,6}.

Para saber a que vértices alcanza el vértice 1, vemos primero que alcanzaal 2, y si vamos al 2 vemos que este alcanza al 3 y al 6, si vamos al 6 vemos que llega al 5, y vuelve al 3. Por lo que el vértice 1 va a poder llegar a los vértices 1,2,3,5 y 6. Así se puede hacer con cada vértice.
En el caso del 4, vemos que en la cuarta columna de cada vértice es siempre cero, por lo que ya sabemos que no hay ningún vértice que lo alcance, a parte de él mismo, pero como sique hay un 1 en la primera columna de la cuarta fila, y ya hemos obtenido R(1), podemos ver que el vértice 4 llega a todos los demás vértices.

El vértice 3 alcanza a los vértices 3, 5 y 6 y el vértice 4 a todos.

(ii)

En la matriz de accesibilidad usamos el 1 cuando el vértice x alcanza al y. Por lo tanto, mirando R(x), podemos obtener la matriz de adyacencia, por ejemplo, R(1) alcanzaal 1,2,3,5 y 6, por lo que ponemos 1 en esas columnas de la primera fila.

| 1 1 1 0 1 1 |
| 0 1 1 0 1 1 |
| 0 0 1 0 1 1 |
R=| 1 1 1 1 1 1 |
| 0 0 1 0 1 1 |
| 0 0 1 0 1 1 |

(iii)

La matriz de acceso es la inversa de R, ya que, en la de accesibilidad, las columnas nos dicen los vértices y que alcanzan a x.

| 1 0 0 1 0 0 |
| 1 1 0 1 0 0 |
| 1 1 1 1 1 1 |
Q=| 0 0 0 1 0 0 |
| 1 1 11 1 1 |
| 1 1 1 1 1 1 |
(iv)

Ya con la matriz de acceso, es fácil obtener Q(v). Cuando encontremos un 1, es porque ese vértice pertenece al conjunto de vértices que alcanzan al de esa fila, de manera que obtenemos lo siguiente:

Q(1)={1,4}, Q(2)={1,2,4}, Q(3)={1,2,3,4,5,6}, Q(4)={4}, Q(5)={1,2,3,4,5,6}, Q(6)={1,2,3,4,5,6}.

Los únicos vértices que alcanzan al vértice 1 son losvértices 1 y 4. Sin embargo al vértice 3 lo alcanzan todos.

PROBLEMA 3.2:

(i)
1. La primera matriz, R0, es igual a la matriz de adyacencia:

| 0 1 0 0 0 0 0 |
| 0 1 0 0 0 0 0 |
| 0 0 0 1 0 0 0 |
A=R0= | 0 0 0 0 0 0 1 |
| 0 0 0 0 0 0 0 |
| 0 0 1 0 0 0 0 |
| 0 0 1 0 0 0 0 |

2. Para R1 no habrá cambios, ya que solo hay un arco que sale desde el vértice 1, pero ninguno deentrada, por lo que, por ejemplo, teniendo i=3 y j=2 (siendo k=1, evidentemente), no se cumple la condición que dice que para que Rij sea igual a 1, tiene que haber un arco de i hacia k (Rik) y otro de k hacia j (Rkj). En este caso no hay arco de i hacia k, por lo que el resultado sigue siendo 0 para R(3,2). Y así pasa con el resto de casos.
3. Con R2 pasa algo parecido, pero en este caso tenemos unbucle y solo un arco entrante desde el vértice 1.
De momento tenemos que A=R0=R1=R2.
4. En este caso si que encontramos cambios en la matriz. Para R3 encontramos un arco desde i=6 hacia k=3 (siendo i la fila y k la columna), y desde k=3 hacia j=4 (siendo k la fila y j la columna), por lo que R(6,4) sera 1. Lo mismo pasa para R(7,4).

| 0 1 0 0 0 0 0 |
| 0 1 0 0 0 0 0 |
| 0 0 0 1 0 0 0 |R3 = | 0 0 0 0 0 0 1 |
| 0 0 0 0 0 0 0 |
| 0 0 1 1 0 0 0 |
| 0 0 1 1 0 0 0 |

5. Pasamos a R4. Para R(3,7) tenemos arco de i=3 hacia k=4 y de k=4 hacia j=7. Para R(6,7) y R(7,7) también los cambiamos por 1.

| 0 1 0 0 0 0 0 |
| 0 1 0 0 0 0 0 |
| 0 0 0 1 0 0 1 |
R4 = | 0 0 0 0 0 0 1 |
| 0 0 0 0 0 0 0 |
| 0 0 1 1 0 0 1 |
| 0 0 1 1 0 0 1 |

6. El vértice 5 no estaconectado con ninguno, por lo que no hay cambios en la matriz R5. Lo mismo para la matriz R6, ya que la columna 6 esta toda a ceros.
7. En R7 se producen tres cambios, en R(3,3), R(4,3) y R(4,4).
| 0 1 0 0 0 0 0 |
| 0 1 0 0 0 0 0 |
| 0 0 1 1 0 0 1 |
R7 = | 0 0 1 1 0 0 1 |
| 0 0 0 0 0 0 0 |
| 0 0 1 1 0 0 1 |
| 0 0 1 1 0 0 1 |

8. Para terminar, ponemos toda la diagonal a 1...