Download Árboles - Facultad de Ciencias-UCV

UNIVERSIDAD CENTRAL DE VENEZUELA
FACULTAD DE CIENCIAS
ESCUELA DE COMPUTACION
Matemáticas Discretas III (Cód. 6108)
Práctica # 4
Árboles
1. Sea G = <V,A> un grafo no dirigido sin lazos. Demostrar que las siguientes
proposiciones son equivalentes:
(a) G es un árbol.
(b) G es conectado, pero si se elimina cualquiera de sus arcos, G quedará
desconectado en dos subgrafos que son árboles.
(c) G no contiene ciclos y |V | = |A| + 1.
(d) G es conectado y |V | = |A| + 1.
(e) G no contiene ciclos y si a, b ∈ V con {a, b} ∈ A, entonces el grafo que
se obtiene al añadir el arco {a, b} a G tiene precisamente un ciclo.
2. Demostrar que para cualquier árbol T = <V,A>, si |V | ≥ 2, entonces T tiene al
menos dos vértices colgantes (vértices de grado 1).
3. Sean T1 = <V1, A1> y T2 = <V2, A2> dos árboles tales que |A1| = 17 y |V2| =
2|V1|. Determine |V1|, |V2| y |A2|.
4. Sea B = <V, A> un bosque de siete árboles con |A| = 40. ¿Cuánto vale |V|?
5. Si un árbol tiene cuatro vértices de grado 2, uno de grado 3, dos de grado 4 y
uno de grado 5, ¿cuántos vértices colgantes tiene el árbol?
6. Si un árbol T = <V,A> tiene v2 vértices de grado 2, v3 vértices de grado 3, ... y
vn vértices de grado n, ¿cuánto valen |V | y |A|?
7. Si G = <V,A> es un grafo no dirigido sin lazos, demuestre que G es un árbol si
existe un único camino entre dos vértices cualesquiera de G.
8. Sea T = <V,A> un árbol con raíz ordenado mediante un sistema universal de
direcciones. Suponga que el vértice v ∈ V tiene dirección 2.1.3.6.
(a) ¿Cuál es el número mínimo de hermanos que v debe tener?
(b) ¿Cuántos ascendientes tiene v?
(c) ¿Qué otras direcciones deben haber en el sistema?
9. Sea T = <V,A> un árbol con raíz y sea m un entero positivo. T es un árbol mario si (el grado de salida) d+(v) ≤ m para todo v ∈ V. Si d+(v) ∈ {0,m} para
todo v ∈ V , T es un árbol m-ario completo. Sea T = <V,A> un árbol m-ario
completo con h hojas y i vértices internos. Demuestre que:
(a) |V | = mi + 1
(b) h = (m − 1)i + 1
(c) i = (h − 1)/(m − 1) = (|V | − 1)/m
10. ¿Cuántos vértices internos tiene un árbol 5-ario completo con 817 hojas?
11. Si T = <V,A> es un árbol con raíz y a es el número de nivel (longitud del
camino simple desde la raíz) máximo de una hoja de T, entonces T tiene altura
a. Sea T = <V,A> un árbol m-ario completo (m ≥ 1) de altura a con h hojas.
Demostrar que h ≤ ma.
12. Sea T = <V,A> un árbol binario. Si |V | = n, ¿cuál es la altura máxima posible
de T? Si T es un árbol binario completo, ¿cuál es la altura máxima posible de T?
13. Demostrar que un grafo no dirigido G es conectado si y sólo si G tiene un árbol
recubridor.
14. Muestre una representación de árbol orientado con raíz para la expresión
aritmética
(a + b + c)(cd + f) / (a + c)en
15. Explique el uso de árboles orientados con raíz como árboles de decisión.
Muestre un ejemplo que ilustre su aplicación.
16. ¿Cuántos bosques recubridores distintos (aunque isomorfos) tiene el grafo Cn (el
ciclo con n vértices, n ≥ 3)?
17. Halle los árboles de recubrimiento en profundidad y en amplitud para K5. Fije
Ud. Un orden para los vértices.
18. Sea G = <V,A> un grafo no dirigido conexo sin lazos donde V = {a, b, c, d, e,
f, g, h} y A = {{a, b}, {a, c}, {a, d}, {a, e}, {b, g}, {c, g}, {d, h}, {e, f},
{e, h}}. Encuentre los árboles recubridores en profundidad y amplitud si el
orden de los vértices es
(a) a; b; c; d; e; f; g; h
(b) a; b; c; d; h; g; f; e
19. Considere un grafo con pesos G = <V,A> en el cual cada arco a ∈ A tiene
asociado un peso numérico (costo) p(a). Se desea hallar un árbol recubridor T
tal que la suma de los pesos de los arcos en T sea minimal respecto a cualquier
árbol recubridor de G.
(a) Investigue el algoritmo de Kruskal para hallar los árboles recubridores
minimales de un grafo con pesos no dirigido, conexo y sin lazos. Muestre un
ejemplo de su aplicación.
(b) Investigue el algoritmo de Prim para hallar los árboles recubridores
minimales de un grafo con pesos no dirigido, conexo y sin lazos. Muestre un
ejemplo de su aplicación.
GDMDIII. Octubre 2012.