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.