ÁRBOLES BINARIOS DE BÚSQUEDA
Empezaremos
recordando lo que son los árboles. Un árbol es una colección de nodos que puede
estar vacía o
no.
Si no está
vacía, el árbol estará formado por un nodo raíz y cero o más subárboles que
están
unidos a la raíz
por otras tantas aristas.
Para que un
árbol sea binario es requisito indispensable el que el número máximo de hijos
que
tenga cada nodo
sea 2. Por lo tanto el árbol anterior no es un árbol binario, ya que el nodo A
tiene 3
hijos.
Por último, un
árbol será de búsqueda si todos sus nodos cumplen las siguientes condiciones:
• Todos los nodos
situados a su izquierda son menores que él.
• Todos los nodos
situados a su derecha son mayores que él.
Resumiendo, se
puede decir que un árbol binario de búsqueda es un árbol en el que cada nodo
tiene a lo sumo
dos hijos, y en el que para cada nodo todos los nodos a su izquierda son
menores que él
y todos los nodos a su
derecha son mayores que él.
El siguiente árbol es un ejemplo
de árbol de búsqueda:
En cambio este árbol viola la
condición de orden en el nodo 2, ya que un nodo a su derecha, 1, no es
mayor que él.
Transformación de un árbol general
en un árbol binario.
En esta sección
estableceremos los mecanismos necesarios para convertir un árbol general en un
árbol
binario. Para
esto, debemos seguir los pasos que se describen a continuación:
1. Enlazar los
hijos de cada nodo en forma horizontal (los hermanos).
2. Enlazar en
forma vertical el nodo padre con el nodo hijo que se encuentra más a la
izquierda. Además,
debe eliminarse
el vínculo de ese padre con el resto de sus hijos.
3. Rotar el
diagrama resultante aproximadamente 45 grados hacia la izquierda, y así se
obtendrá el árbol
binario
correspondiente.
OPERACIONES BÁSICAS EN ÁRBOLES
BINARIOS DE BÚSQUEDA
Como en toda
estructura de datos hay dos operaciones básicas, inserción y eliminación.
Inserción: El
procedimiento de inserción en un árbol binario de búsqueda es muy sencillo,
únicamente hay que
tener cuidado de no
romper la estructura ni el orden del árbol.
Borrar: El borrado en
árboles binarios de búsqueda es otra operación bastante sencilla excepto en un
caso.
Vamos a ir
estudiando los distintos casos.
Tras realizar la
búsqueda del nodo a eliminar observamos que el nodo no tiene hijos. Este es el
caso más
sencillo, únicamente
habrá que borrar el elemento y ya habremos concluido la operación.
Otra operación
importante en el árbol es el recorrido el mismo. El recorrido se puede realizar
de tres
formas
diferentes:
• Preorden: Primero el nodo
raíz, luego el subárbol izquierdo y a continuación el subárbol derecho.
• In orden: Primero el
subárbol izquierdo, luego la raíz y a continuación el subárbol derecho.
• Postorden:
Primero el subárbol izquierdo, luego el subárbol derecho y a continuación la
raíz.
ÁRBOLES
ETIQUETADOS
A veces es
necesario etiquetar los vértices o aristas de un dígrafo para indicar su uso
para su propósito
específico.
Esto es
particularmente cierto para muchos de los árboles es la ciencia de la
computación.
Ahora se
proporcionará un ejemplo donde el conjunto de los vértices no son importantes,
sino que la
utilidad del
árbol se enfatiza mediante las etiquetas sobre estos vértices.
Así, se
representará los vértices como puntos y se mostrará la etiqueta de cada vértice
junto al punto
que representa dicho
vértice.
GRAFOS
La teoría de grafos (también llamada teoría de las gráficas) es un
campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos (también llamadas gráficas) estructuras que
constan de dos partes, el conjunto de vértices, nodos o puntos; y
el conjunto de aristas, líneas o lados (edges en inglés) que pueden ser orientados o no.
La teoría de grafos es una rama de la matemáticas discretas y aplicadas, y es una disciplina que unifica diversas áreas
como combinatoria, álgebra,probabilidad, geometría de polígonos, aritmética y topología.
Actualmente ha tenido mayor preponderancia en el campo de la informática, las ciencias de la computación y telecomunicaciones.
El origen de la teoría de grafos se remonta al siglo XVIII con el problema
de los puentes de Königsberg, el cual consistía en encontrar un camino que recorriera los
siete puentes del río pregel (
54°42′12″N 20°30′56″E) en la ciudad de Königsberg, actualmente Kaliningrado, de modo que se recorrieran todos los puentes pasando una
sola vez por cada uno de ellos. El trabajo de Leonhard Euler sobre el problema titulado Solutio problematis ad geometriam
situs pertinentis (La solución de un problema
relativo a la geometría de la posición) en 1736, es considerado
el primer resultado de la teoría de grafos. También se considera uno de los
primeros resultados topológicos en geometría (que no depende de ninguna
medida). Este ejemplo ilustra la profunda relación entre la teoría de grafos y
la topología.
El termino «grafo»,
proviene de la expresión «graphic
notation» usada por primera
vez por Edward
Frankland y posteriormente
adoptada por Alexander Crum Brown en 1884, y hacia referencia a la representación gráfica de los enlaces entre
los átomos de una molécula.
El primer libro sobre teoria de grafos fue escrito por Dénes Kőnig y publicado en 1936.
Gracias a la teoría de grafos se pueden resolver diversos problemas como
por ejemplo la síntesis de circuitos secuenciales,
contadores o sistemas de apertura. Se utiliza para diferentes áreas por
ejemplo, Dibujo computacional, en toda las áreas de Ingeniería.
Los grafos se utilizan también para modelar trayectos como el de una
línea de autobús a través de las calles de una ciudad, en el que podemos
obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el
algoritmo de Floyd.
Para la administración de proyectos, utilizamos técnicas como PERT en las que se modelan
los mismos utilizando grafos y optimizando los tiempos para concretar los
mismos.
La teoría de grafos también ha servido de inspiración para las ciencias
sociales, en especial para desarrollar un concepto no metafórico de red social que sustituye los
nodos por los actores sociales y verifica la posición, centralidad e
importancia de cada actor dentro de la red. Esta medida permite cuantificar y
abstraer relaciones complejas, de manera que la estructura social puede
representarse gráficamente. Por ejemplo, una red social puede representar la
estructura de poder dentro de una sociedad al identificar los vínculos
(aristas), su dirección e intensidad y da idea de la manera en que el poder se
transmite y a quiénes.
TIPOS DE GRAFOS
§ Grafo
simple. o simplemente grafo es aquel
que acepta una sola una arista uniendo dos vértices cualesquiera. Esto es
equivalente a decir que una arista cualquiera es la única que une dos vértices
específicos. Es la definición estándar de un grafo.
§ Multigrafo. o pseudografo son
grafos que aceptan más de una arista entre dos vértices. Estas aristas se
llaman múltiples o lazos (loops en inglés). Los grafos
simples son una subclase de esta categoría de grafos. También se les
llama grafos no-dirigido.
§ Grafo dirigido. Son
grafos en los cuales se ha añadido una orientación a las
aristas, representada gráficamente por una flecha
§ Grafo etiquetado.
Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente)
o un etiquetado a los vértices.
§ Grafo aleatorio.
Grafo cuyas aristas están asociadas a una probabilidad.
§ Hipergrafo.
Grafos en los cuales las aristas tienen más de dos extremos, es decir, las
aristas son incidentes a 3 o más vértices.
§ Grafo infinito.
Grafos con conjunto de vértices y aristas de cardinal infinito.
REPRESENTACION DE GRAFOS
Existen
diferentes formas de representar un grafo (simple), ademas de la geométrica y
muchos métodos para almacenarlos en una computadora. La estructura de datos usada depende de las características
del grafo y el algoritmo usado para manipularlo. Entre las estructuras
más sencillas y usadas se encuentran las listas y las matrices, aunque
frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque
tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen
acceso rápido, pero pueden consumir grandes cantidades de memoria.
Estructura de lista
§ lista de incidencia -
Las aristas son representadas con un vector de
pares (ordenados, si el grafo es dirigido), donde cada par representa una de
las aristas.
§ lista de adyacencia - Cada vértice
tiene una lista de 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
de B y viceversa), pero las búsquedas son más rápidas, al costo de
almacenamiento extra.
§ lista de grados - También llamada secuencia de
grados o sucesión gráfica de un grafo no-dirigido es
una secuencia de números, que corresponde a los grados de los vértices del
grafo.
Estructuras matriciales
§ Matriz de incidencia - El grafo está
representado por una matriz de A (aristas) por V (vértices), donde
[arista, vértice] contiene la información de la arista (1 - conectado, 0 - no
conectado)
§ Matriz de adyacencia - El grafo está
representado por una matriz cuadrada M de tamaño 
, donde 
es el
número de vértices. Si hay una arista entre un vértice x y un vértice y,
entonces el elemento 
es
1, de lo contrario, es 0.
PROBLEMAS DE TEORIAS DE
GRAFOS
Ciclos y caminos
hamiltonianos
Un ciclo es
una sucesión de aristas adyacentes, donde no se recorre dos veces la misma
arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene
además que recorrer todos los vértices exactamente una vez (excepto el vértice
del que parte y al cual llega).
Por
ejemplo, en un museo grande (al estilo del Louvre), lo
idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo
hamiltoniano en el grafo que representa el museo (los vértices son las salas, y
las aristas los corredores o puertas entre ellas).
Se
habla también de camino hamiltoniano si no se impone regresar al punto de
partida, como en un museo con una única puerta de entrada. Por ejemplo, un
caballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar
dos veces por la misma: es un camino hamiltoniano. Ejemplo de un ciclo
hamiltoniano en el grafo del dodecaedro.
Grafos planos.
Cuando un grafo o multigrafo se puede dibujar en un plano sin que dos
segmentos se corten, se dice que es plano.
Un juego muy conocido es el siguiente: Se dibujan tres casas y tres
pozos. Todos los vecinos de las casas tienen el derecho de utilizar los tres
pozos. Como no se llevan bien en absoluto, no quieren cruzarse jamás. ¿Es
posible trazar los nueve caminos que juntan las tres casas con los tres pozos
sin que haya cruces?
Cualquier disposición de las casas, los pozos y los caminos implica la
presencia de al menos un cruce.
