Ficha Aprendizaje 6(MATEMATICA DISCRETA)

1.    ¿Qué significa que un vértice de un grafo alcance a otro vértice del grafo ? (1 pto)

Significa que hay un camino que llegue desde el vértice inicial “vi” al vértice final “vf”.

Por tanto, en la tabla de accesibilidad, justo en la posición donde coinciden la fila de “vi” y la columna de “vf” deberá 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? (1,5 ptos).

5 matrices, simplemente porque si tiene 5 vertices, al ser una matriz NxN, tendrá 5 filas y 5 columnas, y este algoritmo empieza por la primera y por cada iteración suma una fila y una matriz.

En resumen: NºVertices=NºMatrices

3.    Escribe una condición necesaria para que un grafo sea conexo. (1,5 ptos)

Que desde cualquier vértice del gráfo 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

(3 ptos).

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? (1 pto).

Cuando exactamente el grado de los vertices impares es 2