Programacion imperativa modular Graphos.
Enviado por poland6525 • 15 de Junio de 2018 • 755 Palabras (4 Páginas) • 291 Visitas
...
G es ac´ıclico y |E | = |V | − 1[pic 17]
G es ac´ıclico, pero si agrega un nuevo arco a E , el grafo resultante es c´ıclico.[pic 18]
---------------------------------------------------------------
Un ´arbol con ra´ız es un ´arbol con un nodo distinguido r (la ra´ız)
Para un nodo x en un ´arbol con ra´ız r :
- Cualquier nodo y en el camino de r a x es un
ancestro de x.[pic 19]
- Si y es un ancestro de x entonces x es un
descendiente de y .
- El sub´arbol con ra´ız en x es el ´arbol formado por x y todos sus descendientes.
- Si el u´ltimo arco del camino entre r y x es (y, x ), y es el padre de x y x es hijo de y
- La ra´ız es el u´nico nodo que no tiene padre.
- Si dos nodos tienen el mismo padre, son
hermanos.
---------------------------------------------------------------
Para un nodo x en un ´arbol con ra´ız r :[pic 20]
- Un nodo sin hijos es una hoja o nodo externo.
- Un nodo que no es una hoja es un nodo interno.
- El nu´mero de hijos de un nodo es igual al
grado del nodo.
---------------------------------------------------------------
Para un nodo x en un ´arbol con ra´ız r :[pic 21]
- La longitud del camino de r a x es la
profundidad de x .
- Todos los nodos de la misma profundidad conforman un nivel del ´arbol.
- La altura de x es el nu´mero de arcos del camino m´as largo desde x hasta una hoja.
- La altura del ´arbol es la altura de su ra´ız.
---------------------------------------------------------------
En un ´arbol ordenado, los hijos de cada nodo tienen un orden: primer hijo, segundo hijo, etc.
[pic 22]
---------------------------------------------------------------
Un ´arbol binario T es una estructura definida sobre un conjunto finito de nodos tal que:
No tiene nodos, o[pic 23]
Est´a compuesta de tres conjuntos disyuntos de nodos: una ra´ız, un ´arbol binario llamado el sub´arbol izquierdo y un ´arbol binario llamado el sub´arbol derecho.[pic 24]
- El ´arbol binario sin nodos es el ´arbol nulo.[pic 25]
- Si el sub´arbol izquierdo/derecho no es nulo, su ra´ız es el hijo izquierdo/derecho de la ra´ız del ´arbol completo.
- Si un sub´arbol es nulo se dice que el hijo correspondiente no existe.
---------------------------------------------------------------
Un ´arbol binario es m´as que
...