En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen)
es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o
arcos, que permiten representar relaciones binarias entre elementos de un conjunto
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o
nodos) unidos por líneas (aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre
unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede
representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales
y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones
inalámbricas).
Los árboles corresponden a una de las subclases de grafos de uso más amplio,
particularmente en computación. Los grafos se pueden clasificar en dos grupos: dirigidos y
no dirigidos. Los arboles forman parte de los no dirigidos. Sirven para organizar y relacionar
datos en una base de datos, por ejemplo. Esto permite realizar operaciones de manera
eficiente. Por ejemplo, un árbol de definición jerárquica se utiliza para configurar una base
de datos para los registros de libros existentes en diversas bibliotecas. Otro ejemplo de la
utilización de árboles son los diccionarios. A partir de una palabra, se realiza una búsqueda
en el árbol para saber si está incluida en el conjunto, y si existe, se obtienen sus datos
asociados (por ejemplo, si es un verbo, un sustantivo, un artículo, etc.).
DEFINICIONES
Un Grafo (o grafo no dirigido): es un grafo en el cual sus aristas son no dirigidas,
es decir, no están orientadas en ningún sentido.
Un grafo dirigido (o digrafo) s un tipo de grafo en el cual las aristas tienen un
sentido definido, a diferencia del grafo no dirigido, en el cual las aristas son
relaciones simétricas y no apuntan en ningún sentido.
Grafo conexo: un grafo G es conexo si dados cualesquiera dos vértices v y w en
G, existe un camino de v a w.
Camino: sean v0 y vn vértices de un grafo. Un camino de v0 a vn de longitud n es
una sucesión alternante de n+1 vértices y n aristas que comienza con el vértice v0
y termina con el vértice vn.
Longitud del camino: es el número de aristas que contiene.
Ciclo: sean v y w vértices en un grafo G, un ciclo o circuito es un camino de
longitud distinta de 0 de v a w, sin aristas repetidas.
Subgrafo: es un grafo cuyo conjunto de vértices es un subconjunto del de G, cuyo
conjunto de aristas es un subconjunto del conjunto de las aristas de G, y tal que la
aplicación x es la restricción de la aplicación de G.
Grafo con pesos (o poderado): es un grafo en el cual se le asignan valores a las
aristas y la longitud del camino de un grafo con pesos es la suma de todos los
pesos de las aristas en la ruta (camino).
Árbol: Es un grafo en el que cualesquiera dos vértices están conectados
por exactamente un camino.
Bosque: Un bosque es un conjunto de árboles; o de forma equivalente, un bosque
es un grafo acíclico.
En la ciencia de la computación definimos un árbol como un conjunto de nodos y líneas. Un
nodo es un elemento de información que reside en el árbol. Una línea es un par de nodos
ordenados, y a la secuencia de líneas se le denomina ruta. Además, los árboles tienen las
siguientes propiedades:
Tienen un nodo al que se le llama raíz del árbol.
Todos los nodos, excepto la raíz, tienen una sola línea de entrada (el nodo raíz no
tiene ninguna).
Existe una ruta única del nodo raíz a todos los demás nodos del árbol. Si hay una
ruta <a,b>, entonces a „b‟ se le denomina “hijo” de “a” y es el nodo raíz de un
subárbol.
Gráficamente puede representarse una estructura árbol de diferentes maneras y
todas ellas equivalentes;
CARACTERISTICAS DE UN ÁRBOL
1. NODO indica un elemento, o ítem, de información.
2. Todo árbol que no es vacío, tiene un único nodo raíz.
3. Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el
nodo Y. X es hijo de Y.
4. Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. X es
padre de Y.
5. Se dice que todos los nodos que son descendientes directos (hijos) de un mismo
nodo (padre), son hermanos.
6. Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal
u hoja.
7. Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.
8. Grado es el número de descendientes directos de un determinado nodo. Grado del
árbol es el máximo grado de todos los nodos del árbol.
9. Nivel es el número de arcos que deben ser recorridos para llegar a un determinado
nodo. Por definición, la raíz tiene nivel 1.
10 Altura del árbol es el máximo número de niveles de todos los nodos del árbol.
Tipos de árboles
-ÁRBOL BINARIO
En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada
nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos
(de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no
almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el
hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles
binarios de búsqueda, los montículos binarios y Codificación de Huffman.
Tipos de árboles binarios
Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con
cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).
A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un
árbol binario completo como un árbol binario lleno en el que todas las hojas están a
profundidad n o n-1, para alguna n.
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En
un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el
nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
Árbol binario de búsqueda auto-balanceable
En ciencias de la computación, un árbol binario de búsqueda auto-balanceable o equilibrado
es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de
nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente.
Esto es importante, ya que muchas operaciones en un árbol de búsqueda binaria tardan un
tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios
pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son
insertadas en orden. Mantener baja la altura se consigue habitualmente realizando
transformaciones en el árbol, como la rotación de árboles, en momentos clave.
Tiempos para varias operaciones en términos del número de nodos en el árbol n:
Operación Tiempo en cota superior asintótica
Búsqueda O(log n)
Inserción O(log n)
Eliminación O(log n)
Iteración en orden O(n)
Para algunas implementaciones estos tiempos son el peor caso, mientras que para otras
están amortizados.
Árbol-B
En las ciencias de la computación, los árboles-B ó B-árboles son estructuras de datos de
árbol que se encuentran comúnmente en las implementaciones de bases de datos y
sistemas de archivos. Los árboles B mantienen los datos ordenados y las inserciones y
eliminaciones se realizan en tiempo logarítmico amortizado.
B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener
varios hijos, existiendo una relación de orden entre ellos, tal como muestra el dibujo.
Un árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un árbol
que satisface las siguientes propiedades:
[Link] nodo tiene como máximo M hijos.
[Link] nodo (excepto raíz y hojas) tiene como mínimo M/2 hijos.
[Link] raíz tiene al menos 2 hijos si no es un nodo hoja.
[Link] los nodos hoja aparecen al mismo nivel.
[Link] nodo no hoja con k hijos contiene k-1 elementos almacenados.
[Link] hijos que cuelgan de la raíz (r1, ···, rm) tienen que cumplir ciertas condiciones:
1. El primero tiene valor menor que r1.
2. El segundo tiene valor mayor que r1 y menor que r2, etc.
3. El último hijo tiene valor mayor que rm.
Árbol multicamino
Los árboles multicamino o árboles multirrama son estructuras de datos de tipo árbol usadas
en computación.
Un árbol multicamino posee un grado g mayor a dos, donde cada nodo de información del
árbol tiene un máximo de g hijos.
