APLICACIONES DE GRAFOS

Objetivo:

Mostrar la aplicación de la teoría de grafos dentro de los márgenes de diseño en la vida real y los diferentes programas utilizados, ya sea en estructuras de comunicación, y dirigidos a la ejecución de programas.

1. Generalidades

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 todas 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.

LISTAS Y MATRICES

Lista de adyacencia

En esta estructura de datos la idea es asociar a cada vertice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sóllo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vertices 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. 

Matriz de adyacencia

Se trata de una matriz cuadrada de n filas *n columnas (siendo n el número de vértices del grafo).

Para construir la matriz de adyacencia, cada elemento a ij vale {{1}} cuando haya una arista que una los vértices i y j En caso contrario el elemento a ij vale 0.

La matriz de adyacencia, por tanto, estará formada por ceros y unos.

Una lista de adyacencia invertida almacena para cada vértice la lista de adjuntos
desde otros vértices.

Con la estructura de puede calcular el grado de entrada de cualquier vértice
solamente contando el numero de nodos de la lista del vértice requerido.

CARACTERIZACIÓN DE GRAFOS

Grafos Simples Un grafo es simple si a lo más sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es el único que une dos vértices específicos. Un grafo que no es simple se denomina complejo. 

Grafos Conexos Un grafo es conexo (más formalmente fuertemente conexo) si todos sus vértices están conectados por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b. Es posible determinar si un grafo es fuertemente conexo coleccionando la información de los grados de sus vértices al tiempo que se acumulan las diferentes rutas que salen de un vértice o llegan a él. En términos matemáticos la propiedad de un grafo de ser fuertemente conexo permite establecer en base a él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes fuertemente conexos", es decir, porciones del grafo, que son fuertemente conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos. 

Grafos Completos Un grafo simple 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 Bipartitos Un grafo G es bipartito si puede expresarse como G = {V1 + V2, A} (es decir, la unión de dos grupos de vértices), bajo las siguientes condiciones: 

• V1 y V2 son distintos y tienen más de un elemento cada uno. 

• Una arista en A une un vértice de V1 con uno de V2. 

• No existen aristas uniendo dos elementos de V1; análogamente para V2.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzzles en los que debe unirse un elemento de la columna A con un elemento de la columna B. 

Cibergrafia :

http://campus.cva.itesm.mx/nazira/Tc1003/PDF/TODO/0701_Tc1003_TODO_Grafos.pdf

GRAFOS ISOMORFOS

Se dirá que dos grafos G y G' son isomorfos entre sí, si: 

