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