Definición
Es una estructura de
datos ampliamente usada que emula la forma de un árbol (un conjunto de nodos conectados).
Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o
más nodos hijos conectados a él.
Representación
en memoria de árboles
Hay dos formas tradicionales
de representar un árbol binario en memoria:
·
Por
medio de datos tipo punteros también conocidos como variables dinámicas o
listas.
·
Por
medio de arreglos.
Los nodos del árbol
binario serán representados como registros que contendrán como mínimo tres
campos. En un campo se almacenará la información del nodo. Los dos restantes se
utilizarán para apuntar al subárbol izquierdo y derecho del subárbol en
cuestión. Cada nodo se representa gráficamente de la siguiente manera:
Árboles generales
Es una estructura
jerárquica aplicada sobre una colección de elementos u objetos llamados nodos;
uno de los cuales es conocido como raíz. Además se crea una relación o
parentesco entre los nodos dando lugar a términos como padre, hijo, hermano,
antecesor, sucesor, ancestro, etc. Formalmente se define un árbol de tipo T
como una estructura homogénea que es la concatenación de un elemento de tipo T
junto con un número finito de árboles disjuntos, llamados subárboles. Una forma
particular de árbol puede ser la estructura vacía.
Árboles binarios
DISTINTO
Se dice que dos
árboles binarios son distintos cuando sus estructuras son diferentes.
SIMILARES
Dos árboles binarios
son similares cuando sus estructuras son idénticas, pero la información que
contienen sus nodos es diferente.
EQUIVALENTES
Son aquellos árboles
que son similares y que además los nodos contienen la misma información.
COMPLETOS
Son aquellos árboles
en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el
subárbol izquierdo y el subárbol derecho.
Recorridos en un árbol binario
Hay tres maneras de
recorrer un árbol: en inorden, preorden y postorden. Cada una de ellas tiene
una secuencia distinta para analizar el árbol.
Preorden
Se visita primero la
raíz, luego el subárbol izquierdo y por último el subárbol derecho, esto de
manera recursiva para cada subárbol partiendo de la raíz.
Examinar
la raíz.
·
Recorrer
el subárbol izquierdo en preorden.
·
Recorrer
el subárbol derecho en preorden.
Inorden
Se visita primero el
subárbol izquierdo, luego la raíz y por último el subárbol derecho, esto de
manera recursiva para cada subárbol partiendo de la raíz.
·
Recorrer
el subárbol izquierdo en inorden.
·
Examinar
la raíz.
·
Recorrer
el subárbol derecho en inorden.
Postorden
Se visita primero el
subárbol izquierdo luego el subárbol derecho y por último la raíz, esto de
manera recursiva para cada subárbol partiendo de la raíz.
·
Recorrer
el subárbol izquierdo en postorden.
·
Recorrer
el subárbol derecho en postorden.
·
Examinar
la raíz.
Balanceo de árboles binarios
Mantener un árbol
perfectamente balanceado es muy costoso, entonces se adopta un concepto menos
estricto de balanceo: árboles balanceados (equilibrados). Un árbol está
balanceado si para cada uno de sus nodos se tiene que las alturas de sus dos
subárboles difieren a lo más en 1. Se tiene que un árbol perfectamente
balanceado es también balanceado; pero no es cierto lo contrario.
Para estos árboles el
mantenimiento del balanceo no es muy costoso, y las operaciones de búsqueda,
inserción y borrado mantienen su orden O(log2n).
Los árboles pueden
estar balanceados por altura o por peso.
Árbol balanceado por
altura: en dónde todos los hijos o nodos hoja se intentan mantener a la misma
distancia de la raíz.
• Árbol balanceado
por peso: en dónde los nodos más visitados o utilizados se mantienen a poca
distancia de la raíz Un árbol es un grafo conexo y sin ciclos.
Propiedades:
Si G = (V, A) es un
árbol de n vértices, entonces:
1)
Para
todo par de vértices x e y existe un único camino de x a y.
2)
Todas las aristas de G son puentes.
3)
½ A½ = n - 1.
4)
Todo árbol tiene al menos dos hojas (vértices
de grado uno).
Caracterizaciones: Un
grafo G= (V,A) es un árbol Û Para todo par de vértices x e y existe un único
camino de x a y Û G es conexo y todas las aristas son puentes Û G es acíclico y
maximal (la adición de una arista nueva origina un ciclo) Û G es conexo y ½ A½
= n - 1 Û G es acíclico y ½ A½ = n - 1
Los árboles forman
una de las subclases de las gráficas de uso más amplio. En
el terreno de la
computación los árboles sirven para organizar y relacionar lo datos de una base
de datos.
Clases para la implementación de árboles.
Para estructurar un
conjunto de elementos en árbol, deberemos escoger uno de ellos e1 al que
llamaremos raíz del árbol. Del resto de los elementos se selecciona un
subconjunto e2,..., ek estableciendo una relación padre-hijo entre la raíz y
cada uno de dichos elementos de manera que e1 es llamado el padre de e2,de
e3,...ek y cada uno de ellos es llamado un hijo de e1. Iterativamente podemos
realizar la misma operación para cada uno de estos elementos asignando a cada
uno de ellos un número de 0 o más hijos hasta que no tengamos más elementos que
insertar. El único elemento que no tiene padre es e1,la raíz del árbol. Por
otro lado hay un conjunto de elementos que no tienen hijos aunque sí padre que
son llamados hojas .Como hemos visto la relación de paternidad es una relación
uno a muchos.
También podemos
implementar tres tipos de operaciones en los arboles como son: búsqueda,
inserción, eliminación.
Búsqueda
Se va a recorriendo
el árbol, si el nodo actual no es el buscado se decide si hay que buscar por la
derecha o por la izquierda.
El algoritmo para
encontrar el nodo o llegar al árbol vacío puede desarrollarse como algoritmo
recursivo del nodo del árbol o como algoritmo iterativo del árbol.
Inserción
Nos desplazamos
dependiendo del resultado de la comparación, cuando llegamos a una hoja
insertamos. Si la clave del elemento a insertar coincide con la del nodo raíz
el elemento a insertar sustituye al que había. Si es menor buscamos el subárbol
izquierdo, Si es mayor buscamos el subárbol derecho.
Eliminación
Si se trata de una
hoja se elimina directamente, si se tiene un único hijo se elimina el nodo
haciendo que su nodo padre pase a referenciar a su hijo.
Aplicación del tema
Los árboles tienen
una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para
representar fórmulas matemáticas, para organizar adecuadamente la información,
para construir un árbol genealógico, en la toma de decisiones, para el análisis
de circuitos eléctricos y para numerar los capítulos y secciones de un libro.
Las aplicaciones de
los árboles binarios son muy variadas ya que se les puede utilizar para
representar una estructura en la cual es posible tomar decisiones con dos
opciones en distintos puntos.
Aportaciones
El tema de árboles nos aportó el saber que existen estructuras de datos
en las que es posible almacenar datos del mismo tipo partiendo de una idea
principal hacia las demás que van surgiendo de la misma. También nos dimos
cuenta que su aplicación de los arboles binarios es múltiple y está en cosas
que normalmente usamos.
Conclusiones
Los árboles son estructuras de datos formados por una raíz o vértice y
por aristas o arcos. Estos se representan en memoria por medio de arreglos y
listas, generalmente tienen tres tipos de recorrido que son en preorden,
inorden y postorden, teniendo también tres tipos de operaciones a realizar
sobre estos como eliminación, inserción y
búsqueda. La manera en que aplicamos este tema de árboles es infinita y
un ejemplo de ello es en la organización de información.
TEMA: Grafos
Los grafos sirven para representar relaciones arbitrarias (no
necesariamente jerárquicas) entre objetos de datos. En general, un grafo
es una manera de representar relaciones que existen entre pares de objetos. Un
grafo se representa mediante un diagrama en el cual a cada vértice le
corresponde un punto y si dos vértices son adyacentes se unen sus puntos
correspondientes mediante una línea.
Definición
Un grafo es un conjunto de objetos, llamados vértices, y relaciones entre
objetos que establecen una relación entre pares de vértices, representadas por
aristas. Un grafo se define como un par G = (V, A), donde V es un conjunto
finito no vacío de vértices y A es un conjunto de pares de vértices de V, es
decir, las aristas.
Tipos de grafos
Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.
Grafo
dirigido
Es
aquel cuyas aristas son dirigidas. Los grafos dirigidos suelen representar
relaciones asimétricas.
Consta de:
1. un conjunto finito
de vértices V
2. un conjunto de
aristas E en el que cada arista es un conjunto de exactamente dos vértices.
Grafo
no dirigido
Es
aquel cuyas aristas son no dirigidas. Representan relaciones simétricas.
Consta de:
1. un conjunto finito
de vértices V
2. un conjunto de
arcos E _ V × V (obsérvese que cada arco es un par ordenado vértices)
Algunos
de los principales tipos de grafos son los que se muestran a continuación:
Grafos isomorfos
Dos grafos G1 = (V1,
A1) y G2 = (V2, A2) se dice que son isomorfos cuando existe una biyección entre
los conjuntos de sus vértices que conserva la adyacencia.
Si dos grafos G1 y G2 son isomorfos, tienen el mismo número de
vértices, el mismo número de aristas, el mismo número de vértices de cualquier
grado, el mismo número de ciclos de cualquier longitud, etc.
Grafos Planares
Decimos que un grafo G es planar si se puede dibujar en el plano sin
que los lados se crucen fuera de sus extremos.
Un grafo G
= (V,E) es regular de grado k o k-regular
si cada vértice tiene grado k; es decir, un grafo es regular si todos los vértices tienen el mismo
grado.
Grafos Bipartitos
Se dice que un grafo
simple G = (V,E) es bipartito si el conjunto de vértices V se puede dividir en
dos conjuntos disjuntos V1, V2, (V1 ∪ V2 = V, V1 ∩ V2 = ∅,
de tal manera que toda arista e ∈ E conecta un vértice
de V1 con un vértice de V2.
Grafo bipartido
completo
Un grafo bipartido completo si V=V1∪V2 y dos vértices de V
están unidos por una arista de E si y solo si un vértice está en V1 y
el otro en V2. Se denota por K r, s al grafo bipartido completo
donde V1 tiene r vértices y V2 tiene s vértices.
Un
grafo bipartito regular
Se
denota Km, n donde m, n es el grado de cada conjunto disjunto de vértices.
Grafo
completo
Un grafo
es completo si
existen aristas uniendo todos
los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe
tener una arista e
que los une.
Grafos Platónicos
Son los Grafos
formados por los vértices y aristas de los cinco sólidos regulares (Sólidos
Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el
icosaedro.
Grafo nulo
Se dice que un grafo
es nulo cuando los vértices que lo componen no están conectados, esto es, que
son vértices aislados.
Grafo Hamiltoniano
Un grafo o multígrafo
que contenga un ciclo de Hamilton se denomina Hamiltoniano. Un ciclo simple en
un grafo o multígrafo G se dice que es de Hamilton, si contiene a todos los
vértices de G.
Grafo Euleriano
Un grafo que admita
un ciclo de Euler se denomina grafo euleriano. Un ciclo de un grafo o
multígrafo se dice de Euler si pasa por todos los vértices recorriendo cada
arista exactamente una vez.
Grafo
conexo
Un grafo
se dice que es conexo si cada par de sus vértices están conectados.
Grafos
ponderados
Llamamos
grafos ponderados a los grafos en los que se asigna un número a cada una de las
aristas.
Representación de grafos en memoria
Existen varias
estructuras de datos que pueden utilizarse para representar grafos. La elección
de la estructura de datos adecuada depende del tipo de operaciones que se
quieran aplicar al conjunto de vértices y aristas del grafo en cuestión.
Hay tres maneras de representar un grafo en memoria
1.- Mediante
matrices:
·
Incidencia
·
Adyacencia
2.- Mediante listas:
·
Adyacencia
Matriz de incidencia
La matriz de
incidencia es una matriz binaria (sus elementos solo pueden ser 0 y 1) que se
utiliza para representar relaciones binarias.
Construcción de la matriz de incidencia a partir de un
grafo
·
Las
columnas de la matriz representan las aristas del grafo
·
Las
filas representan a los distintos nodos
·
Por
cada nodo unido por una arista, ponemos un 1 en el lugar correspondiente y
llenamos el resto de las ubicaciones con 0
Ejemplo de una matriz de incidencia
En el ejemplo de la
siguiente figura, si sumamos las cantidades de 1´s que hay en cada columna
veremos que solo hay dos.
Pero si sumamos las
cantidades de 1´s que hay por cada fila, comprobaremos que los nodos 2, 4 y 5
poseen un valor de 3.
Ese valor indica la
cantidad de aristas que inciden sobre el
nodo.
Matriz de adyacencia
Las filas representan
los nodos de origen y las columnas, los nodos destinos.
De esta forma cada
intersección entre fila y columna contiene un valor booleano que indica si hay
o no conexión entre los nodos a los que se refiere.
Si se trata de un
grafo con pesos, en lugar de usar valores booleanos, usaremos los propios pesos
de cada enlace y en caso de que no exista conexión entre dos nodos,
rellenaremos esta casilla con un valor que representa un coste, es decir con el
valor Natural Last.
Ejemplo de una matriz de adyacencia
En caso de que el
grafo sea no dirigido, la matriz resultante es simétrica respecto a la diagonal
principal.
La representación de
un grafo mediante una matriz solo es válida cuando el número de nodos del grafo
es fijo.
Lista de adyacencia
Cada vértice tiene
una lista a vértices los cuales son adyacentes a él.
Esto causa:
redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia
B y viceversa).
Pero las búsquedas
son más rápidas al costo de almacenamiento extra.
En esta estructura de
datos la idea es asociar a cada vértice i del grafo en una lista que contenga
todos aquellos vértices j que sean adyacentes a él.
De esta forma solo
reservara memoria para los arcos
adyacentes a i y no para todos los posibles arcos que pudieran tener como
origen i.
El grafo, por lo
tanto, se representa por medio de un vector de n componentes donde cada
componente va a ser una lista de adyacencia correspondiente a cada uno de los
vértices del grafo.
Cada elemento de la
lista consta de un campo indicando el vértice adyacente. En caso de que el
grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor
de la etiqueta.
Ejemplo de una lista de adyacencia
Se asocia cada nodo
del grafo una lista que contenga todos aquellos nodos que sean adyacentes a él.
Clases para la implementación de grafos.
En esta sección se
analizan algunas de las operaciones sobre grafos, como:
·
Creación
·
Inserción
·
Búsqueda
·
Eliminación
Matriz de adyacencia
Creación
Se utiliza para crear
un grafo vacío, con un tamaño máximo y número de vértices igual a 0. Se pasa
como argumento un booleano que indica si se trata de un grafo dirigido o no
dirigido.
public
GrafoMA (boolean d) {
maxNodos
= numVertices = 0;
dirigido
= d;
}
Inserción de aristas
La inserción de una
arista (i, j) en la matriz supone asignar a la celda
correspondiente el valor true. Si se trata de un grafo dirigido, debe tenerse
en cuenta que el vértice origen i corresponde a fila, mientras
que el vértice destino j corresponde la columna. En caso de que
se trate de un grafo no dirigido, debe recordarse que la arista (i, j)
es igual a la arista (j, i) para que la matriz mantenga la
propiedad de la simetría.
public void insertaArista (int i,
int j) {
matrizAdy [i] [j] = true;
if (!dirigido)
matrizAdy [j] [i] = matrizAdy [i]
[j];
}
Eliminación de una arista
La
eliminación de la arista (i, j) es sencilla, consiste en asignar
el valor false a la celda correspondiente de la matriz. En caso de que se trate
de un grafo no dirigido, habrá de modificarse igualmente el valor correspondiente
a la arista (j, i):
public void eliminarArista (int i, int j) {
matrizAdy [i] [j] = false;
if
(!dirigido)
matrizAdy
[j] [i] = false;
}
Insertar vértices
La
modificación de los vértices del grafo supone un grado de complejidad mayor que
el tratamiento de las aristas. Para la inserción de un vértice, el código aquí
mostrado simplifica el método de manera que no deja insertar vértices si se
supera el límite de vértices del grafo (valor del campo maxNodos). En caso de
que no se supere el número máximo de vértices, simplemente se asigna el valor
false a las celdas correspondientes y se actualiza el campo numVertices:
public void insertaVertice (int n) {
if ( n
> maxNodos - numVertices )
System.out.println
("Error, se supera el número de nodos máximo");
else {
for (int i=0; i < numVertices + n; i++) {
for (int j = numVertices; j < numVertices + n; j++)
matrizAdy
[i] [j] = matrizAdy [j] [i] = false;
}
numVertices
= numVertices + n;
}
}
Lista de adyacencias
Creación
El
constructor Grafo (boolean d) se utiliza para crear un grafo vacío, con un
tamaño máximo y número de vértices igual a 0. El argumento booleano indica si
se trata de un grafo dirigido o no dirigido.
public
GrafoLA (boolean d) {
maxNodos
= numVertices = 0;
dirigido
= d;
}
Insertar aristas.
La
inserción de una arista (i, j) en la lista de adyacencias supone
insertar un nodo con clave j en la lista con índice i.
En caso de que se trate de un grafo no dirigido, debe recordarse que la arista
(i, j) es igual a la arista (j, i) de forma que
habrá que insertar en la lista con índice j el nodo con clave i.
public void insertaArista (int i, int j) {
if (i
>= numVertices)
System.out.println
("Error, no existe el vértice en el grafo");
else {
listaAdy[i].insertar (j);
if
(!dirigido)
listaAdy[j].insertar
(i);
}
}
Eliminar aristas
La
eliminación de la arista (i, j) consiste en eliminar el nodo con
clave j de la lista con índice i. Si el grafo es no
dirigido, habrá que eliminar el nodo con clave i de la lista con
índice j:
public void eliminaArista (int i, int j) {
if (j
>= numVertices)
System.out.println("Error,
no existe el vértice en el grafo");
else {
listaAdy[i].eliminar (j);
if
(!dirigido)
listaAdy[j].eliminar
(i);
}
}
Insertar vértices
Al igual
que en la matriz de adyacencias, no se permite insertar vértices si se supera
el límite de vértices del grafo (valor del campo maxNodos). El método aquí
propuesto tiene como argumento un entero que indica el número de vértices que
se desea añadir al grafo. En caso de que no se supere el número máximo de nodos
del grafo, se inicializan las n listas correspondientes a los vértices
que se añaden al grafo.
public void insertaVertice (int n) {
if (n
> maxNodos - numVertices)
System.out.println
("Error, se supera el número de nodos máximo del grafo");
else
for (int i = numVertices; i < numVertices + n; i++)
listaAdy[i]= new Lista();
numVertices += n;
}
Aplicación del tema
A menudo,
cuando se observa la red de rutas aéreas de un país interesa observar cómo ir
de una ciudad a otra por las rutas posibles. En consecuencia, se tiene dos
conjuntos de objetos distintos: ciudades y rutas.
Los
grafos se usan para almacenar datos que están relacionados de alguna manera
(relaciones de parentesco, puestos de trabajo, etc.); por esta razón se puede
decir que los grafos representan la estructura real de un problema. En lo que a
ingeniería de telecomunicaciones se refiere, los grafos son una importante
herramienta de trabajo, pues se utilizan tanto para diseño de circuitos como
para calcular la mejor ruta de comunicación en Internet, redes de computadoras,
redes de transporte y también son utilizadas en bases de datos (diagramas
entidad/relación).
El tema de grafos nos
fue de gran utilidad, necesitamos poder entenderlo ya que es una estructura
bastante amplia en cuanto a su uso y con ella podemos hacer bastantes cosas que
son representadas mediante estos diagramas de fácil estructuración. Sus
aportaciones son muchas y sin embargo no nos percatábamos de eso.
Conclusiones
Los grafos son
estructuras formadas por vértices o nodos y por aristas o arcos que
generalmente representan relaciones entre objetos de datos. Existen dos tipos
de grafos que son dirigidos y no dirigidos, entre otros como son completos,
isomorfos, bipartitos, regulares, planos, eulerianos, por mencionar algunos.
Generalmente se representan por medio de matrices y listas y en cuanto a su
implementación de operaciones tenemos cuatro que son: búsqueda, creación,
eliminación e inserción.
Hola estimados Vany y Cristian:
ResponderEliminar¡Excelente trabajo, muy bien!
¡Saludos cordiales!