UNIVERSIDAD DISTRITAL FRANCISCO JOS DE CALDAS
FACULTAD DE INGENIERA
CIENCIAS DE LA COMPUTACIN II
___________________________________________________________________________
CONSULTA N5
___________________________________________________________________________
RBOLES COMO GRAFOS
PRESENTADO POR:
DAVID CAMILO ARANGUREN JIMENEZ
COD. 20132020623
CARLOS ANDRES AGUIRRE CAAS
COD. 20141020215
DOCENTE:
JULIO CESAR FLOREZ BAEZ
BOGOT - COLOMBIA
16 DE ABRIL DEL 2017
TABLA DE CONTENIDOS
TABLA DE CONTENIDOS 2
INTRODUCCIN 3
RBOL 4
DEMOSTRACIN 4
CARACTERSTICAS DE UN GRAFO RBOL G 4
PROPIEDADES 5
DISTANCIA EXCENTRICIDAD Y CENTRO DE UN RBOL 8
EN GENERAL DE UN RBOL 12
LISTA DE REFERENCIAS 19
INTRODUCCIN
Como ya se ha visto en consultas previas, existen muchos tipos de grafos que se distinguen
entre s y todos pueden ser aplicados en diferentes campos como en las ciencias de la
computacin, es aqu donde incursionamos en el grafo especial llamado rbol.
Los tipos especficos de grafos llamados rboles fueron utilizados por primera vez en 1847
por Gustav Kirchhoff (1824-1887) en su trabajo en redes elctricas, aunque posteriormente
fueron desarrollados y definidos de nuevo por Arthur Cayley (1821-1895). En 1875, Cayley
us estos grafos especiales para enumerar los ismeros diferentes de los hidrocarburos
+ .
saturados C H (Grimaldi, pg. 607).
n 2 n+2 n Z
Al transcurrir los aos tambin se han venido utilizando a los rboles en otros aspectos, por
ejemplo con la aparicin de los componentes digitales se encontraron nuevas aplicaciones
para los rboles, tales como redes. Algunos tipos especiales de rboles son muy importantes
en el estudio de las estructuras de datos, las ordenaciones, la teora de codificacin y en la
solucin de ciertos problemas de optimizacin. De aqu la importancia del tema de esta
consulta donde se realizar una introduccin a los rboles como grafos especiales al estudiar
sus principales propiedades y caractersticas.
RBOL
Un rbol se define como un grafo conexo y acclico, aunque cabe recalcar que un grafo no
conexo y acclico es un bosque, y obviamente, cada componente conexo de un bosque es un
rbol (Un bosque es una unin disjunta de rboles). A continuacin una definicin ms
formal:
El grafo G es un rbol si, y slo s, todo par de vrtices de G est conectado por una cadena
nica. En la figura 1, el grafo G1 es un rbol ya que es conexo y acclico, mientras que el
grafo G2 no lo es ya que contiene el ciclo {3, 4, 5}.
figura 1 (rbol. creada por nosotros para fines ilustrativos.)
DEMOSTRACIN
Si tenemos a G el cual es un rbol. Por ser conexo, todo par de vrtices est conectado al
menos por una cadena. Si existiera un par de vrtices conectado por dos cadenas distintas, la
unin de estas cadenas contendra un ciclo, en contradiccin con la definicin de rbol.
Recprocamente, admtase que G cumple la condicin de conexin nica. Obviamente G es
conexo, pero adems es acclico, ya que, de existir un ciclo, dos vrtices distintos de dicho
ciclo estaran conectados por dos cadenas distintas. Luego G es un rbol. Tambin hay que
observar que en este caso se ha supuesto tcticamente la inexistencia de lazos.
CARACTERSTICAS DE UN GRAFO RBOL G
1. G es conexo y no tiene ciclos .
2. G no tiene ciclos y, si se aade alguna arista se forma un ciclo.
3. G es conexo y si se le quita alguna arista deja de ser conexo.
4. G es conexo y el grafo completo de 3 vrtices K 3 no es un menor de
G.
5. Dos vrtices cualesquiera de G estn conectados por un nico camino
simple.
PROPIEDADES
Todo rbol es a su vez un grafo con slo un conjunto numerable de vrtices es adems un
grafo plano.
Ejemplo:
En teora de grafos, un grafo plano (o planar) es un grafo que puede ser dibujado en el plano
sin que ninguna arista se cruce o en una definicin ms formal puede ser que este grafo puede
ser "incrustado" en un plano. En la figura 2 apreciamos un grafo que cumple con estas
caractersticas.
figura 2 (grafo plano. creada por nosotros para fines ilustrativos.)
Todo grafo conexo G admite un rbol de expansin, que es un rbol que contiene cada vrtice
de G y cuyas aristas son aristas de G.
Ejemplo:
En la figura 3 se aprecian dos grafos, G1 = ({A, B, C, D}, {a, b, c}) y G = ({A, B, C, D, E, F,
G}, {a, b, c, d, e, f}). En donde G es rbol de expansin, rbol generador o rbol recubridor
de G1 ya que sus vrtices contienen a cada uno de los vrtices de G1 al igual que todas sus
aristas.
figura 3 (rbol k-ario. creada por nosotros para fines ilustrativos.)
Todo rbol k-ario completo de altura h tiene kh hojas.
Ejemplo:
En la figura 3 se aprecia un grafo rbol K-ario con altura 2 y en donde K es 3, Por lo que el
nmero de hojas que contiene este rbol es K h = 32 = 9 nodos hojas.
figura 3 (rbol k-ario. creada por nosotros para fines ilustrativos.)
Dado n vrtices etiquetados, hay n n2 maneras diferentes de conectarlos para construir un
grafo. El resultado se llama frmula de Cayley. El nmero de rboles con n vrtices de grado
d1,d2,...,dn es:
En cualquier rbol T = (V, S), |V| = |S| + 1.
Ejemplo:
En la figura 4 se aprecian dos grafos G1= (V1, S1) y G2 = (V2, S2) , en donde:
V1 = (1, 2, 3, 4, 5), V2 = (1, 2, 3, 4)
S1 = (a, b, c, d), S2 = (x, y, z)
por lo que:
G1 = ({1, 2, 3, 4, 5}, {a, b, c, d})
G2 = ({1, 2, 3, 4}, {x,y,z})
Luego:
|V1| = |S1| + 1, 5=4+1
|V2| = |S2| + 1, 4=3+1
Por lo que concluimos que G1 es rbol y G2 no lo es.
figura 4 (relacin aristas-nodos. creada por nosotros para fines ilustrativos.)
DISTANCIA EXCENTRICIDAD Y CENTRO DE UN RBOL
Sea G un grafo no trivial (es un grafo con 0 aristas, y 1 vrtices) y u,v una pareja de vrtices
de G, la distancia, d g (u,v) o d(u,v) entre u y v es la longitud del u-v camino ms
corto en G, si tal camino existe. Si G no contiene un camino de u-v, entonces se
dice que d(u,v)= (Sansaloni, s.f).
La distancia en un grafo G es una funcin mtrica (conjunto que lleva asociada una funcin
distancia, es decir, que esta funcin est definida sobre dicho conjunto, cumpliendo
propiedades atribuidas a la distancia), y cumple con las siguientes propiedades:
d(u,v) 0 y d(u,v)=0 u=v
d(u,v) = d(v,u) u,v V(G)
d(u,v) d(u,w) + d(w,v) u,v,w V(G)
como tal dentro de una rbol la distancia o longitud de un camino X es el nmero de arcos o
aristas que deben ser recorridas para llegar desde la raz al nodo h (nodo al que desea llegar).
Dentro de un rbol encontramos el concepto de longitud de camino interno (LCI) la cual
significa la suma de las longitudes de camino de todos los nodos del rbol, y se calcula por
medio de la siguiente frmula.
h
LCI = n ii donde
i=1
i = nivel del rbol
h = altura del rbol
ni = nmero de nodos en el nivel i
figura 5 (longitud de camino interno, obtenida de:[Link]
[Link]?cb=1386363956 )
para hallar la media de la longitud dentro de una rbol utilizamos la siguiente operacin:
LCIM = LCI / N donde
LCIM = Longitud media de camino interno
LCI = longitud de camino interno
N = nmero de nodos
figura 6 (longitud media de camino interno, obtenida de:[Link]
phpapp01/95/[Link]?cb=1386363956)
Ahora para poder explicar como calcular la longitud de un camino externo es necesario
definir dos conceptos muy importantes.
rbol extendido: Es aquel en el que el nmero de hijos de cada nodos es igual al grado del
rbol En caso de que algn nodo no cumpla con esta condicin se debe incorporar al mismo
tantos nodos especiales como se requiera.
Nodos especiales: Tienen como objetivo:
Reemplazar las ramas vacas o nulas
No pueden tener descendientes
Se representa en forma de cuadrado.
Ejemplo
figura 7 (rbol extendido, obtenida de:[Link]
BNI/AAAAAAAAAB8/Q9GESWUDuXY/s1600/arbol+[Link])
la longitud de camino externo (LCE) es la sumatoria de las longitudes de camino de todos los
nodos especiales del rbol y se calcula con la siguiente frmula
h+1
LCI = n ei donde
i=2
h = altura del rbol
i = niveles del rbol
ne = nmero de nodos especiales en el nivel i
figura 8 (longitud de camino externo, obtenida de:[Link]
[Link]?cb=1372160411)
para hallar la longitud media de un camino externo dividimos la longitud de camino externo
con por el nmero de vrtices especiales.
LCEM = LCE / Ne
Ejemplo:
figura 9 (longitud media de camino externo, obtenida de:[Link]
Z8LPj3UIyYzkoOWT_hFkwzILNPD0Jx1FhEANC3q9GSsgtoMJX9FJBgfHUCmOBB9nACrg=s114)
la excentricidad de v V se define como la distancia mxima desde v a cualquier otro
vrtice del grafo G siguiendo caminos de longitud mnima (Grafos: conceptos bsicos).
algunos autores llaman a la mxima excentricidad como el dimetro y lo denotan como d(G)
y llaman a la mnima excentricidad como el radio y lo denotan como r(G)
ejemplo
figura 10 (excentricidad, dimetro y radio dentro de un grafo. creada por nosotros para fines ilustrativos.)
lo primero que hacemos es mirar la excentricidad con respecto a cade vrtice del grafo
e(v1) = 3 e(v2) = 2
e(v3) = 2 e(v4) = 3
e(v5) = 3 e(v1) = e(v4) = e(v5) = 3
e(v2) = e(v3) = 2
entonces tenemos que d(G) = 3 y r(G) = 2.
En algunos grafos se cumple que la excentricidad de un vrtice v es igual al radio del grafo
G, e(v) = r(G), en este caso se dice que v es un vrtice central de G.
Como se pudo ver en el ejemplo anterior es posible que varios vrtices tengan la misma
excentricidad entonces en este caso se dice que tanto estos vrtices como las aristas que los
conectan forman el centro del grafo.
Ejemplo:
figura 11 (centro de un arbol. creada por nosotros para fines ilustrativos.)
EN GENERAL DE UN RBOL
Un rbol es un grafo en el cual entre todo par de vrtices existe un nico camino simple el
cual debe cumplir las siguientes propiedades:
Si a un rbol se le agrega una arista entre dos de sus vrtices, deja de ser rbol.
Todas las aristas de un rbol son puentes
En todo rbol se cumple que: | V | = | A | + 1
Se denomina BOSQUE al grafo no conexo en el cual cada una de sus componentes es un
rbol.
En un bosque de k componentes se cumple que | V | = | A | + k
Otros datos interesantes:
Un vrtice v de un rbol se dice que es HOJA cuando g(v) = 1
Se llama RAMA a todo camino que va desde la raz a alguna hoja.
Otras definiciones que se deben tener en cuenta son las siguientes:
Antecesor: v es antecesor de w cuando existe un nico camino simple de v a w.
Sucesor: w es sucesor de v en el caso anterior
Padre: v es padre de w cuando existe una arista de v a w.
Hijo: w es hijo de v en el caso anterior.
Hermanos: v y w son hermanos si tienen el mismo nodo padre
figura 12 (tipos de nodos dentro de un rbol. creada por nosotros para fines ilustrativos.)
Algunos de los conceptos importantes al momento de trabajar con grafos son:
Nivel: es el nmero de nodos que deben ser recorridos para llegar de un vrtice desde la raz.
Altura: se le llama altura al nmero mximo de niveles de un rbol.
figura 13 (ejemplo de nivel y altura de un rbol. obtenida de [Link]
content/uploads/2014/08/[Link])
Peso: se conoce como peso al nmero de nodos que tiene un rbol.
figura 14 (ejemplo de peso en un rbol. obtenida de [Link]
content/uploads/2014/08/[Link])
Orden: es el nmero mximo de hijos que puede tener un nodo.
figura 15 (ejemplo de el orden de un rbol. obtenida de [Link]
content/uploads/2014/08/[Link])
Grado: es el nmero mayor de hijos que tiene alguno de los nodos pertenecientes a un rbol
y est limitado por el Orden.
figura 16 (ejemplo de el grado de un rbol. obtenida de [Link]
content/uploads/2014/08/[Link])
Los principales tipos de rboles son
binarios: es un rbol binario si cada vrtice tiene a lo sumo 2 hijos.
binario completo: se dice que un rbol es binario completo si cada vrtice tiene exactamente
2 hijos.
binario total o perfecto: se dice que un rbol es binario total si todas las hojas estn en el
mismo nivel.
figura 17 (ejemplo rbol binario completo y total. obtenida de [Link]
content/uploads/2014/08/[Link])
n-arios: es una rbol n-ario si cada vrtice tiene a lo sumo n hijos.
n-ario completo: se dice que un rbol es n-ario completo si cada vrtice distintos de las hojas
tiene exactamente n hijos
n-ario total o perfecto: se dice que es un rbol n-ario total si todas sus hojas estn en el mismo
nivel
Formas de recorrer un rbol
Recorrer un rbol significa nombrar todos los vrtices del rbol siguiendo un determinado
orden. Ello es muy importante si consideramos una base de datos de forma
arborescente. Cada vrtice del rbol es un nodo de informacin, o sea un registro de la
base (Universidad tecnolgica nacional facultad regional Buenos Aires).
Existen 3 formas de recorrer un grafo
1. pre-orden
figura 18 (ejemplo recorrido pre-orden de un rbol. obtenida de [Link]
content/uploads/2014/08/[Link])
2. post-orden
figura 19 (ejemplo recorrido post-orden de un rbol. obtenida de [Link]
content/uploads/2014/08/[Link])
3. in-orden
figura 20 (ejemplo recorrido in-orden de un rbol. obtenida de [Link]
content/uploads/2014/08/[Link])
Algunas de las aplicaciones de los rboles en la vida real
Los rboles son muy tiles en las ciencias de la computacin, ya que sirven para representar
estructuras de datos jerrquicas, de forma de optimizar el tiempo de acceso a los registros.
En qumica orgnica, por ejemplo, las molculas de los alcanos son rboles. El concepto de
isometra tiene que ver con el isomorfismo.
figura 21 (ejemplo de aplicacin de los rboles. obtenida de [Link]
[Link] )
Tambin los rboles tienen mltiples usos, ya que con ellos se pueden representar datos de
una manera organizada. Por ejemplo, los organigramas de las organizaciones son rboles
dirigidos con raz, y el hecho de que el grado positivo (entrante) de cada nodo o vrtice sea 1
significa la unidad de mando.
figura 22 (ejemplo de aplicacin de los rboles. obtenida de [Link]
LISTA DE REFERENCIAS
1. Ralph P. Grimaldi. Matemticas discretas y combinatoria Tercera edicin: Addison- Wesley
Iberoamericana, S.A
2. Fausto A. Toranzos. Introduccin a la teora de grafos. The General Secretariat of the
Organization of American States Washington, D.C.
3. Blancarte, O. (22 de Agosto de 2014). Estructura de datos rboles. Obtenido de
[Link]
4. Grafos: conceptos bsicos. (s.f.). Obtenido de
[Link]
[Link]
5. Sansaloni, T. C. (s.f.). Fundamentos de la teora de grafos. Obtenido de
[Link]
6. Universidad tecnolgica nacional facultad regional Buenos Aires. (s.f.). Grafos, digrafos y
rboles. Obtenido de [Link]
%C3%ADgrafos%20y%20%C3%[Link]
