Teoría de Grafos

Un grafo es un conjunto de nodos o vértices (V) y un conjunto de aristas (E), donde cada arista relaciona a un par de nodos pertenecientes a V.
La estructura algebraica para los grafos es G=(V,E).

Ejemplo de grafos:

Existen diferente tipos de grafos:

Grafo Dirigido:

Un grafo dirigido (G) consiste de un conjunto V de vértices y un conjunto E al conjunto de aristas del grafo a su vez los vértices de un grafo dirigido pueden usarse para representar objetos y los enlaces relaciones entre los objetos, ejemplo de ello que los vértices pueden representar ciudades y los enlaces vuelos aéreos entre ciudades también un enlace es un par ordenado de
vértices (v, w), donde v es la cola y w corresponde a la cabeza del enlace.

Ejemplo:

Grafo no Dirigido:

Sea G un Grafo no Dirigido, donde G=(V,E) y V corresponde al conjunto de vértices y E al conjunto de aristas del grafo.
Un Grafo no Dirigido se diferencia de un Grafo Dirigido debido a que cada arista en E es un par no ordenado de vértices. Si (v,w) es una arista no dirigida (v,w) = (w,v).

Ejemplo:

Costos:

Los enlaces tanto para los grafos Dirigidos como No Dirigidos tienen un costo (valor), por lo tanto son grafos etiquetados.

Ejemplo:

Representación de los grafos

Un grafo Dirigido o No-Dirigido se puede representar mediante:

Matriz de Adyacencia:

La Matriz Adyacente A de un Grafo G=(V,E) tiene V*V elementos y se define como:

Ejemplo:

VENTAJA:
Se puede determinar en un tiempo fijo y constante si un enlace(arco) pertenece o no al grafo.

DESVENTAJAS:
Se requiere un almacenamiento |v|*|v|. Es decir O(n2).

Lista de Adyacencia:

La lista de adyacencia para un vértice v es una lista enlazada de todos los vértices w adyacentes a v. Un grafo puede ser representado por |v| listas de adyacencias, una para cada vértice.

Ejemplo:

VENTAJAS:
La lista de adyacencia requiere un espacio proporcional a la suma del número de vértices más el número de enlaces(arcos). Hace buen uso de la memoria.

DESVENTAJAS:
La representación con lista de adyacencia es que puede llevar un tiempo O(n) determinar si existe un arco del vértice i al vértice j, ya que pueden haber O(n) vértices en la lista de adyacencia. Para el vértice i.

Arreglos para la Lista de Adyacencia:

Se utilizan los arreglos para implementar la Lista de Adyacencia.

Complejidad Computacional

Algoritmos de Búsqueda

Los algoritmos de búsqueda son aquellos destinados a ubicar un valor determinado dentro de un conjunto de datos, como por ejemplo un número dentro de un vector.

Búsqueda Secuencial (lineal): Se utiliza en vectores no ordenados. El dato que se requiere buscar, se va comparando uno por uno (secuencialmente) con los contenidos en el vector hasta encontrarlo, o en caso contrario, recorrerlo por completo.

Se tiene que en un vector con «n» elementos:
Mejor caso: 1 comparación.
Caso promedio: n/2 comparaciones.
Peor caso: n comparaciones.

Búsqueda Binaria: Se utiliza sólamente cuando el vector está ordenado. Para ello, se selecciona un elemento cualquiera del vector, preferentemete central, y se compara con el elemento a buscar; si el valor tomado es mayor, se continúa realizando el procedimiento por la sección a la izquierda de éste ignorando la otra parte; si es menor se procede con la sección a la derecha hasta encontrar el valor o, en el peor de los casos, no encontrarlo.

Se tiene que en un vector con «n» elementos:
Mejor caso: 1 comparación.
Caso promedio: 1/2 log₂n comparaciones.
Peor caso: log₂n comparaciones.

Búsqueda Hash: Se utiliza en elementos que se encuentren ordenados. A cada elemento se le asigna un índice, generalmente en un arreglo (array), que son obtenidos mediante la transformación de estos elementos en un número, mediante las funciones de Hashing (transformación de claves). Entre ellas:

