[manooooh]

Hola!!

En el siguiente ejercicio tengo dudas:

Hallar la cantidad de hojas de un árbol con raíz que tiene \( 15 \) vértices internos de grado \( 2 \), \( 8 \) de grado \( 3 \) y \( 9 \) de grado \( 4 \) (el resto son hojas).

Cuando se refiere a "Un árbol con raíz", ¿se debe tener en cuenta (al plantear la sumatoria de los vértices) los grados de la raíz? ¿O el dato ya dado por consigna incluye (está tomando en cuenta) a la raíz?

Estaría interpretando que la consigna se refiere a "grados totales" del digrafo en cuestión.

Sé que en un digrafo \( G=(V,A,\varphi) \) se cumple \( \sum g^+(v_i)=|A| \), \( \sum g^-(v_i)=|A| \), \( \sum g(v_i)=2|A| \), la suma de los grados netos (diferencia entre el grado positivo y el negativo) es \( \sum g_N(v_i)=0 \) y que si el digrafo fuese un árbol la raíz \( r \) cumple \( g^+(r)=0 \).

Gracias!!
Saludos

[Luis Fuentes]

Hola

Hallar la cantidad de hojas de un árbol con raíz que tiene \( 15 \) vértices internos de grado \( 2 \), \( 8 \) de grado \( 3 \) y \( 9 \) de grado \( 4 \) (el resto son hojas).

Cuando se refiere a "Un árbol con raíz", ¿se debe tener en cuenta (al plantear la sumatoria de los vértices) los grados de la raíz? ¿O el dato ya dado por consigna incluye (está tomando en cuenta) a la raíz?

La raíz se considera vértice interno.

Entonces tienes en total \( n=15+8+9+x=32+x \) vértices, donde \( x \) es el número de hojas y por tanto \( n-1=31+x \) aristas. La suma de grados es el doble de número de aristas:

\( 2\cdot 15+8\cdot 3+9\cdot 4+1\cdot x=2(31+x) \)

Y de ahí puedes despejar \( x \).

Saludos.

[manooooh]

Hola, gracias Luis

La raíz se considera vértice interno.

Mi profesor no lo dio así. Tenemos las siguientes definiciones:

Árbol con raíz: Es un árbol dirigido en el cual el grado entrante (positivo) de cada vértice es igual a \( 1 \), salvo un
único vértice con grado positivo igual a cero, llamado raíz.

- Un vértice \( v \) de un árbol se dice que es hoja cuando \( g(v) = 1 \).

- Los vértices internos son todos aquellos que no son la raíz ni las hojas.

- Se llama rama a todo camino que va desde la raíz a alguna hoja.


¿Cambia en algo tu resolución? ¿Cómo consideramos el grado (positivo y negativo) del vértice "raíz"?

Saludos

[Luis Fuentes]

Hola

¿Cambia en algo tu resolución? ¿Cómo consideramos el grado (positivo y negativo) del vértice "raíz"?

Pero en ese caso si la raíz no es vértices interno, no tenemos información sobre cuantos hijos tiene. ¿Qué impediría añadirle a la raíz \( 1314 \) hojas sin que variasen para nada los datos del enunciado?.

Saludos.

[manooooh]

Hola

Me acaba de decir esto el profesor:

El enunciado está mal redactado, los grados que se indican ya incluyen a la raíz, no debería decir "internos".

Gracias Luis.

Saludos