Ejercicios "amistosos"
Grafos
Un grafo es una estructura de datos
no lineal que se utiliza para representar relaciones arbitrarias, no
jerárquicas, entre los elementos de un conjunto.
Consideremos las ciudades Ibagué, Bogotá, Medellín, como elementos
de un conjunto y las rutas aéreas como las relaciones existentes entre
ellas. En éste caso, las relaciones no son jerárquicas, pues es posible
que de Ibagué se pueda ir a Bogotá, de Bogotá a Medellín y de Medellín
a Ibagué.
Si se hace una reseña histórica acerca de grafos, encontramos que EULER
fue el primero en hablar del tema (año 1736), como parte de la solución
del famoso problema de los puentes de Koenigsberg:
'Por la ciudad prusiana de Koenigsberg pasa el rio Pregel, que al pasar
la ciudad tiene dos islas que están unidas a las dos riberas y entre sí
por siete puentes. La gente que pasa por los puentes se ha preguntado si
saliendo de la casa es posible dar un paseo por los 7 puentes, de tal
manera que pasee por cada puente una y sólo una vez, y se regrese al
punto de partida'. Euler trató de resolver este problema y llegó
a la
conclusión de que no es posible encontrar dicha ruta, debido a que a cada
parte, isla o ribera, le llega un número impar de puentes, previo
modelamiento del problema mediante un grafo, reemplazando las islas y
riberas por puntos y los 7 puentes por segmentos.
Considere el siguiente caso: Carlos,
Andrés y David son vecinos, pero
actualmente se encuentran disgustados entre sí. Ayer recibieron la
notificación de que se les instalarán las tuberías de agua, teléfono y
gas; ellos no permiten que ningún tubo de la instalación se intercepte.
Cada uno ha intentado, por separado, resolver su problema en el papel,
reemplazando cada persona por un punto, lo mismo que los servicios, y
luego uniéndolos por medio de segmentos. Es decir, los tres han intentado
dibujar el grafo planar de tal forma que no intercepten los segmentos.
¿Cuántos segmentos se pueden dibujar sin que se intercepten?
DEFINICIONES Y CONCEPTOS
BÁSICOS
Algoritmo de Dijkstra: Permite encontrar la ruta óptima desde un
nodo a los demás nodos del grafo.
Algoritmo de Floyd: Permite encontrar la ruta óptima entre todos
los pares de nodos del grafo.
Algoritmo de Warshall: Permite determinar no sólo cuál es la ruta
mínima, sino el camino de mínimo costo para realizarla.
Arco o arista: Enlace entre los nodos de un grafo en el que se
especifica la dirección y sentido en que hace la conexión.
Camino o cadena: Secuencia de segmentos que une dos nodos
cualesquiera del grafo.
Camino simple: Es un camino en el cual ningún vértice se repite.
Camino cerrado: Camino en el que el primero y el último vértice son
el mismo.
Ciclo: Es un camino de longitud 3 o más.
Dirgrafo G(N,A): Es un grafo dirigido.
Grado: Número de arcos que entran o que salen de un nodo del grafo.
Grafo conexo: Existe un camino entre cualquier par de vértices.
Grafo dirigido G(N,A): Conjunto de nodos unidos mediante arcos.
Grafo etiquetado: Cuando a sus vértices o aristas se les ha
asignado un valor de los posibles valores de un conjunto.
Grafo G(N,S): Un conjunto de nodos unidos mediante segmentos. Un
segmento implica que los nodos están unidos, pero no especifica la
dirección o el sentido en que se efectúa la relación.
Listas de adyacencia: Manera de representar un grafo en la que cada
nodo es una cabeza de lista y con los nodos adyacentes se conforma la
lista.
Matriz de adyacencia: Forma de representar la conectividad de un
grafo mediante una matriz NxN, en la que en la intersección del nodo i con
el nodo j hay un cero si no hay conexión en ese sentido, o 1 si la hay.
Matriz de desplazamientos: Manera de representar la conectividad de
un grafo mediante una matriz NxN en la que en la intersección del nodo i
con el nodo j hay un cero, o el valor o costo del desplazamiento si lo
hay.
Recorrido por expansión: Método para recorrer un grafo en el que se
toma como punto de partida un nodo del grafo y se visitan y marcan los
nodos adyacentes del nodo, y se continúa recursivamente el recorrido por
expansión.
Recorrido en profundidad: Método para recorrer un grafo en el que
se toma como punto de partida un nodo del grafo y se marca como visitado,
se recorre cada nodo adyacente no visitado usando el recorrido en
profundidad recursivamente.
Para resolver un problema de grafos utilizando el computador, debemos ser capaces de almacenar grafos en la memoria del computador. Existen diferentes estructuras de datos que permiten almacenar un grafo, entre ellas están la estructura de tipo red o malla, las listas de adyacencia y las matrices de adyacencia.
Para almacenar un grafo en una lista de adyacencia, se puede trabajar con un arreglo de listas. Es conveniente utilizar una lista de adyacencia cuando el grafo es disperso, es decir, aquel que tiene muchos vértices y pocos arcos o aristas.
Cuando el grafo tiene un alto número de arcos, se debe considerar la posibilidad de trabajar con una matriz de adyacencia.
------------------------------------------------------------------------------------
// El siguiente programa almacena un grafo en un arreglo de
listas de adyacencia.
#include "iostream.h"
#include "conio.h"
#define T 10
#define L clrscr()
struct nodo{
int v;
nodo *sig;
};
void ins_nodo(nodo g[],int v,int ad){
nodo *p,*q,*nuevo;
nuevo=new(nodo);
nuevo->v=ad;
nuevo->sig=NULL;
q=NULL;
p=g[v].sig;
while(p!=NULL){
q=p;
p=p->sig;
}
if (q == NULL)
g[v].sig=nuevo;
else
q->sig=nuevo;
}
leer_grafo(nodo grafo[]){
int v,ad,n,i;
cout << "Digite el numero de vertices:
";
cin >> n;
for(i=1;i<=n;i++){
grafo[i].v=0;
grafo[i].sig=NULL;
}
cout << "Lea el primer vertice. Para
salir, teclee -1 : ";
cin >> v;
grafo[v].v=v;
while(v != -1){
cout <<
"Digite el primer adjunto al vertice "<<v<<".
Para terminar,teclee -1 : ";
cin >> ad;
while(ad != -1){
ins_nodo(grafo,v,ad);
cout << "Digite otro adjunto al vertice
"<<v<<". Para terminar,teclee -1 : ";
cin >> ad;
}
cout
<<endl<<"Lea otro vertice. Para salir, teclee -1 :
";
cin >>
v;
if (v!= -1)
grafo[v].v=v;
}
return(n);
}
void listar_grafo(nodo g[],int nv){
int i;
nodo *p;L;
cout << "Lista de Adyacencia del
GRAFO"<<endl<<endl;
for(i=1;i<=nv;i++){
cout
<<g[i].v<<" ->";
p=g[i].sig;
while(p != NULL){
cout << p->v;
p=p->sig;
if (p!=NULL)
cout <<"->";
}
cout
<<endl;
}
}
void main()
{
L;
nodo grafo[T]; int nv;
nv=leer_grafo(grafo);
listar_grafo(grafo,nv);
getch();
}
---------------------------------------------------------------------------------
EJERCICIOS:
1. Escribir un programa para representar un grafo mediante una
matriz de adyacencia.
2. Codificar en C++ los algoritmos de Dijkstra, Floyd y Warshall.
3. Escriba un programa para recorrer y visualizar un grafo por
expansión y en profundidad.
4. Represente mediante un grafo de cinco nodos los principales
sitios de Ibagué; los arcos serán las vias para comunicar estos sitios; en
cada arco coloque el tiempo que toma para desplazarse. Aplique el
algoritmo de Floyd para encontrar los desplazamientos óptimos entre esos
sitios.
5. Incluya, en el problema anterior, un nodo adicional para el
barrio donde Usted vive y coloque las distancias a dos de los otros
sitios. Aplique el algoritmo de Dijkstra y encuentre las rutas
óptimas a partir de su casa.
.
