Grafo

TALLER

1. Un cartero tiene que repartir sus cartas en la red de calles representada por el grafo de la figura. Para realizar el reparto, el cartero debe empezar yterminar en oficina de correos que se encuentra en el vértice “i”. Demuestre que el cartero puede efectuar el reparto sin recorrer dos veces la misma calle.

Solución:
Construyendo para ello un circuitoeuleriano. Comenzamos con el circuito y borramos sus aristas del grafo, junto con el vértice i que queda aislado.

A continuación, construimos un nuevo circuito en el grafo que queda, por ejemplo ,lo insertamos en el circuito anterior en el lugar adecuado (), obtenido.
.
Borramos las aristas y vértices aislados.

Proseguimos con el algoritmo, construimos el circuito y lo insertamos en ellugar adecuado () obteniendo.

Finalmente nos queda el circuito que insertado en el lugar adecuado, da lugar al siguiente circuito euleriano del grafo inicial:


2. Es posible disponer todas lasfichas de un dominó de manera que estén todas encajadas? Indicación: utilizar un grafo con 7 vértices y verificar que es euleriano y conexo.
Solución:

3. En cada caso de un ejemplo del enunciadoque se pide y justifique.
un grafo fuertemente conexo no de Euler
Un dígrafo Completo de Euler
Un Torne de Euler con 5 vértices.
Solución:

4. Demuestre que el Dígrafo de la figura en un dígrafoHamiltonano aplicando los respectivos Teoremas y encontrando su circuito.

Solución:

5. El grafo para los pueblos de Casa Ibáñez (CI), Alborea (Al), Casas de Ves (CV), Zulema (Z) y Alcalá deJúcar (AJ) es el siguiente:
a) Halla la matriz de distancias y la matriz del grafo, A.
b) Halla e interpreta ,, y .
c) Halla e interpreta los resultados.


Solución:

6. Usar el algoritmo deDijkstra para determinar d(u0,v) para cada v de G en el grafo ponderado G de la figura y determinar un camino mínimo u0-v3.


Solución:

7. Si G es Euleriano, encuentre el ciclo correcto de Euler...