Grafos

REPRESENTACION DE GRAFOS
Orlando Arboleda Molina
Escuela de Ingenier´ıa de Sistemas y Computaci´on de
La Universidad del Valle
8 de septiembre de 2008

Contenido
Representaci´on de grafos
Matrices de adyacencia
Matrices de incidencia

Representaci´on de grafos
Los grafos sin aristas m´ ultiples pueden ser representados de la
siguiente manera:
Listando todas las aristas de su grafo.

Usando listas de adyacencia (especifica v´ ertices que son
adyacentes).

Usando matrices.

Matrices de adyacencia
Suponga que G = (V,E) es un grafo simple donde | V |= n.
Suponga que los v´ ertices de G son listados arbitrariamente
como v1, v2, ...., vn. la matriz de adyacencia A (o AG) de G, con
respecto a su lista de v´ ertices es la matriz nxn talque:
aij = ½ 1 si {vi , vj} es una arista de G
0 en caso contrario
Nota: esta matriz es sim´ etrica.

Matrices de adyacencia (2)
Ejercicio: Dibujar el grafo representado por la siguiente matriz
de adyacencia. Donde los v´ ertices han sido ordenados como
a, b, c, d. 2664
0 1 1 1
1 0 1 0
1 1 0 0
1 0 0 0
3775

Matrices de incidencia
Suponga que G = (V,E) es un grafo no dirigido. Suponga que
los v´ ertices de G son listados arbitrariamente como
v1, v2, ...., vn y las aristas como e1, e2, ...., em, la matriz de
incidencia, con respecto a su lista de v´ertices y aristas, es la
matriz nxm talque:
mij = ½ 1 si la arista ej es incidente con vi
0 en caso contrario
Nota1: esta matriz no es sim´ etrica.
Nota2: tambi´en pueden ser utilizadas para representar aristas
multiples

Matrices de incidencia (2)
Ejercicio: Dibujar el grafo representado por la siguiente matriz
de incidencia. Donde los v´ ertices han sido ordenados como
v1, v2, v3, v4. 2664
0 1 1 0
1 0 1 1
0 1 0 0
0 0 0 1
3775

Codigo java grafos

BUSQUEDA ANCHURA
struct tcola *cola;

void visitar(int k) // listas de adyacencia
{
struct nodo *t;
encolar(&cola,k);
while (!vacia(cola))
{
desencolar(&cola,&k);
val[k]=++id;
for (t=a[k]; t!=z; t=t->sig)
{
if (val[t->v]==0)
{
encolar(&cola,t->v);
val[t->v]=-1;
}
}
}
}


BUSQUEDA DE PROFUNDIDAD

int id=0;
int val[V];

void buscar()
{
int k;
for (k=1; k<=V; k++)
val[k]=0;
for (k=1; k<=V; k++)
if (val[k]==0) visitar(k);
}

void visitar(int k) // matriz de adyacencia
{
int t;
val[k]=++id;
for (t=1; t<=V; t++)
if (a[k][t] && val[t]==0) visitar(t);
}

void visitar(int k) // listas de adyacencia
{
struct nodo *t;
val[k]=++id;
for (t=a[k]; t!=z; t=t->sig)
if (val[t->v]==0) visitar(t->v);
}


* Implementacion basada en una lista de nodos de los que cuelga */
/* la lista de arcos de salida. */



typedef char *tetq;
typedef float tvalor;

typedef struct arco {
struct nodo *origen;
struct nodo *destino;
tvalor valor;
struct arco *sig;
} *tarco;

typedef struct nodo {
int nodo;
tetq etiq;
tarco ady;
tarco inc;
struct nodo *sig;
} *tnodo;

typedef tnodo tgrafo;



LISTAS DE ADYACENCIA
struct nodo
{
int v;
int p;
nodo *sig;
};

int V,A; // vértices y aristas del grafo
struct nodo *a[maxV], *z;

