PDF de programación - Algoritmos básicos de Grafos

Imágen de pdf Algoritmos básicos de Grafos

Algoritmos básicos de Grafosgráfica de visualizaciones

Actualizado el 5 de Mayo del 2019 (Publicado el 21 de Marzo del 2018)
533 visualizaciones desde el 21 de Marzo del 2018
110,0 KB
26 paginas
Creado hace 16a (20/05/2003)
Universidad Central de Venezuela

Facultad de Ciencias

Escuela de Computación



Lecturas en Ciencias de la Computación

ISSN 1316-6239

Algoritmos Básicos de Grafos



Ernesto Coto

ND 2003-02













Laboratorio de Computación Gráfica

Febrero, 2003























Algoritmos Básicos de Grafos

Universidad Central de Venezuela. Facultad de Ciencias. Escuela de Computación.

Laboratorio de Computación Gráfica (LCG)



Los grafos son solo abstracciones matemáticas, pero son útiles en la práctica porque
nos ayudan a resolver numerosos problemas importantes. Estas notas describen algunos de
los algoritmos y métodos más conocidos para resolver problemas de procesamiento de
grafos, así como proponen alternativas para la representación de los mismos en el
computador. Cada algoritmo o método está acompañado de figuras que ilustran su
funcionamiento y de una breve descripción teórica que incluye el estudio de la complejidad
en
taxonomía de
clasificación de problemas de procesamiento de grafos, basada en el grado de dificultad de
lo mismos.


tiempo del mismo. En adición se

la descripción de una

incluye

Estas notas abarcan desde problemas simples como el de recorrido de grafos, hasta
problemas más complejos como los de flujo en redes. Es recomendable que el lector tenga
conocimientos básicos de estructuras de datos dinámicas y de teoría de grafos.



Palabras Claves: Grafos. Algoritmia. Algoritmos de Grafos. Procesamiento de Grafos.
Estructuras de Datos para Grafos.




Febrero, 2003













Ernesto Coto

ecoto@strix.ciens.ucv.ve
ecoto@opalo.ciens.ucv.ve

Venezuela. Caracas

Apdo. 47002, 1041-A.

ND 2003-02

Resumen








CONTENIDO

1.

2.

3.

4.

5.

CONCEPTOS BASICOS

REPRESENTACION EN EL COMPUTADOR

PROBLEMAS DE PROCESAMIENTO DE GRAFOS

RECORRIDO DE GRAFOS

CALCULO DEL CAMINO MAS CORTO

6. ORDENAMIENTO TOPOLOGICO

7.

8.

CAMINOS DE EULER

ARBOL DE EXPANSION MINIMA

9. GRAFOS BIPARTITOS, CICLOS IMPARES Y COLORACIÓN

10.

11.

12.

COMPONENTES FUERTEMENTE CONEXAS

TOUR HAMILTONIANO Y TSP

FLUJO EN REDES

13.

BIBLIOGRAFIA

4

4

6

9

13

15

17

18

21

22

23

23

26



1. CONCEPTOS BASICOS


Hablando intuitivamente, un grafo es un conjunto de nodos unidos por un conjunto
de líneas o flechas. Por lo general, los nodos son entes de procesamiento o estructuras que
contienen algún tipo de información y las líneas o flechas son conexiones o relaciones entre
estos entes. Si se utilizan flechas para conectar los nodos decimos que el grafo es dirigido
(también llamado digrafo) porque las relaciones entre los nodos tienen una dirección. En
caso contrario el grafo es no dirigido. En cualquiera de los dos casos, bien sea que se
utilicen líneas o flechas, a estas relaciones se les puede llamar simplemente aristas.
Frecuentemente las aristas también tienen algún tipo de información asociada (distancia,
costo, confiabilidad, etc.), en cuyo caso estamos en presencia de un grafo pesado.


Las secuencias de aristas forman caminos o ciclos. Un ciclo es un camino que
termina en el mismo nodo donde comenzó. Si el camino recorre todos los nodos del grafo
es llamado tour. El número de aristas en un camino es la longitud del camino.


Se dice que un grafo es conexo si se puede llegar desde cualquier nodo hasta
cualquier otro mediante un camino. De lo contrario no es conexo, pero puede dividirse en
componentes conexas, que son subconjuntos de nodos y aristas del grafo original que si son
conexos. Un grafo conexo sin ciclos es llamado un árbol.


Estos son apenas unos cuantos conceptos de lo que se conoce como la Teoría de
Grafos. El objetivo de estas notas no es cubrir por completo dicha teoría sino enfocarnos en
la implementación de este tipo de estructuras y las operaciones y algoritmos más comunes e
importantes que se aplican sobre las mismas.

2. REPRESENTACION EN EL COMPUTADOR


Hay por lo menos dos maneras evidentes de representar un grafo en un computador,
utilizando la notación pseudoformal propuesta en [2]. La primera utiliza lo que se conoce
como una matriz de adyacencia, a saber:



Arreglo de <Tipo> Nodos de [1..N];
Arreglo de logico MatrizDeAdyacencia de [1..N][1..N];

