Grafos y Arboles

1. Hallar el siguiente Grafo:

A) Vértices:
V= {A,B,C,D,E,F,G}

B) Aristas:
E={(A,B)(A,C)(B,A)(B,E)(C,A)(C,D)(C,F)(D,C)(D,F)(D,G)(E,B)(E,G)(F,D)(F,G)(G,D)(G,E)(G,F)}C) El costo para ir del nodo A al nodo G es:
* A-B-E-G= 15
* A-C-D-G= 12
* A-C-F-G= 14
* A-C-D-F-G= 17
* A-C-F-D-G= 11

D) El costo para ir del nodo Eal nodo C es:
* E-F-D-C= 15
* E-G-F-C= 17
* E-B-A-C= 12
* E-G-D-F-C= 14
* E-G-F-D-C= 20

E) Representación Matricial.
| A | B | C | D | E | F | G |
A |- | 5 | 2 | - | - | - | - |
B | 5 | - | - | - | 5 | - | - |
C | 2 | - | - | 8 | - | 6 | - |
D | - | - | 8 | - | - | 1 | 2 |
E | - | 5 | - | - | - | - | 5 |
F | - | - | 6| 1 | - | - | 6 |
G | - | - | - | 2 | 5 | 6 | - |

F) El camino menos costoso del nodo A al nodo D es:
* A-C-F-D= 9

G) El camino menos costoso del nodo A al nodo Ges:
* A-C-F-D-G= 11

2. Crea los Arboles con los recorridos que se indican.
a) INORDEN o m c a f x h g

a
f
g
h
x
c
o
m
a
f
g
h
x
c
o
m

b)INORDEN d b h m x l j o g
h
h
x
l
g
o
j
d
b
m
x
l
g
o
j
d
b
m

c) PREORDEN a c o m x f g h
a
g
x
h
f
m
o
c
a
g
x
h
f
m
o
c

d) PREORDEN x bd m h o l j g
j
j
x
l
h
g
o
m
d
b
x
l
h
g
o
m
d
b

e) POSTORDEN m o c f h g x a
a
m
x
g
h
c
o
f
a
m
x
g
h
c
o
f

3. Recorre lossiguientes árboles en Preorden, Inorden y Postorden.
a)

* PREORDEN= {5-3-2-1-4-8-7-5’-10-9-11}
* INORDEN= {1-2-3-4-5-5’-7-8-9-10-11}
* POSTORDEN={1-2-4-3-5’-7-9-11-10-8-5}

b)

* PREORDEN= {40-30-20-10-5-25-35-32-50-45-42-55}
* INORDEN= { 5-10-20-25-30-32-35-40-42-45-50-55}
* POSTORDEN= { 5-10-25-20-32-35-30-42-45-55-50-40}