10 Abril, 2020, 16:06 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Homenaje a NUMERARIUS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Problema de árboles  (Leído 1389 veces)
0 Usuarios y 1 Visitante están viendo este tema.
colipan
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 15


Ver Perfil
« : 09 Diciembre, 2009, 08:58 »

Sea T un árbol m-ario completo con 201 nodos y 161 hojas

a: cuál es el valor de m?
b: cuántas aristas T
c: cuál es la altura?

¿necesitaría aplicar m = n-1 siendo m = 201 y n = 161?
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.144


Ver Perfil
« Respuesta #1 : 09 Diciembre, 2009, 09:44 »

Hola

 mmmm..¿exactamente como te han definido árbol completo?.

Saludos.
En línea
colipan
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 15


Ver Perfil
« Respuesta #2 : 09 Diciembre, 2009, 09:51 »

Gracias

el enunciado en concreto es:

a)Sea G un grafo que tiene 6 vertices de grado 2, 2 vertices de grado 3, 3 vertices
de grado 4 y los demas vertices tienen grado 1. Si sabemos que eliminando
de manera conveniente 3 aristas de G, obtenemos un arbol generador de G,
calcula el orden de G y el numero de vertices de grado 1.


b) Sea T un arbol m-ario completo con 201 nodos, 161 de los cuales son hojas.
1) >Cual es el valor de m?
2) >Cuantas aristas tiene T?
3) >Cual es la altura minima de T?

En línea
colipan
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 15


Ver Perfil
« Respuesta #3 : 09 Diciembre, 2009, 09:55 »

Disculpa

Un arbol m-ario T = (V,A) es completo si los vertices internos tienen grado de salida m y las hojas tienen grado de salida 0
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.144


Ver Perfil
« Respuesta #4 : 09 Diciembre, 2009, 10:21 »

Hola

 Para el (b). Se cumple que el número de nodos [texx]k[/texx] que no son hojas cumple:

[texx] n=km+1[/texx]

  siendo [texx]n[/texx] los nodos totales.

 En nuestro caso:

[texx] 201=m(201-161)+1[/texx]

 de donde [texx]m=5[/texx].

 El número de aristas es el número de nodos menos uno.

 El número máximo de hojas de un árbol [texx]5[/texx]-ario de altura [texx]h[/texx] es:
 
 [texx]5^h[/texx]

 Con eso deduce la altura mínima de tu árbol.

Saludos.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.144


Ver Perfil
« Respuesta #5 : 09 Diciembre, 2009, 13:11 »

Hola

 En cuanto al (a), si llamamos [texx]x[/texx] al número de vértices de grado [texx]1[/texx], el número total de vértices de tu grafo es:

[texx] n=6+2+3+x=11+x[/texx]

 El número de aristas es:

[texx] a=\dfrac{6\cdot 2+2\cdot 3+3\cdot 4+x}{2}=\dfrac{30+x}{2}[/texx]

 Si retiramos tres de ellas tenemos un árbol generador, por lo que:

[texx] a-3=n-1[/texx]

Saludos.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!