Actividad de aprendizaje Taller de Grafos y Árboles

ACTIVIDAD 4 TALLER DE GRAFOS Y ÁRBOLES

David Steven Babativa Diaz

                                                  Universidad Manuela Beltrán      

                                              Faculta de ingeniería de software      

                                                              Bogotá, 2023      

Tabla de contenido 

Recorridos en un grafo        3

Problema a)        3

Problema b)        5

Árbol de codificación de Huffman        7

Problema a)        7

Problema b)        8

Árbol de expansión        9

Problema a)        9

Problema b)        10

Bibliografía        10

EJERCICIOS PROPUESTOS 

Recorridos en un grafo    

[pic 1] 

Problema a)  

[pic 2] 

Solución problema a)    

Primero vamos a identificar la cantidad, tanto de vértices como aristas que vamos a usar.  

V=(A, H, E, I, C, G, B, J, F, D)  

Como podemos ver estamos usando 10 vértices ahora calcularemos la cantidad de aristas del grafo.  

Para eso utilizamos el conjunto de pares no ordenados por medio de los vértices. V=V(G)  E=((A,H), (A,D), (A,B) ,(A,I), (A,E),  

(H,A),(H,E),(H,I),(H,C),(H,B),(E,A),(E,H),(E,D),(E,I),(I,A),(I,E),(I,H),(I,C),(C,I),(C,H),  

(C,B)(C,B),(C,F),(G,C),(G,B),(B,G),(B,C),(B,A),(B,H),(B,D),  

(B,F),(B,J),(J,B),(J,D),(J,F),(F,J),(F,B),(F,C),(F,D),(D,A),(D,E),(D,B),(D,J),(D,F)).  

Ahora contamos las veces que se repiten los vértices y esas serán la cantidad de cada uno  

Ahora sumamos cada vértice y nos da 88.  

Ahora multiplicamos las aristas del grafo que son 44 por el doble en este caso x2.  

44 * 2 = 88  

Vemos que nos da la misma cantidad vértices.  

Como ya sabemos la cantidad de vértices y aristas vamos a ver que tipo de grafo es si es euleriano o hamiltoniano.  

[pic 3] 

Como podemos ver no sería euleriano ya que para serlo todos sus vértices deben tener grado par. por mínimo debe tener 2 impares y vemos que tiene más de 3 impares todos los diferentes colores que vemos son los vértices impares los que no tienen son los pares.  

[pic 4] 

Por lo tanto este es un grafo Hamiltoniano por que como podemos ver podemos recorrer todos los vértices una vez comenzamos desde uno inicial hasta uno final como podemos ver comenzamos desde el A y podemos continuar sin necesidad de repetir.  

Problema b)    

[pic 5]   

Solución problema b)    

Primero vamos a identificar la cantidad, tanto de vértices como aristas que vamos a usar.  

V=(G, H, F, B, E, C, D, A)  

Como podemos ver estamos usando 8 vértices ahora calcularemos la cantidad de aristas del grafo.  

Para eso utilizamos el conjunto de pares no ordenados por medio de los vértices.  

V=V(G)  

E=(F,G),(F,H)(F,B)(F,A)(G,F),(G,A),(G,C)(G,H),(H,G)(H,B)(H,F)(H,E)(B,H)(B,

F)(B,E),(B,D)(E,H)(E,B)(E,C)(E,D)(C,G)(C,E)(C,D)(C,A)(D,E)(D,B)(D,C)(D,A) (A,C),(A,G) (A,D)(A,F))  

Ahora contamos las veces que se repiten los vértices y esas serán la cantidad de cada uno  

Ahora sumamos cada vértice y nos da 64  

Ahora multiplicamos las aristas del grafo que son 32 por el doble en este caso x2.  

32 * 2 = 64  

Vemos que nos da la misma cantidad vértices.  

Como ya sabemos la cantidad de vértices y aristas vamos a ver qué tipo de grafo es si es euleriano o hamiltoniano.  

[pic 6] 

Por lo tanto es te grafo es Euleriano ya que podemos recorrer sin ningún problema el grafo de manera correcta y completa en este caso este grafo es conexo ya que tiene todos sus vértices pares que son 4 cada uno de ellos y no hay ningún vértice impar.  

...