Sistemas numéricos

Índice


Unidad 6.- Teoría de Grafos






Elementos y características de los grafos


Representación de los grafos


Algoritmos de recorrido y búsqueda


Aplicaciones de grafos


Árboles


Redes


TEORIA DE GRAFOS

CONCEPTO.

La teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos(también llamadas gráficas). Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas, que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Los grafos son una herramienta básica aplicable en muchos campos de la ciencia y de latecnología. Son áreas de aplicación: la Inteligencia artificial, la Economía, la Física, la Teoría de autómatas, la Telecomunicación, la Biología, la Teoría de juegos, la Teoría de conjuntos, etc.



Definiremos grafo G como una estructura formada por:

a) Un conjunto V de elementos, V= {v1, v2, v3,…, vn} , en el que cada vk se denomina vértice o nodo.

b) Un conjunto A de parejasaij = (vi, vj), tal que vi, vj € V, que se llaman arcos.



El grafo puede denotarse como: G (V, A).

G=Grafo

V=Vértice

A=Arista

[pic]

Representación de un grafo con 6 vértices y 7 aristas.




La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y lasmatrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.
Estructura de lista
• Lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo esdirigido), donde cada par representa una de las aristas.
• Lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.
Ejemplo de Lista de Adyacencia.


[pic] Estructurasmatriciales.
• Matriz de incidencia - El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (1 - conectado, 0 - no conectado)
• Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño n2, donde n es el número de vértices. Si hay una arista entre un vértice x y un vértice y, entonces elelemento mx,y es 1, de lo contrario, es 0.
Subgrafo.
Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H (dependiendo de las necesidades de la situación).
El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristasadyacentes al subconjunto de vértices de G.
Definición:
Sea G= (V, A). G’= (V’, A’) se dice subgrafo de G si:
1- V’ [pic]V
2- A' [pic]A
3- (V’, A’) es un grafo
• Si G’=(V’,A’) es subgrafo de G, para todo v [pic]G se cumple gr (G’,v)≤ gr (G, v)
G2 es un subgrafo de G.
[pic]
Hipergrafos
Una estructura de hipergrafos es un par ordenado G:=(H, K) de dos hipergrafos H y K, bajo el mismoconjunto base.
El tamaño o volumen de una estructura está dada por |A|·(|H|+|K|).
Ejemplo
Sea A: = {a,b,c}, entonces G: = (H,K), con H: = {{a,b},{b,c},{c}} y K: = {{a,c},{b,c},{a,b,c}} es una estructura de hipergrafos, de tamaño 18.

Grados
Se define grado de entrada de un vértice como el numero de arcos que en el acaban, y grado de salida de un vértice por el numero de arcos que en el...