CLASE Grafo
Privado:





Publico:



FCLASE

Un valor verdadero en la posición (i,j) de la matriz indica que hay una arista que
conecta al nodo i con el nodo j. Para representar un grafo pesado se puede cambiar la matriz
de adyacencia de lógicos a una matriz de registros, siendo el peso un campo del registro.

# Todas las operaciones aquí


Esta representación es muy útil cuando se cumplen dos condiciones principales.
Primero, si se conoce el número exacto de nodos en el grafo no hace falta utilizar
estructuras dinámicas porque las estáticas se pueden acceder con mayor facilidad. Segundo,
la matriz de adyacencia no contiene un gran número de elementos en FALSO.



4

Si no se cumple la primera de estas condiciones y el número de nodos en el grafo
puede variar drásticamente entonces se justifica el uso de estructuras dinámicas. En este
caso, lo ideal es utilizar una lista lineal de nodos conteniendo la información en <Tipo>.
Por supuesto, si el número de nodos va a cambiar entonces tampoco se justificas tener un
matriz estáticas, por lo que debería utilizarse una matriz esparcida.

CLASE Nodo




#Nodo de la lista de <Tipo>



Publico:
entero Id;
<Tipo> Info;
› Nodo proximo;

#Operaciones aquí

FCLASE

#La declaración de los nodos para las columnas (NodoC), filas (NodoF) y
#nodos internos de la matriz van aquí. Son las declaraciones de una
#matriz esparcida implementada con listas con posición lógica fija o
#relativa.

CLASE Grafo






FCLASE

Sin embargo, puede que esta solución no sea la más conveniente por el hecho de
que la matriz esparcida ocupará más memoria que su contraparte estática a medida que el
número de conexiones entre los nodos sea mayor, ya que habrá pocos elementos no nulos
dentro de la matriz. En ese caso, se debe utilizar otra implementación.

Privado:
› Nodo
primerNodo;
› NodoF primeraFila;
› NodoC primeraColumna; # 1era. columna de la matriz esparcida
Publico:
# Todas las operaciones aquí

# 1er. nodo de la lista
# 1era. fila de la matriz esparcida



#Nodo de la lista de <Tipo>



CLASE Nodo




Publico:
entero Id;
<Tipo> Info;
› Nodo proximo;
› Ady ListaDeAdyacentes;

#Operaciones aquí



#Nodo de la lista de nodos adyacentes

› Nodo AdyAeste;
› Ady proximo;
#Operaciones aquí

FCLASE

CLASE Ady




Publico:



FCLASE

CLASE Grafo




Privado:

Publico:

› Nodo primerNodo;

# 1er. nodo de la lista



5

# Todas las operaciones aquí



FCLASE


Esta representación ocupa menos memoria que la anterior sin importar si la matriz
esparcida esta muy llena o no, pero puede incrementar la complejidad de algunas
operaciones, como por ejemplo saber cuales nodos son adyacentes a un nodo en particular
(en caso de un grafo dirigido).


De nuevo, si las aristas también tienen algún tipo de información asociada bastaría

una leve modificación en la clase Ady estructura para agregarla.


Por supuesto, se deben implementar las operaciones más comunes como agregar un

nodo al grafo, eliminar un nodo del grafo y conectar un nodo con otro. En adición, se puede
implementar todo tipo de operaciones basadas en la teoría de grafos, para resolver los
problemas que se describen a continuación.

3. PROBLEMAS DE PROCESAMIENTO DE GRAFOS


Los algoritmos que se tratan en este texto son fundamentales y son muy útiles en
muchas aplicaciones, pero solamente son una introducción al tema de algoritmos de grafos.
Existe un gran variedad de problemas relacionados con grafos y una gran variedad de
algoritmos para procesamiento de grafos, pero claramente no todo problema de grafos es
sencillo de resolver y en muchas ocasiones tampoco es sencillo determinar que tan difícil
puede ser resolverlo.


En [5] podemos encontrar un categorización de problemas de grafos de acuerdo al

grado de dificultad para resolverlos, a saber:











Fáciles: Un problema fácil de procesamiento de grafos es aquel que se puede
resolver utilizando un programa eficiente y elegante. Frecuentemente su tiempo
de ejecución es lineal en el peor caso, o limitado por un polinomio de bajo grado
en el número de nodos o el número de aristas.

Generalmente, también podemos decir que el problema es fácil si podemos
desarrollar un algoritmos de fuerza bruta que aunque sea lento para grandes
grafos, es útil para grafos pequeños e inclusive de tamaño medio. Entonces, una
vez que sabemos que el problema es fácil, buscamos soluciones eficientes y
escogemos la mejor de ellas.

Tratable: Un problema tratable de procesamiento de grafos es aquel para el que
se conoce un algoritmo que garantiza que sus requerimientos en tiempo y
espacio están limitados por una función polinomial en el tamaño del grafo
(número de nodos + número de aristas).

Todo problema fácil es
  • Links de descarga
http://lwp-l.com/pdf9749

Comentarios de: Algoritmos básicos de Grafos (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad