1. ¿Qué significa que un vértice de un grafo alcance a otro vértice del grafo?
Significa que tiene que haber un camino que llegue desde el vértice inicial “vi” al vértice final “vf”. Lo cual, en la tabla de accesibilidad, justo en la posición donde coincide la fila de “vi” con la columna de “vf” debe ir un 1.
2. ¿Cuántas matrices Ri aparecen en la sucesión del algoritmo de Warshall para calcular la matriz de accesibilidad R de un grafo de 5 vértices?
Cinco matrices, porque al tener cinco vértices y ser una matriz N x N, debe tener cinco filas y cinco columnas, y este algoritmo empieza por la primera y por cada iteración suma una fila y una matriz.
Queda de la siguiente manera: nº vértices = nº matrices
3. Escribe una condición necesaria para que un grafo sea conexo.
Que desde cualquier vértice del grafo se pueda acceder a cualquier otro, es decir, que estén conectados.
4. Representa gráfica y matemáticamente un grafo dirigido no simple que tenga un tour y un camino euleriano.
G = {V, A}
V = {A, B, C, D, E}
A = {(A, B), (B, E), (E, D), (D, D), (D, C), (C, A)}
Posible tour: T = (A, B) (B, E) (E, D) (D, D) (D, C) (C, A)
5. Si G es un grafo no dirigido con unos vértices de grado par y otros de grado impar ¿Cuándo podemos asegurar que G tiene un camino euleriano?
Cuando exactamente hay dos vértices impares