void inicializar()
{
int i,x,y,peso;
char v1,v2;
struct nodo *t;
z=(struct nodo *)malloc(sizeof(struct nodo));
z->sig=z;
for (i=0; i a[i]=z;
for (i=0; i {
scanf("%c %c %d\n",&v1,&v2,&peso);
x=v1-'A'; y=v2-'A';

t=(struct nodo *)malloc(sizeof(struct nodo));
t->v=y; t->p=peso; t->sig=a[x]; a[x]=t;

t=(struct nodo *)malloc(sizeof(struct nodo));
t->v=x; t->p=peso; t->sig=a[y]; a[y]=t;
}
}

METODO DE BUSQUEDA HASHING

Hash: se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc., resumir o identificar un dato a través de la probabilidad, utilizando una función hash o algoritmo hash. Un hash es el resultado de dicha función o algoritmo.

FUNCION HASH

Es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor. Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada

VENTAJAS:
Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar
Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones
No se requiere almacenamiento adicional para los índices.

DESVENTAJAS:

El archivo no esta clasificado
No permite llaves repetidas
Solo permite acceso por una sola llave
Costos
Tiempo de procesamiento requerido para la aplicación de la función hash

ALGORITMO HASHING

Algoritmo que se utiliza para generar un valor de hash para algún dato, como por ejemplo claves. Un algoritmo de hash hace que los cambios que se produzcan en los datos de entrada provoquen cambios en los bits del hash. Gracias a esto, los hash permiten detectar si un dato ha sido modificado.

ALGORITMOS DE HASH MAS COMUNES

SHA-1: algoritmo de hash seguro Algoritmo de síntesis que genera un hash de 160 bits. Se utiliza, por ejemplo, como algoritmo para la firma digital.
MD2 y MD4 Algoritmos de hash que generan un valor de 128 bits.
MD5 Esquema de hash de hash de 128 bits muy utilizado para autenticación cifrada. Gracias al MD5 se consigue, por ejemplo, que un usuario demuestre que conoce una contraseña sin necesidad de enviar la contraseña a través de la red.

FUNCIONES DE HASH

Residuo de la división
Medio del cuadrado
Pliegue
RESIDUO DE LA DIVISIÓN
La idea de este método es la de dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para el registro (dirección = llave módulo divisor).       Mientras que el valor calculado real de una dirección relativa, dados tanto un valor de llave como el divisor, es directo; la elección del divisor apropiado puede no ser tan simple. Existen varios factores que deben considerarse para seleccionar el divisor:
RESIDUO DE LA DIVISIÓN

El rango de valores que resultan de la operación "llave % divisor", va desde cero hasta el divisor 1. Luego, el divisor determina el tamaño del espacio de direcciones relativas. Si se sabe que el archivo va a contener por lo menos n registros, entonces tendremos que hacer que divisor > n, suponiendo que solamente un registro puede ser almacenado en una dirección relativa dada.
El divisor deberá seleccionarse de tal forma que la probabilidad de colisión sea minimizada. ¿Como escoger este numero? Mediante investigaciones se ha demostrado que los divisores que son números pares tienden a comportase pobremente, especialmente con los conjuntos de valores de llave que son predominantemente impares. Algunas investigaciones sugieren que el divisor deberá ser un numero primo. Sin embargo, otras sugieren que los divisores no primos trabajan también como los divisores primos, siempre y cuando los divisores no primos no contengan ningún factor primo menor de 20. Lo mas común es elegir el número primo mas próximo al total de direcciones.
RESIDUO DE LA DIVISIÓN

Ejemplo:       
Numero de direcciones 996. La eleccion de m sera 997, que es el primo mas cercano. Se aplica esta función hash cuyo número es:
245643
h(245643) = 245643 mod 997 = 381
MEDIO DEL CUADRADO

En esta técnica, la llave es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir la dirección relativa. Si se desea una dirección de n dígitos, entonces los dígitos se truncan en ambos extremos de la llave elevada al cuadrado, tomando n dígitos intermedios. Las mismas posiciones de n dígitos deben extraerse para cada llave.
MEDIO DEL CUADRADO

Ejemplo:      

Utilizando esta función hashing el tamaño del archivo resultante es de 10n donde n es el numero de dígitos extraídos de los valores de la llave elevada al cuadrado.
POR PLIEGUE

En esta técnica el valor de la llave es particionada en varias partes, cada una de las cuales (excepto la ultima) tiene el mismo numero de dígitos que tiene la dirección relativa objetivo. Estas particiones son después plegadas una sobre otra y sumadas. El resultado, es la dirección relativa. Igual que para el método del medio del cuadrado, el tamaño del espacio de direcciones relativas es una potencia de 10.

COMPARACIÓN ENTRE LAS FUNCIONES HASH

Aunque alguna otra técnica pueda desempeñarse mejor en situaciones particulares, la técnica del residuo de la división proporciona el mejor desempeño. Ninguna función hash se desempeña siempre mejor que las otras. El método del medio del cuadrado puede aplicarse en archivos con factores de cargas bastantes bajas para dar generalmente un buen desempeño. El método de pliegues puede ser la técnica mas fácil de calcular pero produce resultados bastante erráticos, a menos que la longitud de la llave se aproximadamente igual a la longitud de la dirección.

Tablas hash

Una tabla hash o mapa hash es una estructura de datos que asocia llaves o claves con valores. La operación principal que soporta de manera eficiente es la búsqueda: permite el acceso a los elementos (teléfono y dirección, por ejemplo) almacenados a partir de una clave generada (usando el nombre o número de cuenta, por ejemplo). Funciona transformando la clave con una funcion hashen un hash, un número que la tabla hash utiliza para localizar el valor deseado.

OPERACIONES BÁSICAS

Inserción(llave, valor) búsqueda(llave) que devuelve valor La mayoría de las implementaciones también incluyen borrar(llave). También se pueden ofrecer funciones como iteración en la tabla, crecimiento y vaciado. Algunas tablas hash permiten almacenar múltiples valores bajo la misma clave.
Para usar una tabla hash se necesita:
Una estructura de acceso directo (normalmente un array).
Una estructura de datos con una clave
Una función resumen(hash) cuyo dominio sea el espacio de claves y su imagen (o rango) los números naturales

INSERSION

Para almacenar un elemento en la tabla hash se ha de convertir su clave a un número. Esto se consigue aplicando la función resumen a la clave del elemento.
El resultado de la función resumen ha de mapearse al espacio de direcciones del array que se emplea como soporte, lo cual se consigue con la función modulo. Tras este paso se obtiene un índice válido para la tabla.
El elemento se almacena en la posición de la tabla obtenido en el paso anterior.

BUSQUEDA

Para recuperar los datos, es necesario únicamente conocer la clave del elemento, a la cual se le aplica la función resumen.
El valor obtenido se mapea al espacio de direcciones de la tabla.
Si el elemento existente en la posición indicada en el paso anterior tiene la misma clave que la empleada en la búsqueda, entonces es el deseado. Si la clave es distinta, se ha de buscar el elemento según la técnica empleada para resolver el problema de las colisiones al almacenar el elemento.

HASHING ABIERTO


Suposición de hashing uniforme: es cuando cualquier elemento es igualmente probable de caer en cualquiera de las m entradas de la tabla hash, independientemente de cualquier otro elemento.
Desde un “gran” Universo sólo un número reducido de claves serán consideradas.

HASHING CERRADO

En Hashing cerrado, todos los elementos o claves son almacenadas en la tabla hashing misma. Es decir, cada entrada de la tabla contiene un elemento del conjunto dinámico o NULL.
Grafo múltiple: Es un grafo que contiene alguna
arista paralela.
􀂾 Digrafo acíclico: Es un digrafo que no contiene
circuitos. Se le conoce con las siglas dag.
􀂾 Grafo o digrafo con peso: Es un grafo o digrafo
que tiene un valor entero o real asignado a cada
arista.
􀂾 Grafo completo: Es un grafo no dirigido donde
cada par de nodos es adyacente

CODIGO IMPLEMENTACION

package ejemplos;

public class matrices {
public static void main( String args[] ) {

int matriz[][] = new int[3][];
matriz[0] = new int[2];
matriz[1] = new int[3];
matriz[2] = new int[4];


for ( int i=0; i < 3; i++ ) {
for ( int j=0; j < matriz[i].length; j++ )
matriz[i][j] = i * j;
}


for ( int i=0; i < 3; i++ ) {
for ( int j=0; j < matriz[i].length; j++ )
System.out.print( matriz[i][j] );
System.out.println();
}


System.out.println( "Elemento fuera de limites del array" );
matriz[4][0] = 7;

}
}

GRAFOS NO DIRIJIDOS


Grafo no dirigido (GND): G = {N, L, f}

Funciones de dispersion

Funciones de Dispersión

Consiste en la elección de una clave, para el buen funcionamiento de la estructura, debe cumplir las siguientes características:
• Ser una función sencilla y por tanto rápida.
• Distribuir uniformemente los elementos en el espacio de almacenamiento
• Evitar en lo posible la aparición de sinónimos
• Para dos claves muy similares, generar posiciones distantes.


En primer lugar, obtenemos un numero a partir de la clave alfanumérica utilizada y luego hacemos la operación modulo N sobre ese numero. Así obtendremos una posición donde almacenar nuestro elemento. Hay que cuenta que N (el tamaño de la tabla) ha de ser un número primo.
El código seria: prívate static int Hash1(String Clave)
{ int valor = Clave.charAt(0); int tam = Clave.length(); for (int i = 1; i < tam ;i++) { valor += Character.getNumericValue( Clave.charAt(i)); } return (valor % N); }


Método de la División


Es la función de dispersión clásica para claves enteras.

Consiste en tomar el resto de la división de la clave por el número de entradas de la tabla (B).

Código: x = x % B;

Como ventajas citar que es una función fácil de calcular y que se puede utilizar para tablas de cualquier tamaño, aunque se recomienda elegir B con cuidado.

Como inconvenientes podemos citar que el rango de valores es limitado.


Suma de ASCII


Es la función de dispersión clásica para claves de tipo cadena. Consiste en sumar los valores ASCII de la clave.

Ejemplo: “HOLA” => (‘H’+’O’+’L’+’A’) % B
§
Codigo:
for (int i=0; i
x = (x + clave.charAt(i)) % B;
}
Como ventajas citar que es una función fácil de implementar y que se ejecuta con rapidez.
Como inconvenientes podemos citar que no distribuye bien las claves si el tamaño de la tabla es grande, ya que las claves se van a situar en la
parte superior de la tabla.

Ordenacion x Shell Shotr

Es una mejora del método de inserción directa que se utiliza cuando el número de elementos a ordenar es grande. El método se denomina “shell” –en honor de su inventor Donald shell – y también método de inserción con incrementos decrecientes.
En el método de clasificación por inserción, cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es más pequeño.


Pedirle a un ordenador que haga algo intuitivamente es, de momento, bastante complicado, así que sustituiremos la intuición por un procedimiento mecánico más o menos ingenioso.Veamos el siguiente arreglo


74, 14, 21, 44, 38, 97, 11, 78, 65, 88, 30


Shell nos propone que hagamos sobre el arreglo una serie de ordenaciones basadas en la inserción directa, pero dividiendo el arreglo original en varios sub-arreglo tales que cada elemento esté separado k elementos del anterior (a esta separación a menudo se le llama salto o gap)... Se debe empezar con k=n/2, siendo n el número de elementos de arreglo, y utilizando siempre la división entera.... después iremos variando k haciéndolo más pequeño mediante sucesivas divisiones por 2, hasta llegar a k=1.
Pero vamos a ello... En nuestro ejemplo, n=11 (porque hay 11 elementos). Así que k=n/2=11/2=5


Empezamos con k=5. Así pues, vamos a dividir nuestro arreglo original en 5 sub-arreglo, en los cuales, sus elementos estarán separados por 5 lugares del arreglo original (el salto o gap es 5).
Vamos a hacerlo con colores. Tomamos el primer elemento (el 74) contamos 5 lugares y tomamos también otro elemento (el 97) volvemos a contar 5 y tomamos otro (el 30) y acabamos porque se nos acaba el arreglo.
El primer sub-arreglo con k=5 es el formado por 74, 97 y 30. Vamos a pintarlos en rojo


74, 14, 21, 44, 38, 97, 11, 78, 65, 88, 30


Ahora, ordenaremos los elementos del sub-arreglo rojo pero sólo entre ellos, utilizando el algoritmo de Inserción directa.

30, 14, 21, 44, 38, 74, 11, 78, 65, 88, 97

Fíjate qué curioso. El 30, un elemento relativamente pequeño se ha ido hacia el principio y el 97 hacia el final... ¡pero dando saltos (gap) de 5 en 5 lugares! Cada uno ha avanzado en saltos de 5 hacia una posición cercana a su ubicación definitiva.


Formemos ahora otro sub-arreglo con salto k=5... partiendo del segundo elemento (el 14) y contando 5 (tomamos también el 11) y ya está, porque se acaba el arreglo.

30, 14, 21, 44, 38, 74, 11, 78, 65, 88, 97


Vamos a ordenarlos entre ellos con Inserción directa... el 11 primero y el 14 después.

30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97


Ahora a por otro... el 21 y el 78


30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97

Están en orden entre ellos, así que se quedan como están.


Ahora le toca al sub-arreglo formado por el 44 y el 65

30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97

Que también están en orden entre ellos... y finalmente el 38 y el 88, que también están en orden.

30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97


Hemos formado 5 sub-arreglos en los cuales los elementos están separados por 5 lugares (porque k=5). Hemos ordenado cada sub-arreglo por separado utilizando inserción directa, y hemos logrado que cada elemento se dirija hacia su ubicación definitiva en pasos de 5 lugares.Por supuesto, no hemos terminado todavía, pero resulta evidente que algunos elementos, como el 30, el 97 o el 11 han dado un gran salto y que no deben andar muy lejos de su sitio final.


Decimos ahora que el arreglo está 5-ordenado.
Para continuar con el algoritmo, debemos ir reduciendo progresivamente k dividiéndolo sucesivamente por 2 y k-ordenando los sub-arreglos que nos salgan (recuerda que nos salen k sub-arreglo). Cuando lleguemos a k=1 habremos terminado.
Pero de momento, nuestra k valía 5, así que ahora k←k/2=5/2=2
Nuestra nueva k vale 2. Repetimos todo el tinglado, pero ahora nos saldrán 2 sub-arreglo cuyos elementos están separados por 2 lugares.


El primero (en marrón) y el segundo (en verde):
30, 11, 21, 44, 38, 74, 14, 78, 65, 88, 97


Ordenamos por un lado los marrones entre ellos y los verdes entre ellos... es decir, 2-ordenamos el arreglo (curiosamente, los verdes ya están ordenados.... probablemente ha contribuido a ello la 5-ordenación que ya hemos hecho. En ese caso, la ordenación ha requerido muy poco esfuerzo)

14, 11, 21, 44, 30, 74, 38, 78, 65, 88, 97


Ahora, cada número está mucho más cerca de su posición definitiva... El arreglo está 2-ordenado... pero sigue también 5-ordenado. No hemos perdido el trabajo que hicimos cuando k era 5.

Finalmente, calculamos un nuevo k dividiendo el que tenemos entre 2. k←k/2=2/2=1
Hemos llegado a k=1. Cuando k es 1 sólo podemos obtener 1 sub-arreglo cuyos elementos están separados 1 posición: el propio arreglo original. Dicho de otra manera... cuando k es 1, el algoritmo de Shell se comporta exactamente igual que el de inserción directa sobre todo el arreglo.


Sin embargo, las k-ordenaciones que hemos hecho (con k=5 y k=2) han hecho que cada elemento se aproximase con saltos de 5 y luego de 2 posiciones hacia su ubicación definitiva. Ahora que k=1 y que vamos a aplicar el algoritmo de inserción directa tal cual, haremos muchas menos comparaciones e intercambios que si lo hubiéramos aplicado con en arreglo tal como lo teníamos al empezar. El algoritmo de inserción directa se comporta tanto mejor cuanto más cerca está cada elemento de su sitio definitivo.
Finalmente, el arreglo queda de ésta manera:
11, 14, 21, 30, 38, 44, 65, 74, 78, 88, 97
Cada elemento descolocado ha tenido que moverse pocos lugares. Muchos de ellos ni siquiera se han movido.

Ordenacion x Insercion Binaria

ORDENACION POR INSERCION
Este método se basa en considerar una parte de lista ordenada y situar cada uno de los elementos insertándolo en el lugar que le corresponda por su valor, todos los valores a la derecha se desplazan una posición para dejar espacio.


EJEMPLO


Este método esta basado en la técnica utilizada por los jugadores de cartas para clasificar sus cartas. El jugador va colocando (insertando) cada carta en su posición correcta:

2 8 10 tres cartas

2 8 9 10 cuatro cartas



ALGORITMO DE INSERCION

( para cada elemento de la lista después del primero ) desde k 2 hasta n hacer:

Guardar el valor de este elemento A(k) en una variable Aux.

Hacer espacio para Aux desplazando todos los valores mayores que dicho valor A(k) una posición.

Insertar el valor de Aux en el lugar del ultimo valor desplazado.


ORDENACION POR INSERCION

La operación de desplazamiento se realiza con un procedimiento Desplazar, Que mueve todos los elementos de la lista mayores que Aux, comenzando con el elemento de la lista de posición Aux-1. Si Aux es el valor mas pequeño, la operación de desplazamiento termina cuando un valor menor o igual a Aux se alcanza. Aux se inserta en la posición que ocupaba el ultimo valor que se desplazo.


ALGORITMO DE DESPLAZAMIENTO

Mientras el primer elemento no se desplaza y valor del elemento > Aux hacer:

Desplazar elemento una posición.

Comprobar valor del siguiente elemento.

Definir NuevaPos como posición original del ultimo elemento desplazado.


METODO DE INSERCIÒN BINARIA

El análisis de la ordenación por inserción es un poco mas complicado. El numero de comparaciones en i-èsimo paso es como k-1 y como mínimo 1. por consiguiente proporciona el numero de comparaciones.


METODO DE INSERCIÒN BINARIA

1. Hallamos el elemento central del área comprendida por la parte ordenada más la posición del elemento a insertar.

2 3 5 6 7 4

2. Comparamos el elemento central con el elemento que queremos insertar. Si dicho elemento central es menor o igual, nos quedamos con la parte derecha (Sin incluir el elemento central). En caso contrario, nos quedamos con la parte
izquierda incluyendo al elemento central.

2..

2 3 5 4

3..

Repetimos el mismo proceso sobre el área con la que nos quedamos, hasta que dicha área se nula.

5 4


4..

Cuando el área sea nula, tendremos la posición de inserción.


2 3 4 5 6 7

GRAFOS



GRAFOS

Las estructura de datos no lineales se caracterizan por no
existir una relación de adyacencia, entre sus elementos, es
decir, un elemento puede estar relacionado con cero, uno o
más elementos.
􀂾 Entre las múltiples aplicaciones que tienen estas estructuras
podemos mencionar:
􀂙 Los grafos son estructuras que se utilizan para modelar diversas
situaciones tales como: sistemas de aeropuertos, flujo de tráfico,...
􀂙 Los grafos también son utilizados para realizar planificaciones de
actividades, tareas del computador, planificar operaciones en
lenguaje de máquinas para minimizar tiempo de

DEFINICION

Un grafo G (N, A, f) es un conjunto no vacío de:
􀂙 N={n1, n2, ... , nM) nodos o vértices,
􀂙 A={a1, a2, ..., a K} aristas y
􀂙 la función f : R → Μ × Μ que indica los pares de nodos que están
relacionados.
􀂾 Hay dos tipos de grafos, los dirigidos o digrafos y los no
dirigidos, según que sus relaciones tengan dirección o no,
respectivamente.
􀂾 La representación gráfica de un grafo se define con un
círculo o rectángulo para los nodos y las relaciones con
líneas o flechas según sea un grafo no dirigido o un digrafo,
respectivamente

EJEMPLO
Digrafo, donde D = {N, A, f} tiene
N = {1, 2, 3, 4},
A = {a, b, c, d, e, g, h} y
f(a) = (1, 2), f(b) = (2, 3), f(c) = (1, 3), f(d) = (3, 4),
f(e) = (1, 4), f(g) = (4, 2), f(h) = (4, 1).

CONCEPTOS BASICOS

Se dice que el aj ∈ A asociado al par de nodos ( ni , nj ) donde ni , nj ∈ N,
comienza en ni y termina en nj. Así, ni es el nodo inicial y nj es el nodo
terminal. Ejemplo: si ni = 1, nj = 2 y aj = a en el digrafo D, entonces 1 es
el nodo inicial de a y 2 es el nodo terminal de a.
􀂾 Arco incidente: aj es un arco incidente sobre nk , si nk es el nodo
terminal de aj. Ejemplo: a es el arco incidente sobre 2, pero no sobre 1.
􀂾 Arcos adyacentes: ai y aj son arcos adyacentes si ai y aj son incidentes en
el mismo nodo. Ejemplo: c y b son arcos adyacentes, pero c y d no lo
son.
􀂾 Arcos paralelos: Dos arcos son paralelos si ellos comienzan y terminan
en los mismos nodos. Ejemplo: En D no hay arcos paralelos. Si anexamos
a D el arco p cuya f(p) = (1, 2), entonces a y p son arcos paralelos.

Camino: Un camino C del digrafo D es una secuencia de
arcos (a1, a2, ..., an) tal que para todo par (ai, aj) de arcos
consecutivos en C, el fin de ai coincide con el inicio de aj.
Ejemplo: b, d es un camino, pero a, c no lo es.
􀂾 Camino simple: Es el camino que no recorre el mismo
arco dos veces. Ejemplo: b, d, g es un camino simple, pero
b, d, g, b no es un camino simple.
􀂾 Camino elemental: Es el camino que no visita un mismo
nodo más de una vez. Ejemplo: b, d es un camino
elemental, pero b, d, g no lo es.

Quicksort

Quicksort el ordenamiento rápido
El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna.

Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.
es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos).
Fue desarrollada por C. Antony R. Hoare en 1960.

Descripción del algoritmo

Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

La idea central de este algoritmo consiste en los siguiente: Se toma un elemento x de una posición cualquiera del arreglo. Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x. Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo.

Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido

Algoritmo en Java:
void ordenarQuicksort(int[] vector, int primero, int ultimo){
int i=primero, j=ultimo;
int pivote=vector[(primero+ultimo)/2];
int auxiliar;
do{
while(vector[i]pivote) j--;
If (i<=j){ auxiliar=vector[j];
vector[j]=vector[i];
vector[i]=auxiliar; i++; j--;
}
}
while (i<=j);
if(primeroif(ultimo>i) ordenarQuicksort(vector,i, ultimo);
}
Analisis del algoritmo:
Estabilidad: No es estable.
Requerimientos de Memoria: No requiere memoria adicional en su forma recursiva. En su forma iterativa la necesita para la pila.

Ventajas:
Muy rápido.
No requiere memoria adicional.
Desventajas:
Implementación un poco más complicada.
Recursividad (utiliza muchos recursos).
Mucha diferencia entre el peor y el mejor caso.

Analisis del algoritmo:

Diversos estudios realizados sobre el comportamiento del mismo demuestran que si se escoge en cada pasada el elemento que ocupa la posición central del conjunto de datos a analizar, el número de pasadas necesarias para ordenar es del orden de Log n. Respecto al número de comparaciones, si el tamaño del arreglo es una potencia de 2, en la primera pasada realizará (n-1) comparaciones, en la 2ª pasada realizará (n-1)/2 comparaciones, pero en 2 conjuntos diferentes, en la tercera pasada realizará (n-1)/4 comparaciones pero en 4 conjuntos diferentes y así sucesivamente. Por lo tanto: C = (n-1) + 2(n -1)/2 + 4(n - 1)/4 + ....... + (n - 1)(n - 1)/(n - 1) Lo cual es lo mismo que: C= (n - 1) + (n- 1) + ....... + (n - 1)

EJEMPLO

El elemento divisor será el 6:
5 - 3 - 7 - 6 - 2 - 1 - 4
p
Comparamos con el 5 por la izquierda y el 4 por la derecha con el pivote.
5 - 3 - 7 - 6 - 2 - 1 - 4
i p j
5 es menor que 6 y 4 NO es mayor que 6. Avanzamos la i, y la j queda donde está.
 
5 - 3 - 7 - 6 - 2 - 1 - 4
i p j
3 es menor que 6 y 4 NO es mayor que 6. Avanzamos la i, y la j queda donde está.
 
5 - 3 - 7 - 6 - 2 - 1 - 4
i p j
7 NO es menor que 6 y 4 NO es mayor que 6.
 
5 - 3 - 7 - 6 - 2 - 1 - 4
i p j
Como i=2 y j=6, i es menor que j, así que intercambiamos los valores de a[i] y de a[j].
5 - 3 - 4 - 6 - 2 - 1 - 7
Como i sigue siendo menor que j, se vuelve a aplicar el mismo algoritmo hasta que se crucen los índices i y j, siendo este momento cuando se vuelve a llamar al método quicksort con la parte del array que es menor que el pivote y, por otro lado, con la parte que es mayor. (Sólo se muestra a continuación una parte, ya que es igual su ejecución en ambas):
1 - 3 - 2
1 es menor que 3: avanzamos por la izquierda. 2 NO es mayor: no avanzamos por la derecha. Como i no es menor que el pivote, se para, y como i es menor que j, se intercambian a[i] y a[j], resultando ya ordenador este subarray:
1 - 2 - 3
El mismo procedimiento se aplicará al otro subarray. Al finalizar y unir todos los subarrays queda el array inicial ordenado en forma ascendente.
1 - 2 - 3 - 4 - 5 - 6 - 7

Heapsort

Heapsort

El ordenamiento por montículos Heap sort es un algoritmo de ordenación no recursivo, no estable.
Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado
Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.


DESCRIPCION

operaciones insertar_en_monticulo y extraer_cima_del_monticulo
function heapsort(array A[0..n]):
montículo M
integer i := 124578
for i = 0..n:
insertar_en_monticulo(M, A[i])
for i = 0..n:
A[i] = extraer_cima_del_monticulo(M)
return A

MATRICEZ

Dos estructuras de datos fundamentales son las conocidas
como: matriz (o array) y registro (o estructura).

Son de uso frecuente, por lo que son elementos
imprescindibles en la programación de muchos problemas.

Por ejemplo, las notas correspondientes a las distintas
evaluaciones realizadas a cada uno de los alumnos de un
determinado curso forman una matriz, y la ficha que contiene
los datos personales de cada uno de estos alumnos es un
ejemplo de registro (o estructura).
Matrices
Una matriz (array en inglés) es un conjunto de elementos
contiguos, todos del mismo tipo, que comparten un nombre
común y a los que es posible acceder mediante la posición
(índice) que ocupa cada uno de ellos en la matriz, como un
vector o una matriz en Álgebra.

Esta disposición permitirá escribir código más simple, ya que
será posible establecer bucles en los que se recorra los
elementos de una matriz mediante el número de índice.

A las matrices de una dimensión se les suele llamar también
vectores o listas, y a las matrices de dos dimensiones, tablas.
La representación de las matrices se hace mediante
variables con subíndices. Los subíndices son números
enteros consecutivos y, por defecto, el primer índice valdrá
0.

Una matriz de dos dimensiones se representa con una
variable con dos subíndices (filas, columnas). Una de tres
con tres, etcétera.

Para formar el nombre de una matriz y definir su tipo, se
siguen las mismas reglas que para las variables:

Dim a(24) As Integer ´matriz de enteros, 1 dimensiones.
Dim c(12,5) As String ´matriz de cadenas, 2 dimensiones.

Declaración de matrices
La declaración de una matriz especifica el nombre de la
matriz, el número de elementos de la misma y el tipo de éstos:

donde:
• variable es el nombre de la matriz.
• dimension es una lista de expresiones numéricas, separadas por comas y que definen las dimensiones de la matriz. Esta lista puede ser de la forma:

[inferior To] superior [, ...

• tipo define el tipo de la variable (Integer, Long, String, etc.)

Ejemplos de declaración de matrices
Lista o vector de 60 enteros, indexados del 0 al 59:
Dim temp(59) As Integer
Lista o vector de 60 enteros, indexados del 1 al 60:
Dim temp(1 To 60) As Integer
Lista o vector de 60 cadenas de caracteres de longitud fija 40:
Dim temp(1 To 60) As String * 40
Tabla de 10 * 10 elementos de tipo Double:
Dim a(9,9) As Double
Dim a(1 To 10, 1 To 10) As Double
Dim a(-5 To 4, 2001 To 2010) As Double


Ejemplo de manipulación de matrices

Const n = 12
Dim A(1 to n) As Double ´matriz de n elementos
Dim i As Integer

´Bucle For para Rellenar la matriz “a” con datos.
For i = 1 To n
A(i) = InputBox(“Introduce el elemento” & i & “ de A”)
Next i

´Bucle For para Visualizar la matriz con Print
For i = 1 To n
MsgBox A(i)
Next i
Matrices dinámicas

Una matriz dinámica, a diferencia de las anteriores, puede ser
redimensionada en cualquier momento de la ejecución del programa.

Para crear una matriz dinámica, primero hay que declararla como si
fuera una matriz estática (con Dim), pero sin darle dimensión.

Para reasignar dinámicamente el número de elementos se utiliza la
sentencia ReDim. No es posible cambiar el número de dimensiones
de la misma, sólo los tamaños de cada dimensión.

Cada vez que se ejecuta ReDim, todos los valores previamente
almacenados se pierden.

Para cambiar el tamaño conservando los valores hay que utilizar la
palabra clave Preserve, en cuyo caso no es posible cambiar el/los
índice/s inferior/es, sólo el superior.


Ejemplo de manipulación de matrices dinámicas
Dim m() As Double 'declaracion de matriz dinamica
Dim filas As Integer, columnas As Integer
Dim i As Integer, j As Integer

'consulto al usuario el tamaño de la matriz
filas = InputBox("Nº filas de la matriz:")
columnas = InputBox("Nº columnas de la matriz:")
ReDim m(1 To filas, 1 To columnas) 'redimensiono la matriz
'Leo los datos
For i = 1 To filas
For j = 1 To columnas
m(i, j) = InputBox("m(" & i & ", " & j & ") = ")
Next j
Next i