documento

EJERCICIOS GRAFOS

EJERCICIO 1


 
Camino
Costo
Longitud
Caminos no simples
V1,V6,V5,V4,V2,V5,V4,V3
41
7
 
V4,V2,V1,V5,V4,V3
22
5
Caminos simples
V6,V1,V5,V4,V2,V3
18
5
 V2,V1,V5,V4,V3
18
4
 
V5,V4,V2,V1,V6
18
4
Ciclos simples
V1,V5,V4,V2,V1
15
4
 
V2,V5,V4,V2
17
3
Ciclos no simples
V2,V1,V6,V1,V5,V4,V2
24
6
 
V5,V4,V2,V1,V6,V1,V5
24
6
Camino máscorto de V1 a V3
V1,V5,V4,V3
15
3
Camino más barato de V1 a V3
V1,V5,V4,V2,V3
14
4
Camino simple más largo
V6,V1,V5,V4,V2,V3
18
5

Ejercicio 2











Ejercicio 3Ejercicio 4
























Ejercicio 5
Movimientos posibles sobre el barco, con un máximo de dos personas

Ca
Mi
0
1
0
2
1
0
1
1
2
0Estados posibles, donde no hay más caníbales que misioneros en ninguna orilla del rio.

Izquierda
Derecha
Posible
Ca
Mi
Ca
Mi
 
3
3
0
0
 
3
2
0
1
NO
3
1
0
2
NO
3
0
0
3
 2
3
1
0
 
2
2
1
1
 
2
1
1
2
NO
2
0
1
3
 
1
3
2
0
 
1
2
2
1
NO
1
1
2
2
 
1
0
2
3
 
0
3
3
0
 
0
2
3
1
NO
0
1
3
2
NO
0
0
3
3
 

Esto nos da untotal de 10 estado posibles, si a esto le sumamos que en cada nodo debemos especificar la posición donde está el barco (IZQUIERDA o DERECHA). Esto nos da un total de 20 nodos.







Este esel grafo












Solución:
[3,3 I ; 1,3 D ; 2,3 I ; 0,3 D ; 1,3 I ; 1,1 D , 2,2 I ; 2,0 D ; 3,0 I ; 1,0 D ; 1,1 I ; 0,0 D]








Ejercicio 6




Matriz de adyacenciaGrafo A
N
1
2
3
4
5
1
0
1
0
1
0
2
1
0
1
0
1
3
0
1
0
0
0
4
1
0
0
0
1
5
0
1
0
1
0


Matriz de adyacencia Grafo B
N
1
2
3
4
5
1
0
1
0
0
0
2
1
0
10
0
3
0
1
0
0
0
4
0
0
0
0
1
5
0
0
0
1
0







C D








Ejercicio 7




»1) A y B son Isomorfos
»2) A y C son Isomorfos
»3) B y C son isomorfos...