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