1. Existe una función biyectiva .
2. Si dos vértices vi, vj son adyacentes en V(G), es decir, viRvj, entonces las correspondientes imágenes de dichos vértices también son adyacentes pero en V(G'), dicho de otra forma,; y viceversa.

Ejemplo: En la siguiente figura, tenemos que G es isomorfo a G'.

Donde V(G) = {1,2,3,4} y V(G') = {A,B,C,D} y como debe cumplirse quef:V(G)  V(G') es una biyección, entonces f(1) = D, f(2) = B, f(3) = C, f(4) = A. Observar que 1R4 en G, entonces, D R A en G'.

Tenemos otra función que también define un isomorfismo entre G y G'.

f(1) = B, f(2) = D, f(3) = C y f(4) = A.

Observar, igualmente, que para este caso 1 R 4 en G, entonces, B R A en G'.

La relación de isomorfismo preserva las vecindades de cada vértice.

La relación de isomorfismo de dos grafos G y G' se denota de la siguiente manera, 

Corolario: Si , entonces:

/V(G) /= /V(G')/

/E(G) /= /E(G') /

Si tiene vi tiene "k" vértices vecinos vi1, vi2, vi3, ... , vik, entonces, f(vi) tiene los siguientes "k" vértices vecinos f(vi1), f(vi2), f(vi3), ... , f(vik).

vi y f(vi) tienen la misma valencia.

Cibergrafía:

http://teoriadegrafos.blogspot.com.co/2007/03/isomorfismo-de-grafos.html

GRAFOS EULERIANOS Y HAMILTONIANOS

Existen todavía algunas familias de grafos que se derivan del concepto de grafos conexos. Este es el caso de los grafos eulerianos y los grafos hamiltonianos. Estas familias de grafos nos permiten resolver el famoso problema de los puentes de Königsberg:

¿cuándo es posible hacer un recorrido de una figura (en este caso de un grafo múltiple) sin pasar dos veces por la misma línea o por el mismo vértice?

Tenemos dos grafos G1 y G2; es posible recorrer uno de ellos sin repetir ninguna línea, pero el otro no. ¿Cuál es cuál? Es evidente que el grafo G1 no puede ser recorrido sin repetir alguna de sus líneas, mientras que el grafo G2 sí.       

                           

Grafos Eulerianos

Recorrido cerrado

Cubre todas las líneas de un grafo, comenzando y terminando en un mismo vértice, recorriendo sin repetición y en forma continua todas las líneas de un grafo G cualquiera. Cuando tal recorrido existe, se denomina eulerianoy un grafo que se puede trazar mediante un recorrido euleriano se llamagrafo euleriano. En la fig. 3.11, G1 es obviamente un grafo euleriano; G2 no lo es, a pesar de que se puede trazar continuamente, ya que el recorrido comienza y termina en vértices distintos; finalmente, G3 no es un grafo euleriano, porque no se puede trazar continuamente.

                                

Diremos que un grafo G es la unión disjunta de ciclos, si podemos descomponer a G como la unión de ciclos que no tienen líneas en común, aunque se permite que tengan, al menos, un vértice en común.

En la figura el grafo se puede descomponer como la unión disjunta de los ciclos C = v1v2v3v4v5v6v1; C' = v1v7v5v1; C'' = v2v7v4v2; C''' = v3v8v9v3 y el recorrido euleriano para el grafo G viene dado por la secuencia de sus líneas 1, 2,..., 15.

OBSERVACION : Esta descomposición por lo general no es única. El grafo de la fig. 3.11 admite otra descomposición como unión disjunta de ciclos, por ejemplo, C = v1v2v7v1; C' = v3v4v2v3; C'' = v3v8v9v3; C''' = v7v4v5v7; C'''' = v5v1v6v5 .

Recíprocamente, supongamos que G es una unión disjunta de ciclos. Sea C un ciclo cualquiera en G. Si entonces G es un ciclo y por lo tanto euleriano. Si existe un ciclo C' en G que tiene un vértice v en común con C (por hipótesis). Si G es la unión de C y C', entonces, comenzando en v trazamos C y luego C', obteniendo así un recorrido euleriano de G. Si la unión de C y C' no es todo G, existe un ciclo C'' que tiene algún vértice v' en común con C o con C', digamos por ejemplo con C'. Si G es la unión de C, C' y C'', entonces comenzando en v trazamos C, luego trazamos C' hasta llegar a v' y luego trazamos C'' hasta completar C', luego regresamos a v como ilustra el diagrama de la fig. 3.13.

Así, obtenemos un recorrido euleriano de G. Si la unión de C, C' y C'' no es todo G, continuamos con este procedimiento hasta obtener un recorrido euleriano de G.

COROLARIO 2: Un grafo conexo es euleriano si y sólo si todos sus vértices tienen valencia par. (Este teorema rige también para multigrafos).

Demostración:

En un recorrido euleriano, cuando visitamos un vértice, necesitamos al menos dos líneas distintas adyacentes al vértice (una para llegar al vértice y otra para salir de él), incluyendo al vértice inicial, porque tenemos que regresar a él para concluir el recorrido. Esto significa, que cada vértice contribuye con un número par de líneas y, por lo tanto, su valencia es par.

Grafos Hamiltonianos

Definición: Un circuito o ciclo hamiltoniano es un ciclo simple que contiene todos los vértices de G. Un circuito hamiltoniano es una trayectoria que empieza y termina en el mismo vértice y pasa por cada vértice una sola vez. 

Ejemplos: ¿Cuál de los grafos siguientes admite un circuito hamiltoniano? 

Solución 

(a) No admite circuitos hamiltonianos. El razonamiento es el siguiente: Si se empieza en v1, v2, v3, v4 y si se está en los demás vértices, en el v5 se estará dos veces. Si se empieza en v5, para luego ir a los vértices v1 o v4 ó a v3 o v2 respectivamente, se tendrá que pasar de nuevo por v5 (puesto que se empezará en v5). Para completar el circuito, se debe regresar a v5, por lo que se pasa tres veces por él.

(b) Un ciclo hamiltoniano es: v1 e1 v2 e2 v3 e3 v4 e4 v1 Teorema. Sea G un grafo conexo con n vértices, donde n≥3. 

Si la suma de los grados de cada par de vértices no adyacentes es mayor o igual a n, entonces G tiene un circuito hamiltoniano. 

Cibergrafia:

http://campus.cva.itesm.mx/nazira/Tc1003/PDF/TODO/0702_Tc1003_TODO_Euler_Hamilton.pdf

http://teoriadegrafos.blogspot.com.co/2007/03/grafos-eulerianos-y-hamiltonianos.html

CICLOS Y CIRCUITOS DE GRAFOS

Ciclo, es una cadena simple, cuyos dos vértices extremos, inicial y terminal, coinciden (no tiene en cuenta la orientación). Si queremos describir la orientación en un ciclo designamos como: u+ = {ui : ui orientada en el sentido del ciclo} u- = {ui : ui orientada en el sentido contrario al ciclo} 

Ciclo elemental, es un ciclo donde no se repite ningún vértice (salvo el primero que coincide con el último). Lo notamos uE = (u1,...,un). 

Propiedad 1: Todo ciclo uC es una suma de ciclos elementales sin aristas comunes. 

Propiedad 2: Un ciclo es elemental si y solo si es un ciclo minimal (es decir que no se pueden deducir otros ciclos por supresión de aristas).

Seudociclo, es una cadena donde los extremos coinciden pero que una misma arista puede figurar más de una vez (también consecutivamente). 

Cociclo del conjunto de vértices A, es el conjunto de aristas incidentes a A, del tipo I(A) no vacío y particionado en dos clases I+(A) y I-(A). 

Ciclo Euleriano es aquel que incluye todas las aristas del grafo una sola vez, conteniendo cada vértice por lo menos una vez. 

Cadena Euleriana, es aquella que recorre todas las aristas una sola vez ( = simple) tocando todos los vértices del grafo. 

Todo multigrafo que posee un ciclo Euleriano es conexo y todos sus vértices tienen grado par . 

A partir del siguiente ejemplo daremos una idea del mecanismo utilizado por Euler para demostrar que la conexidad y el grado par de todos los vértices de un multigrafo, son condiciones necesarias y suficientes para garantizar la existencia de un ciclo Euleriano. Tenemos este grafo que es conexo y sus vértices tienen grado par.

1) Primero se comienza por trazar un camino simple desde un vértice, p. ej a. Supongamos que recorremos a-d-j-n-o-k-l-h-f-e-b-a. Volvimos a a.

La propiedad del grado par, significa que siempre podemos abandonar cada vértice al que entramos, exepto a. Es decir que cualquier cadena que trazemos desde a debe volver a a, formando un ciclo.

2) Las restantes aristas del grafo inicial , conforman un grafo no conexo, pero todos sus vértices mantienen el grado par, ya que al retirar el ciclo encontrado, se redujo cada grado en una cantidad par . Cada subgrafo conexo posee un ciclo Euleriano: d-c-i-j-k-e-d y h-g-m-h

. 3) Estos dos ciclos pueden ser insertados en el ciclo encontrado en 2) en los vértices comunes d y h respectivamente, originando un ciclo Euleriano a-d-c-i-j-k-e-d-j-n-o-kl-h-g-m-h-f-e-b-a, en el grafo original.

Cibegrafía:

https://www.fing.edu.uy/inco/grupos/bioinf/bioinfo1/teorico/grafos.pdf

CLASIFICACIÓN DE LOS GRAFOS

Multigrafo: Es un grafo no orientado con múltiples aristas entre pares de nodos.

Grafo simple: Es un grafo sin bucles, sin múltiples aristas entre pares de vértices.

Grafo completo Para todo par de vértices de G, existe por lo menos una arista que los une. Por lo tanto, un grafo completo de n vértices es aquel que tiene sus n vértices mutuamente adyacentes. n-clique, es un grafo completo simple de n vértices. Se nota Kn.

Subgrafo de G = (X,U) engendrado por el conjunto A ⊂ X, es un grafo cuyos vértices pertenecen al conjunto A y cuyas aristas son aquellas de G que tienen las dos extremidades en A. 

Grafo parcial de G = (X,U) engendrado por V ⊂ U, es el grafo G' = (X,V) cuyos vértices son los mismos de G y cuyas aristas son las que conforman el conjunto V ⊂ U. 

Subgrafo parcial de G, es un subgrafo de un grafo parcial de G

Grafo bipartito: Es un grafo cuyo conjunto de vértices puede ser particionado en dos clases X1 y X2 de tal forma que dos vértices de la misma clase no sean jamás adyacentes. Se nota G = (X1,X2,U)

Grafo bipartito completo, es aquel en el que para todo elemento de X1 y todo elemento de X2 existe por lo menos un arco que los liga.

Un grafo simple bipartito completo con p elementos en X1 y q elementos en X2 se nota Kp,q.

Grafo Regular: es aquel en el que todos sus vértices tienen el mismo grado.

Grafo Ponderado G = (X, U, W) donde (X, U,) es un grafo y W es una función W: U → Z+ (Z+: enteros positivos) . Si u ∈ U, w(u) es llamado el peso de la arista u. Estos pesos corresponden, según la aplicación, a costos, capacidades u otras propiedades de las aristas o arcos. Cuando se desea asignar valores negativos o reales a los pesos de las aristas, se debe tener especial cuidado en la elección de los algoritmos ya que la correctitud de los mismos puede depender de la restricción a Z+.

Grafo Conexo: es aquel en el que para cada par de vértices de G, existe una cadena que los une. En grafos orientados se definen 2 conceptos:

1.  Débilmente conexo: si existe una cadena (sin tener en cuenta la orientación) que une cada par de nodos distintos. 
2.  Fuertemente conexo: si para cada par ordenado de nodos x e y, existe un camino que va de x a y. 

Una componente conexa de un grafo G, es un subgrafo de G engendrado por los vértices que pueden unirse a un vértice xi dado, mediante una cadena (puede ser todo el grafo G).

Cibergrafía:

https://www.fing.edu.uy/inco/grupos/bioinf/bioinfo1/teorico/grafos.pdf

REPRESENTACIÓN DE LOS GRAFOS

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.

Cibergrafía:

http://docencia.udea.edu.co/regionalizacion/teoriaderedes/informaci%F3n/C1_RepresentacionMatrices.pdf 

HISTORIA DE LA TEORIA DE GRAFOS

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.

Cibergrafia

http://teoriagrafosgerson.blogspot.com.co/2008/08/historia-de-la-teoria-de-grafos.html

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.

¿QUÉ ES UN GRAFO?

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. 

Cibergrafía:

https://www.uam.es/personal_pdi/ciencias/gallardo/capitulo8a.pdf

http://campus.cva.itesm.mx/nazira/Tc1003/PDF/TODO/0701_Tc1003_TODO_Grafos.pdf

ARBOLES AVL

ARBOLES AVL 

¿Qué Son? 

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.

MANEJO DE ARCHIVOS

Manejo de Archivos en C:

¿Qué Son? 

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 

ÁRBOLES B

¿Qué Son?

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:

1. 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.
2. 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:

1. 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.
2. 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:

1. Localizar el nodo donde se encuentra la clave.
.
2. 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.
3. Borrar la clave.
4. Si el nodo actual contiene al menos el mínimo de claves como para seguir siendo un B-árbol,fin.
5. Si el nodo actual tiene un número menor que el mínimo:
1. Si un hermano tiene más del mínimo de claves,redistribución y fin.
2. 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).