1. Representación de grafos por matriz de incidencia. Matriz de adyacencia.
Definición 1.4.1. Dado un grafo G = (V, E) con n vértices {v1, ..., vn} su matriz de
adyacencia es la matriz de orden n×n, A(G)=(aij) donde aij es el número de aristas que
unen los vértices vi y vj.
La matriz de adyacencia de un grafo es simétrica. Si un vértice es aislado entonces la
correspondiente fila (columna) esta compuesta sólo por ceros. Si el grafo es simple
entonces la matriz de adyacencia contiene solo ceros y unos (matriz binaria) y la
diagonal esta compuesta sólo por ceros. 2. Dado un grafo simple G = (V, E) con n=|V| vértices {v1, ..., vn} y
m=|E| aristas {e1, ..., em}, su matriz de incidencia es la matriz de orden nxm,
B(G)=(bij), donde bij=1 si vi es incidente con ej y bij=0 en caso contrario.
La matriz de incidencia sólo contiene ceros y unos (matriz binaria). Como cada arista
incide exactamente en dos vértices, cada columna tiene exactamente dos unos. El
número de unos que aparece en cada fila es igual al grado del vértice correspondiente.
Una fila compuesta sólo por ceros corresponde a un vértice aislado
3. Dado un grafo dirigido o dígrafo D = (V, E) con n vértices {v1, ..., vn}
su matriz de adyacencia es la matriz de orden n×n, A(D)=(aij) donde aij es el número
de arcos que tienen a vi como extremo inicial y a vj como extremo final.
La matriz de adyacencia de un dígrafo no es simétrica. Es una matriz binaria. El número
de unos que aparecen en una fila es igual al grado de salida del correspondiente vértice
y el número de unos que aparecen en una determinada columna es igual al grado de
entrada del correspondiente vértice.
El origen de la palabra grafo es griego y su significado
etimológico es "trazar". Aparece con gran frecuencia como respuesta a
problemas de la vida cotidiana,algunos ejemplos podrían ser los siguientes:un
gráfico de una serie de tareas a realizar indicando su secuenciación (un
organigrama),grafos matem´ticos que representan las relaciones binarias,una red
de carreteras,la red de enlaces ferroviarios o aéreos o la red eléctrica de una
ciudad. En cada caso,es conveniente representar gráficamente el problema dibujando
un grafo como un conjunto de puntos(vértices)con líneas conectándolos (arcos).
De aquí se podría deducir que un grafo es básicamente un objeto geométrico
aunque en realidad sea un objeto combinatorio,es decir,un conjunto de puntos y
un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de
vértices.Por otro lado,y debido a su generalidad y a la gran diversidad de
formas que pueden usarse,resulta complejo tratar con todas las ideas
relacionadas con un grafo.
Para facilitar el estudio de este tipo de dato,a continuación se realizará un
estudio de la teoría de grafos desde el punto de vista de las ciencias de la
computación. Considerando que dicha teoría es compleja y amplia,aquí sólo se
realizará una introducción a la misma,describiéndose el grafo como un tipo de
dato y mostrándose los problemas típicos y los algoritmos que permiten
solucionarlos usando un ordenador.
Los grafos son estructuras de datos no lineales que tienen una naturaleza
generalmente dinámica. Su estudio podría dividirse en dos grandes bloques:
Grafos Dirigidos.
Grafos no Dirigidos(pueden ser considerados un caso particular de los
anteriores).
Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que
cada tubería sólo admite que el agua la recorra en un único sentido.Por el
contrario,la red de carreteras de un país representa en general un grafo no
dirigido,puesto que una misma carretera puede ser recorrida en ambos
sentidos.No obstante,podemos dar unas definiciones generales para ambos tipos.
OBJETIVO: El Objetivo de este blog, es dar a conocer la estructura manejada en los diferentes tipos de árboles, dentro de la programación estructurada y estructura de datos en C, viendo como desarrollan una secuencia de pasos lógicos para formar y administrar información o los distintos tipos en cuanto a manejo de archivos, establecer las propiedades de los grafos, sus funcionalidades, aplicaciones varias dentro de las estructuras de datos. Estructura de Datos
Las estructuras de datos es una colección de datos que se caracterizan por su organización y las operaciones que se definen en ellos; debido a su eficiencia, Las estructuras de datos son un medio para manejar grandes cantidades de datos de manera eficiente para usos tales como grandes bases de datos y servicios de indización de Internet. Por tanto una estructura de datos se caracterizará por las relaciones entre los datos que la constituyen y las operaciones posibles en ella. Esto supone que mediante un conjunto de reglas, las relaciones y operaciones posibles como insertar nuevos elementos o eliminar los ya existentes, con lo anterior se define la estructura.
Las estructuras de datos se basan generalmente en la capacidad de un ordenador para recuperar y almacenar datos en memoria.
Teoría de grafos : La Teoría de Grafos juega un papel importante en la fundamentación
matemática de las Ciencias de la Computación. Los grafos constituyen una
herramienta básica para modelar fenómenos discretos y son fundamentales para la
comprensión de las estructuras de datos y el análisis de algoritmos.
En matemáticas y ciencias de la computación, la teoría de grafos estudia
las propiedades de los grafos, que son colecciones de objetos llamados vértices (o
nodos) conectados por líneas llamadas aristas (o arcos) que pueden tener
orientación (dirección asignada). Típicamente, un grafo está diseñado por una serie
de puntos (los vértices) conectados por líneas (las aristas).
El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de
Königsberg es considerado como uno de los primeros resultados 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.
En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el
voltaje y la corriente en los circuitos eléctricos.
En 1852 Francis Guthrie planteó el problema de los cuatro colores que
plantea si es posible, utilizando solamente cuatro colores, colorear cualquier mapa
de países de tal forma que dos países vecinos nunca tengan el mismo color. Este
problema, que no fue resuelto hasta un siglo después por Kenneth Appel y
Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos.
Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos
fundamentales de los grafos. Los grafos son, como veremos, un lenguaje, una notación, que
permite representar relaciones binarias es decir, entre pares
de objetos en un conjunto (recordemos la sección 3.5).
De una manera informal, podríamos decir que un grafo es
una colección de vértices y de aristas que unen estos vértices.
Los vértices los dibujaremos como puntos del plano, y las aristas serán líneas que unen
estos puntos. Vayamos con las definiciones formales: Definición Formal: Un grafo G es un conjunto no vacío V (de vértices) y un conjunto A (de
aristas) extraído de la colección de subconjuntos de dos elementos de V. Una arista de G es,
pues, un subconjunto {a, b}, con a, b ∈ V , a = b.
En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas
no son relevantes, sólo importa a qué vértices están unidas. La posición de los
vértices tampoco importa, y se puede variar para obtener un grafo más claro.
Generalmente, se considera que colocar los vértices en forma de polígono
regular da grafos muy legibles.
Prácticamente cualquier red puede ser modelada con un grafo: una red de
carreteras que conecta ciudades, una red eléctrica o un alcantarillado.
El nombre AVL son las iniciales
de los hombres que idearon este tipo de árbol Adelson-Velskii y Landis en 1962.
Básicamente un árbol AVL es un Árbol binario de búsqueda al que se le
añade una condición de equilibrio. Esta condición es que para todo nodo la
altura de sus subárboles izquierdo y derecho pueden diferir a lo sumo en 1.
Caracteristicas:
- Un AVL es un ABB
- La diferencia entre las alturas de los subárboles derecho e izquierdo no debe
excederse en más de 1.
- Cada nodo tiene asignado un peso de acuerdo a las alturas de sus subárboles.
- Un nodo tiene un peso de 1 si su subárbol derecho es más alto, -1 si su
subárbol izquierdo es más alto y 0 si las alturas son las mismas.
- La inserción y eliminación en AVLs es la misma que en los ABBs.
Equilibrio:
Equilibrio (n) = altura-der (n) – altura-izq (n) describe
relatividad entre subárbol der y subárbol izq.
+ (positivo) -> der mas alto (profundo)
- (negativo) -> izq mas alto (profundo)
Un árbol binario es un AVL si y sólo si cada uno de
sus nodos tiene un equilibrio de –1, 0, + 1.
Si alguno de los pesos de los nodos se modifica en un valor no válido (2 o -2)
debe seguirse un esquema de rotación.
Operaciones sobre un AVL:
- Insertar
- Balancear
* Caso 1 Rotación simple izquierda RSI
* Caso 2 Rotación simple derecha RSD
* Caso 3 Rotación doble izquierda RDI
* Caso 4 Rotación doble derecha RDD
- Eliminar
- Calcular Altura
Balancear el Árbol:
Caso 1: Rotación simple izquierda RSI
Si esta desequilibrado a la izquierda y su hijo derecho tiene el mismo signo
(+) hacemos rotación sencilla izquierda.
Luego
de la rotación:
Caso
2: Rotación simple derecha RSD
Luego de la rotación:
Eliminar un Dato:
Al eliminar un nodo en un árbol AVL puede afectar el
equilibrio de sus nodos. Entonces hay que hacer rotaciones simples o dobles.
Eliminas un nodo como lo hacemos en un árbol binario ordenado. Al localizar el
nodo que queremos eliminar seguimos este procedimiento:
- Si el nodo es un nodo hoja, simplemente lo eliminamos.
- Si el nodo solo tiene un hijo, lo sustituimos con su hijo.
- Si el nodo eliminado tiene dos hijos, lo sustituimos por el hijo derecho y
colocamos el hijo izquierdo en el subárbol izquierdo del hijo derecho.
Ahora que hemos eliminado el nodo, tenemos que volver a equilibrar el árbol:
- Si el equilibrio del padre del nodo eliminado cambia de 0 a +-1 el algoritmo
concluye.
- Si el padre del nodo eliminado cambio de +-1 a 0, la altura del árbol ha
cambiado y se afecte el equilibrio de su abuelo.
- Si el equilibrio del padre del nodo eliminado cambia de +- 1 a +- 2 hay que
hacer una rotación.
- Después de concluirla, el equilibrio del padre podría cambiar, lo que, a su
vez, podría forzarnos a hacer otros cambios (y probables rotaciones) en toda la
ruta hacia arriba a medida que ascendemos hacia la raíz. Si encontramos en la
ruta un nodo que cambie de 0 a +- 1 entonces terminamos.
Los datos que hemos tratado hasta el momento han residido en
la memoria principal. Sin embargo, las grandes cantidades de datos se almacenan
normalmente en un dispositivo de memoria secundaria. Estas colecciones de datos
se conocen como archivos (antiguamente ficheros). Un archivo es un conjunto de
datos estructurados en una colección de entidades elementales o básicas
denominadas registros que son de igual tipo y constan a su vez de diferentes
entidades de nivel más bajos denominadas campos. Hay dos tipos de archivos,
archivos de texto y archivos binarios. Un archivo de texto es una secuencia de
caracteres organizadas en líneas terminadas por un carácter de nueva línea.
En
estos archivos se pueden almacenar canciones, fuentes de programas, base de
datos simples, etc. Los archivos de texto se caracterizan por ser planos, es
decir, todas las letras tienen el mismo formato y no hay palabras subrayadas,
en negrita, o letras de distinto tamaño o ancho. Un archivo binario es una
secuencia de bytes que tienen una correspondencia uno a uno con un dispositivo
externo. Así que no tendrá lugar ninguna traducción de caracteres. Además, el
número de bytes escritos (leídos) será el mismo que los encontrados en el
dispositivo externo. Ejemplos de estos archivos son Fotografías, imágenes,
texto con formatos, archivos ejecutables (aplicaciones), etc.
En c, un archivo
es un concepto lógico que puede aplicarse a muchas cosas desde archivos de
disco hasta terminales o una impresora. Se asocia una secuencia con un archivo
especifico realizando una operación de apertura. Una vez que el archivo está
abierto, la información puede ser intercambiada entre este y el programa. Se
puede conseguir la entrada y la salida de datos a un archivo a través del uso
de la biblioteca de funciones; C no tiene palabras claves que realicen las
operaciones de E/S. La siguiente tabla da un breve resumen de las funciones que
se pueden utilizar. Se debe incluir la librería STDIO.H. Observe que la mayoría
de las funciones comienzan con la letra “F”, esto es un vestigio del estándar C
de Unix.
El puntero a un archivo:
El puntero a un archivo es el hilo
común que unifica el sistema de E/S con buffer. Un puntero a un archivo es un
puntero a una información que define varias cosas sobre él, incluyendo el
nombre, el estado y la posición actual del archivo. En esencia identifica un
archivo especifico y utiliza la secuencia asociada para dirigir el
funcionamiento de las funciones de E/S con buffer. Un puntero a un archivo es
una variable de tipo puntero al tipo FILE que se define en STDIO.H. Un programa
necesita utilizar punteros a archivos para leer o escribir en los mismos. Para
obtener una variable de este tipo se utiliza una secuencia como esta: FILE *F.
Apertura de un archivo
La función fopen(): Abre una secuencia para que pueda ser
utilizada y la asocia a un archivo. Su prototipo es: FILE *fopen(const char
nombre_archivo, cost charmodo); Donde nombre_archivo es un puntero a una cadena
de caracteres que representan un nombre valido del archivo y puede incluir una
especificación del directorio. La cadena a la que apunta modo determina como se
abre el archivo. La siguiente tabla muestra los valores permitidos para modo.
Cierre de un archivo
La función fclose():Cierra una secuencia que fue abierta
mediante una llamada a fopen(). Escribe toda la información que todavía se
encuentre en el buffer en el disco y realiza un cierre formal del archivo a
nivel del sistema operativo. Un error en el cierre de una secuencia puede
generar todo tipo de problemas, incluyendo la pérdida de datos, destrucción de
archivos y posibles errores intermitentes en el programa. El prototipo de esta
función es: int fclose(FILE *F); Donde F es el puntero al archivo devuelto por
la llamada a fopen(). Si se devuelve un valor cero significa que la operación
de cierre ha tenido éxito. Generalmente, esta función solo falla cuando un
disco se ha retirado antes de tiempo o cuando no queda espacio libre en el
mismo.
Acá un ejemplo de como hacer la lectura y modificación de un archivo en C:
El código anterior realiza la apertura de una archivo de texto, y permite escribir y modificar su nombre y edad respectivamente. SI DESEA CONOCER MAS SOBRE ESTE TEMA, INGRESE A ESTE ENLACE
Los B-árboles sugieron en 1972 creados por R.Bayer y
E.McCreight.El problema original comienza con la necesidad de mantener índices
en almacenamiento externo para acceso a bases de datos,es decir,con el grave
problema de la lentitud de estos dispositivos se pretende aprovechar la gran
capacidad de almacenamiento para mantener una cantidad de información muy alta
organizada de forma que el acceso a una clave sea lo más rápido posible.
Como se ha visto anteriormente existen métodos y estructuras
de datos que permiten realizar una búsqueda dentro de un conjunto alto de datos
en un tiempo de orden O(log2n). Así tenemos el caso de los árboles
binarios AVL.¿Por qué no usarlos para organizar a través de ellos el índice de
una base de datos?la respuesta aparece si estudiamos más de cerca el problema
de acceso a memoria externa.Mientras que en memoria interna el tiempo de acceso
a n datos situados en distintas partes de la memoria es independiente
de las direcciones que estos ocupen(n*cte donde cte es el tiempo
de acceso a 1 dato),en memoria externa es fundamental el acceder a datos
situados en el mismo bloque para hacer que el tiempo de ejecución disminuya
debido a que el tiempo depende fuertemente del tiempo de acceso del dispositivo
externo,si disminuimos el número de accesos a disco lógicamente el tiempo
resultante de ejecución de nuestra búsqueda se ve fuertemente recortado.Por
consiguiente,si tratamos de construir una estructura de datos sobre disco es fundamental
tener en cuenta que uno de los factores determinantes en el tiempo de ejecución
es el número total de accesos,de forma que aunque dicho n&uacite;mero pueda
ser acotado por un orden de eficiencia es muy importante tener en cuenta el
número real ya que el tiempo para realizar un acceso es suficientemente alto
como para que dos algoritmos pese a tener un mismo orden,puedan tener en un
caso un tiempo real de ejecución aceptable y en otro inadmisible.
De esta forma,si construimos un árbol binario de búsqueda
equilibrado en disco,los accesos a disco serán para cargar en memoria uno de
los nodos,es decir,para poder llevar a memoria una cantidad de información
suficiente como para poder decidir entre dos ramas.Los árboles de múltiples
ramas tienen una altura menor que los árboles binarios pues pueden contener más
de dos hijos por nodo,además de que puede hacerse corresponder los nodos con
las páginas en disco de forma que al realizar un único acceso se leen un número
alto de datos que permiten elegir un camino de búsqueda no entre dos ramas,sino
en un número considerablemente mayor de ellas.Además,este tipo de árboles hace
más fácil y menos costoso conseguir equilibrar el árbol.
DEFINICIÓN:
Los B-árboles son árboles cuyos nodos pueden tener un número múltiple de hijos tal como muestra el esquema de uno de ellos en la figura 1.
Como se puede observar en la figura 1,un B-árbol se dice que es de orden m si sus nodos pueden contener hasta un máximo de m hijos.En la literatura también aparece que si un árbol es de orden m significa que el mínimo número de hijos que puede tener es m+1(m claves).Nosotros no la usaremos para diferenciar el caso de un número máximo par e impar de claves en un nodo.
El conjunto de claves que se sitúan en un nodo cumplen la condición:
INSERCIÓN EN UN B-ÁRBOL:
Para insertar una nueva clave usaremos un algoritmo que consiste en dos pasos recursivos:
Buscamos la hoja donde debieramos encontrar el valor de la clave de una forma totalmente paralela a la búsqueda de ésta tal como comentabamos en la sección anterior(si en esta búsqueda encontramos en algun lugar del árbol la clave a insertar,el algoritmo no debe hacer nada más).Si la clave no se encuentra en el árbol habremos llegado a una hoja que es justamente el lugar donde debemos realizar esa inserción.
Situados en un nodo donde realizar la inserción si no está completo,es decir,si el número de claves que existen es menor que el orden menos 1 del árbol,el elemento puede ser insertado y el algoritmo termina.En caso de que el nodo esté completo insertamos la clave en su posición y puesto que no caben en un único nodo dividimos en dos nuevos nodos conteniendo cada uno de ellos la mitad de las claves y tomando una de éstas para insertarla en el padre(se usará la mediana).Si el padre está también completo,habrá que repetir el proceso hasta llegar a la raíz.En caso de que la raíz esté completa,la altura del árbol aumenta en uno creando un nuevo nodo raíz con una única clave.
BORRADO EN UN B-ÁRBOL.
La idea para realizar el borrado de una clave es similar a la inserción teniendo en cuenta que ahora,en lugar de divisiones,realizamos uniones.Existe un problema añadido,las claves a borrar pueden aparecer en cualquier lugar del árbol y por consiguiente no coincide con el caso de la inserción en la que siempre comenzamos desde una hoja y propagamos hacia arriba.La solución a esto es inmediata pues cuando borramos una clave que está en un nodo interior,lo primero que realizamos es un intercambio de este valor con el inmediato sucesor en el árbol,es decir,el hijo más a la izquierda del hijo derecho de esa clave.
Las operaciones a realizar para poder llevar a cabo el borrado son por tanto:
Redistribución:la utilizaremos en el caso en que al borrar una clave el nodo se queda con un número menor que el mínimo y uno de los hermanos adyacentes tiene al menos uno más que ese mínimo,es decir,redistribuyendo podemos solucionar el problema.
Unión:la utilizaremos en el caso de que no sea posible la redistribución y por tanto sólo será posible unir los nodos junto con la clave que los separa y se encuentra en el padre.
En definitiva,el algoritmo nos queda como sigue:
Localizar el nodo donde se encuentra la clave.
.
Si el nodo localizado no es una hoja,intercambiar el valor de la clave localizada con el valor de la clave más a la izquierda del hijo a la derecha.En definitiva colocar la clave a borrar en una hoja.Hacemos nodo actual igual a esa hoja.
Borrar la clave.
Si el nodo actual contiene al menos el mínimo de claves como para seguir siendo un B-árbol,fin.
Si el nodo actual tiene un número menor que el mínimo:
Si un hermano tiene más del mínimo de claves,redistribución y fin.
Si ninguno de los hermanos tiene más del mínimo,unión de dos nodos junto con la clave del padre y vuelta al paso 4 para propagar el borrado de dicha clave(ahora en el padre).