– Plegamiento: Se divide la clave en partes iguales (con excepción de la última que puede ser menor) y se aplica una operación aritmética sobre ellos para determinar el índice dentro del arreglo. Por ejemplo, si un número de 7 cifras se debe ordenar en un arreglo de 1000 elementos, se divide en cifras de 2, 2 y 3 y luego se suman para obtener el índice:

5700931 »> 57 + 00 + 931 »> 988

– Truncamiento: Considera sólo una parte de la clave y la toma como índice dentro del vector, ingorando el resto. Por ejemplo, si un número de 7 cifras se debe ordenar en un arreglo de 1000 elementos, se pueden tomar el segundo, el cuarto y el sexto para formar un nuevo número:

5700931 »> 703

– Aritmética Modular: Se toma la clave y se divide por el largo del vector, obteniendo el resto de esa operación para utilizarla como índice.

– Mitad del Cuadrado: Se calcula el cuadrado del número y luego se utilizan las cifras centrales de aquel cálculo para determinar el índice dentro del arreglo. Por ejemplo, para un arreglo de 100 elementos:

5793 »> 33558849 »> 58

Algoritmos de Ordenamiento

Los algoritmos de ordenamiento, como su nombre lo indica, son aquellos destinados al ordenamiento de los elementos de un vector, según a lo solicitado mediante las intrucciones del algoritmo utilizado y que comúnmente corresponden a un orden numérico o lexicográfico.

Ordenamiento Búrbuja (Bubblesort): Toma un valor del vector que se quiere ordenar y se compara con el siguiente, y en caso de que no estén ordenados, prosigue realizando comparaciones hasta que ese valor quede como se solicita. Continuará así hasta que el último elemento del vector quede ordenado.
Su orden de complejidad es de O(n²).

Ordenamiento de Búrbuja Bidireccional (Cocktail sort): Al igual que el método búrbuja, la forma de realizar las comparaciones es la misma, pero en éste las comprobaciones se realizan de ida y vuelta, ordenando los valores en ambos extremos del vector hasta que quede organizados de la manera solicitada. Realiza menos comparaciones que el metodo búrbuja, pero su orden de complejidad es el mismo: O(n²).

Ordenamiento por Selección (Selection Sort): Recorre el vector realizando comparaciones hasta encontrar el valor mínimo y lo intercambia con el valor de la primera posición, para luego proseguir con el siguiente mínimo para la segunda posición hasta ordenar el vector por completo.
Su orden de complejidad es de O(n²).

Ordenamiento por Inserción (Insertion sort): Se inicia con un elemento en un vector y uno por uno se van incorporando más valores que se comparan con los elementos ya ordenados. Todos los valores mayores se desplazan una posición a la derecha cada vez que el valor ingresado sea menor o cuando éste llegue al comienzo del vector.
Su orden de complejidad es de O(n²).

Ordenamiento por Mezcla (Merge sort): Se divide la lista de valores en 2 sublistas, por la mitad idealmente (éstas a la vez pueden subdividirse en listas mas pequeñas) y luego se ordenan. Con las sublistas ordenadas, ambas se mezclan y se comparan para crear una sola lista con todos los valores ordenada.
Su orden de complejidad es de O(n log n).

Ordenamiento rápido (Quicksort): Se basa en tomar un valor de la lista, llamado pivote, y ordenar el resto de los valores a ambos lados de él, si son mayores a la derecha y si son menores a la izquierda, creando dos sublistas. Luego continúa con el mismo procedimiento en las sublistas hasta que todo quede ordenado.
Su orden de complejidad es de O(n log n).

Heapsort:
Shellsort:

Algoritmos: Definición

El algoritmo (del matemático persa Al-Juarismi) es una secuencia de tareas definidas y finitas, realizadas en orden una tras otra para dar la solución a un problema dado. Hay diferentes formas para representar un algoritmo, ya sea mediante los diferentes tipos de lenguajes de programación y pseudocódigo o mediante diagramas de flujo.
Como bien se mencionó, debe ser una secuencia de intrucciones definidas y finitas, pero además, debe de ser preciso para que la solución satisfaga las necesidades del usuario.

A continuación se detallarán los algoritmos más comúnmente conocidos agrupados en algortimos de ordenamiento y algoritmos de búsqueda, detallando el cómo funcionan y las diferencias que puedan existir de uno con otro.