Post on 12-Aug-2015
Profesora Pilar Pardo H
Fecha: 14-06-2014
Damary Paquíen Sandoval
Docente:
Sede Concepción Talcahuano
TAREA DE GRAFOS
Asignatura
Analisis de Algoritmos
Integrantes:
TAREA:
EJERCICIO 1: A partir de las siguientes Matrices, construir sus respectivos Grafos si es posible.
MATRIZ 1 MATRIZ 2 MATRIZ 3
A B C D A B C A B C D E F G H
A 0 1 1 1 A 0 1 0 A 0 1 1 0 0 0 0 0
B 1 0 1 1 B 1 0 1 B 1 0 0 1 0 0 0 0
C 1 1 0 1 C 0 0 0 C 1 0 0 1 0 0 0 0
D 1 1 1 0 D 0 1 1 0 0 0 0 0
E 0 0 0 0 0 1 0 0
F 0 0 0 0 1 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0
DESARROLLO:
MATRIZ 1 MATRIZ 2 MATRIZ 3
No es posible de realizar
porque es dirigido y no
dirigido.
EJERCICIO 2: Construya la Matriz de adyacencia del siguiente grafo no dirigido:
DESARROLLO:
MATRIZ
V= {1,3,5,8} E= {(1,3),(1,5),(1,8) 1 3 5 8
(3,1),(3,5),(3,8) 1 0 1 1 1
(5,1),(5,3),(5,8) 3 1 0 1 1
(8,1),(8,3),(8,5)} 5 1 1 0 1
8 1 1 1 0
A B
D C
A B
D C
E H
G F
1 5
8 3
EJERCICIO 3: Construya la Matriz de adyacencia del siguiente grafo dirigido:
DESARROLLO:
MATRIZ
V= {1,2,3,4} E= {(1,2),(1,3),(1,4) 1 3 5 8
(2,2),(2,3) 1 0 1 1 1
(3,4)} 3 0 1 1 0
5 0 0 0 1
8 0 0 0 0
EJERCICIO 4: Construya la Matriz de adyacencia del siguiente grafo dirigido:
DESARROLLO:
MATRIZ
V= {a,b,c,d} E= {(a,b),(a,c) a b c d
(b,c),(b,d) a 0 8 40 0
(c,d)} b 0 0 15 30
c 0 0 0 15
d 0 0 0 0
a b 8 c 40
b c 15 d 30
c d 15
d
30
15
40 15
1 2
3 4
a b
d c
8
EJERCICIO 5: Construya la Matriz de adyacencia del siguiente grafo dirigido:
DESARROLLO:
MATRIZ
V= {a,b,c,d} E= {(a,b),(a,c) a b c d
(b,a),(b,c),(b,d) a 0 120 40 0
(c,a),(c,b),(c,d) b 120 0 5 10
(d,b),(d,c)} c 40 5 0 15
d 0 10 15 0
a b 120 c 40
b a 120 c 5 d 10
c a 40 b 5 d 15
d b 10 c 15
120
10
15
40 5
a b
d c