FICHA DE APRENDIZAJE, TEMA 6

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

Sea G=(V,A) un grafo dirigido.

Sean x_i,x_j ∈V, diremos que x_{j es alcanzable desde} x_{i o que xi alzanza a xj, si existe un camino dirigido de x}i <sub>a xj.

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? Tendremos 6 matrices, R0, R1, R2, R3, R4, R5.

3. Escribe una condición necesaria para que un grafo sea conexo.
Un grafo es conexo si todo par de vértices está conectado. Si existe un camino entre cualquier par de vértices.

4. Representa grafica y matemáticamente un grafo dirigido no simple que tenga un tour y un camino euleriano.

Grafo que tiene un tour Euleriano.

Representación gráfica:</sub>

Expresión matemática:

G=(V,A)
V={1,2,3,4,5}
A={e1(1,2), e2(2,5), e3(5,3), e4(3,2), e5(2,3), e6(3,4), e7(4,5), e8(5,1)}
T:1,2,5,3,2,3,4,5,1

Grafo con un camino Euleriano.

Expresión gráfica:

Expresión matemática:

G=(V,A)
V={1,2,3,4,5}
A={e1(1,2), e2(2,5), e3(5,3), e4(3,2), e5(2,3), e6(3,4), e7(4,5)}
T:1,2,5,3,2,3,4,5

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?

Es condición necesaria que el grafo tenga dos vértices de grado impar para tenr un camino euleriano, pero no es condición suficiente.