lunes, 28 de noviembre de 2011

PROBLEMA SOBRE ÁRBOLES

UNLAM
MATEMÁTICA DISCRETA

PROBLEMA DE ÁRBOL

Si un árbol tiene 4 vértices de grado 2, uno de grado 3, dos de grado 4 y otro de grado 5. Cuantos vértices colgantes tiene?
Sabemos que, en un grafo:
y en un árbol:                                                            V= A+1
Entonces:
4 . 2 + 1. 3 + 2 . 4 + 1 . 5 + x . 1= 2 .A,    (1)  donde  x es la cantidad de hojas, es decir vértices de grado 1.
y además:
4 + 1 + 2 +1 + x = A + 1
8 + x = A + 1
7 + x = A
Reemplazamos en (1):
8 + 3 + 8 + 5 + x = 2. ( 7 + x)
24 - 14 = x
10 = x.

Por lo tanto, el árbol tiene 10 hojas.

La Profe.