Facilitador: Marco Antonio Cárdenas Soto

Problemario grafos y arboles

1.- Trace un grafo con Cuatro vértices de grados 1, 2, 3, 4.

2.- Trace una Grafica simple de cuatro vértices grados 2, 3, 3, 4.

3.- Determine el grado de cada vértice, así como el grado del grafo siguiente:

V1: 2 V6: 3

V2: 2 V7: 4

V3: 3 V8: 4

V4: 6 V9: 4

V5: 2 V10: 2

15 + 17 = 32

G(v) = 2|A| = 2|15| = 32

4.- Determine si el grafo tiene un ciclo de Euler

Si tiene un ciclo Euler ya que el grado de cada vértice es par.

5.- Trace la matriz de incidencia y adyacencia para el siguiente grafo:

6.-

Decodifique cada cadena de bits mediante los códigos de Huffman de la figura anexa:

a) 011010010

b) 01111100100011

a) [0110 = P] [10 = A] [010 = N] La palabra formada es PAN.

b) [01111 = D] [10 = A] [010 = N] [00 = E] [11 = S] La palabra formada es DANES.

7.- Codifique las siguientes palabras con el grafo anterior

E1 E2 E3 E4 E5

E6 E7

V1

1 0 1 0 0 0 0

V2

0 1 1 1 1 0 1

V3

0 0 0 0 0 1 0

V4

1 1 0 1 0 0 0

V5

0 0 0 0 1 1 0

V1

V2 V3 V4

V5

V1 0 1 0 1 0

V2 1 1 0 1 1

V3 0 0 1 0 0

V4 1 1 0 0 0

V5 0 1 1 0 0

a) NASA 010 10 11 10

b) PASE 0110 10 11 00

c) SALES 11 10 01110 00 11

8.- Determine las relaciones del siguiente árbol:

a) Padre de Eros Afrodita.

b) Ancestros de Hermes Zeus, Cronos, Urano.

c) Hijos de Zeus Apolo, Atenea, Hermes, Heracles.

d) Descendientes de cronosZeus, Poseidón, Hades, Ares, Apolo, Atenea, Hermes, Heracles.

e) Hojas Atlas, Prometeo, Eros, Poseidón, Hades, Ares, Apolo, Atenea, Hermes, Heracles.

f) Vértices internos Afrodita, Cronos y Zeus.

g) Determine el subárbol con raíz en cronos

9.-a Dibuje el grafo de la matriz de incidencia

9.-b Dibuje el grafo de las matrices de adyacencia

e

dc

ba

e

bc

da

V4

V5

V2V1

V3

10.- Los vértices representan ciudades y las aristas los costos de construcción de los caminos indicados, determine el sistema de carreteras más barato.

La suma de los puntos de a - b, b - f, f - d, d - c, c - g y de g - e da un total de 59.