PROBLEMAS PROPUESTOS UNIDAD 2 AfianzANDO el Conocimiento sobre Árboles y Grafos

Esteban Andrés Díaz Mina

Justifique la respuesta a cada uno de los siguientes problemas: 1. Construye un grafo de precedencia para el siguiente programa.

S1 : x := 0 S2 : x := x + 2 S3 : y := x - 1 S4 : z := x + y S5 : z := z + y S6 : w := z + 2

2. Dados los grafos Kn y Cn : a. Para cuales valores de n, los grafos tienen un circuito de Euler? b. Para cuales valores de n, los grafos tienen un camino de Euler pero no un circuito de

Euler? 3. Un grafo simple es llamado regular si cada vértice de este grafo tiene el mismo grado. Un

grafo es llamado n-regular si cada vértice en el grafo es de grado n. a. Para que valores de n los grafos Kn y Cn son regulares? b. Para que valores de n el grafo Km,n No es regular?

4. ¿Cuántos vértices y cuántas aristas tienen los siguientes Grafos?

a. Kn b. Wn

5. Determine si los siguientes grafos son isomorfos. Justifique su respuesta.

Descripción de una Situación: Como es de conocimiento general, en los pueblos, se toma como referencia de ubicación los sitios públicos. En el pueblo X donde vive el señor Jóse_Santos, se tienen los siguientes sitios públicos: Alcaldía, Guardería, Parque, Supermercado, Estadio, Prendería, Panadería y un enlace que representa el hecho de que se puede desplazar de un sitio a otro. {Alcaldia, Parque} {Alcaldia, Guarderia} Guarderia, Estadio} {Parque, Supermercado} {Parque, Estadio} {Prenderia, Panaderia} {Supermercado, Estadio} {Estadio, Prenderia} {Panaderia, Supermercado} {Panaderia, Parque} {Panaderia, Guarderia} {Guarderia, Supermercado} Dibuje el grafo G, que represente la ubicación de los sitios del Pueblo.

6. ¿Es el grafo G bipartita?. ¿El grafo G tiene un circuito de Euler. ¿El Grafo es Plano? ¿Cuál

es el número cromático de G? Justifique su respuesta

7. Obtenga un árbol generador del siguiente grafo:

a. Usando búsqueda en profundidad a partir del vértice f.

b. Usando búsqueda en anchura a partir del vértice k.

Nota. Si un vértice tiene varios vértices adyacentes, escoja el que aparece primero en el orden lexicográfico.

8. Construya un árbol ordenado etiquetado cuyo recorrido preorden es a, b, e, f, g, c, h, i, j, d, k, l, m; donde a, b, c tienen 3 hijos; d y k tienen un hijo, y todos los otros vértices son hojas.

9. Supongamos que m es un entero con m≥2. Un código de Huffman m-ario para un

conjunto de N símbolos se puede construir de manera análoga a la construcción del código de Huffman binario. En el paso inicial, se combinan ((N - 1) mod (m - 1)) + 1 árboles de peso mínimo que constan de un solo vértice para formar un árbol con raíz que tiene a estos vértices como hojas. En cada uno de los pasos siguientes, los m árboles de menor peso se combinan para formar un árbol m-ario. Use codificación 4-aria de Huffman para la frase TECNOLOGO

EN SISTEMAS DE INFORMACION GEOGRAFICO y determine el porcentaje de bits ahorrados. Nota: No tenga en cuenta los espacios.

Éxitos!