guia 10 grafos

UNIVERSIDAD INCA GARCILASO DE LA VEGA

FACULTAD DE INGENIERIA DE SISTEMAS, COMPUTO Y TELECOMUNICACIONES

GUIA DE PRÁCTICA 10

ASIGNATURA Estructura de InformaciónTEMA GrafosPROFESOR Carlos A. Ruiz De La Cruz MeloALUMNOCODIGOFECHACICLOTURNOSEMESTRE 2013-III

1. OBJETIVOS

Que el estudiante:

Tenga una correcta definición de la estructura de un grafo, así como su representación y nomenclatura como TAD.

Implemente grafos en código C++.

2. INTRODUCCION TEORICA

Un grafo es un concepto matemático que nos permite tener la posibilidad de manipular el enmarañado de información que se da al tratar de representar problemas muy complejos como en circuitos, redes o problemas de la vida real en las que se trata de hallar el camino mas corto entre dos ciudades, en fin su ámbito de aplicación es muy general y cubre muchas áreas diversas.

Los grafos constituyen una herramienta que nos da la posibilidad de modelar relaciones en las que hay objetos con posibilidades de comunicación, ofreciéndonos una solución menos costosa que las presentadas por otros medios como la programación lineal.

2.1. Definición

Un grafo puede verse como un conjunto de vértices o nodos y aristas o también denominados arcos. Cada arco es una línea que enlaza dos vértices del grafo o también dirigirse o enlazarse a si mismo. En este ámbito los vértices son objetos que guardan información y los arcos son la conexión existente entre los vértices. Los grafos pueden representarse de la siguiente manera:

Figura 11.1. Grafo no dirigido

Un grafo se denomina grafo dirigido o no dirigido dependiendo si los arcos se denotan con una flecha o no. El denotarlos con una flecha(grafo dirigido) significa que las uniones entre un

A

B E

C D

Grafo no dirigido

nodos o vértices : A, B, C, D, E

Arcos o aristas

Grafo dirigido

nodos : A, B, C, D, E

Arcos o aristas

vértice y otro son unidireccionales, ósea que si tenemos un vértice A conectado por una arista con un vértice B donde la flecha apunte de A a B, nos indica que el recorrido es en un solo sentido de A a B, en caso contrario cuando la conexión se da a través de una línea sin ninguna dirección significa que el recorrido puede darse en ambos sentidos(grafo no dirigido) ósea es bidireccional. Por ejemplo el grafo anterior es un grafo no dirigido, mientras que el grafo que esta a continuación es un grafo dirigido.

Figura 11.2. Grafo dirigido

2.2. Grafo dirigido y no dirigido

En la terminología de grafos encontramos dos tipos de grafos, dirigidos y no dirigidos según se exprese o no el sentido de sus arcos. El capítulo grafos estará orientado al enfoque de los grafos dirigidos, así que cuando usemos el término grafos significará que nos referimos a un grafo dirigido y el término arco se referirá a un arco también dirigido, a menos que se diga o se deduzca lo contrario.

2.2.1. Grafo dirigido

Un grafo dirigido G es también llamado un dígrafo en el cual cada arco e de G tiene ya una dirección. En este grafo cada arista e esta descrita por un par ordenado (u,v), donde u y v son nodos del grafo G

Como G es un grafo en el que cada arista e=(u,v), podemos definir G también como el par (V,A) donde V y A tienen el siguiente significado:

V: denota el conjunto finito de nodos o también llamados vértices.A: denota el conjunto finito de arcos o también llamadas aristas.

Con respecto al arco a=(u,v) donde a es un arco que comienza en u y finaliza en v, se define G como una relación que se expresa de la siguiente forma:

G= { (u, v) / u, v V , además existe un arco con un origen en u y un destino en v }

Por ejemplo el grafo siguiente puede expresarse como se observa a su derecha:

2.2.2. Grafo no dirigido

Un grafo no dirigido G tiene una definición similar a la de un grafo dirigido tal es asi que G=(V,A) y esta definido como el par (V, A) donde:

A

B E

C D

A

B E

C D

V={ A, B, C, D, E}A={ (A,B),(A,E), (B,C), (B,D)}

V: es también el conjunto finito de nodos o vértices.A: es también el conjunto finito de arcos

Pero con la diferencia que al expresar la relación no hacemos mención que hay un sentido entre un vértice y otro, simplemente es un arco entre dos vértices:

G={ (u, v) / u, v V, además existe un arco entre u y v }

Por ejemplo el siguiente grafo es un grafo no dirigido

2.3. Terminología

Camino: se define un camino entre dos nodos como una secuencia de nodos o vértices en la que dos nodos contiguos o sucesivos están unidos por un arco del grafo

Camino simple: por camino simple se tiene a un camino en el que desde un vértice a otro, en su secuencia de nodos, ningún nodo se repite, ósea no se pasa dos o mas veces por un mismo nodo.

Ciclo: por ciclo se entiende a un camino en el cual el camino simple tiene como inicio y final de camino al mismo vértice. Cuando en un grafo no existen ciclos estamos entonces ante un árbol.

Longitud de camino: es el número de nodos que tiene la secuencia de un camino

A

B F

C D

E

AB F

C DE

AB F

CE

Árbol Grafo ciclo

A

B F

C D

E

{ E, A,B, F}: camino simple E-F{ E, A, B, C, D, B, F} camino no simple E-F

A

F

C D

E

{E, A, F} camino de longitud 3{E, C, A, F,D}:camino de longitud 5

Grafo fuertemente conexo: se le dice al grafo en el cual para todo par de vértices se da un camino entre ellos y a su vez un camino en sentido inverso. A continuación puede observar dos grafos fuertemente conexos.

Grafo unilateralmente conexo: se le dice al grafo que presenta el caso contrario al que presenta un grafo fuertemente conexo.

2.4. Representación de grafos dirigidos

Al igual que otros TAD’s, un grafo se puede implementar de varias maneras, así podemos tener una implementación a través del uso de arreglos bidimensionales y la otra forma es haciendo uso de listas enlazadas. ¿Cual forma es la mas adecuada para la implementación de un grafo?, bueno, la respuesta dependerá principalmente del propósito o de la frecuencia con la que se acceda a la información de la estructura.

Ambas estructuras, arreglos y listas tienen ventajas y desventajas las cuales pueden consultarse en sus respectivos capítulos. En cada caso lo que se busca es la forma de representar un grafo, para ello, un grafo se puede representar en memoria a través de una matriz de adyacencia que es una matriz cuadrada que se utiliza como una manera de expresar relaciones binarias, o también puede representarse a través de una lista de adyacencia en caso la implementación fuera en termino de listas.

Una matriz de adyacencia se conceptúa como una estructura bidimensional o tabla de dimensiones V x V, en el que un par a[ i ][ j ] registrara un valor de uno si realmente existe un arco que va del nodo i al nodo j, en caso contrario el valor del par a[ i ][ j ] será cero.

A F

D

E

A FE

Por ejemplo no se puede llegar de F, A o D a E

Por ejemplo no se puede llegar de F a E

D

A FE

A

F

C D

E

C

B DA

ABCDA1B11C1D1

Matriz de adyacencia

2.4.1. Matriz de adyacencia

Sea G un grafo dirigido de n vértices y ordenados desde v1, v2, v3 hasta vn, para el cual tenemos la matriz de adyacencia A=( I , J) del grafo G, matriz de m x m y definida de la manera siguiente:

1 si existe una arco que va de vI a vJ

A I,J 0 si no existe una arista de vI a vJ

Una matriz A que guarda valores de 0 y 1 se conoce como matriz de bits o también matriz booleana y depende de la clasificación de los nodos de G ya que distintas clasificaciones pueden resultar en distintas matrices de adyacencia. Por ejemplo observemos el siguiente grafo:

V={ A, B, C, D }A={ (A,D), (A,C), (C,D), (D,B), (B,A), (C,C) }

A

raíz

nulo

B C

nulo

D

nulo nulo

nulo Lista de adyacencia

B

A

D

nulo

nulo B

nulo

C

nulo

nulo

A

C

D

B

Luego asumiendo que el orden de los vértices es A, B, C y D, la matriz de adyacencia toma la configuración siguiente:

En la matriz un valor de 1 indica un camino directo y un 0 representa un camino que no existe.

ORIGEN DESTINOA DA CC DD BB AC C

La importancia de la matriz de adyacencia radica principalmente en que es un mecanismo que nos ayuda a definir los caminos de longitud 1 que se dan en el grafo.

En general:

A : nos muestra los caminos de longitud 1A2 : A . A nos muestra los caminos de longitud 2A3 : A2. A nos muestra los caminos de longitud 3:Ak : Ak-1. A nos muestra los caminos de longitud k

De lo dicho anteriormente, probémoslo con el siguiente grafo:

V={A, B, C, D}A={ (A,C) , (C,A), (C,D), (D,B), (B,A) }

Matriz de caminos de longitud 1

0011100000110100

A=

A

C

D

B

ABCDA0010B1000C1001D0100

A=

En la matriz observamos que un 1 representa un camino directo

ORIGEN DESTINOA CB AC AC DD B

Matriz de caminos de longitud 2

En la matriz observamos que un 1 representa un camino de longitud 2.

Matriz de caminos de longitud 3.

En la matriz observamos que un 1 representa un camino de longitud 3. Sin embargo de C a A hay dos caminos de longitud 3.

ORIGEN DESTINOA BA CB AB DC AC DD C

Matriz de caminos de longitud 4.

ORIGEN DESTINOA AA DB CC BC CD A

ABCDA1001B0010C0110D1000

A2 =

ABCDA0110B1001C2001D0010

A3=

ABCDA2001B0110C0120D1001

A4=

En la matriz observamos que un 1 representa un camino de longitud 4, sin embargo de A a A hay dos caminos de longitud 4, así como también hay dos caminos de longitud 4 de C a C.

ORIGEN DESTINOA AA DB BB CC BC CD AD D

Como A es nuestra matriz de adyacencia, definamos ahora la matriz B como la suma total de matrices como sigue:

B = A + A2 + A3 +....+Am

Como resultado dada la entrada i, j de la matriz B, nos dará el número total de caminos de longitud n o menor, del vértice o nodo i al j.

2.4.2. Matriz de caminos

Dado G un grafo dirigido simple con m vértices v1, v2…..vm. Su matriz de caminos es la matriz cuadrada mxm donde C= v(i, j) y que se define como se muestra:

Desde la matriz B comenzamos a construir la matriz de caminos C de la manera siguiente:

Considere el grafo G anterior con 4 vértices

En el cual sumando las matrices A, A2, A3 y A4 obtenemos como resultado la matriz B:

1 si hay un camino de vi a vj Ci j = 0 si no existe camino de vi a vj

1 si tenemos un número diferente de cero Ci j = en la entrada i, j de la matriz B.

0 en caso contrario.

A

C

D

B

0010100010010100

1001001001101000 0110100120010010

2001011001201001

+ + +B=

A2 A3 A4A

reemplazando las entradas no nulas por 1, obtenemos la matriz de caminos C del grafo G:

Otra manera de encontrar la matriz de caminos sin tener que hacer los cálculos anteriores es usando el algoritmo de Warshall.

2.4.2.1. Algoritmo de Warshall

Dado un grafo G dirigido con m vértices, v1, v2,…vm . Queremos encontrar la matriz de caminos C para el grafo G. Para tal propósito primero se definen las matrices cuadradas mxm como sigue:

A = C0 , C1 , C2 , …….. Cm

Sea entonces Ck (i, j) la entrada i, j de la matriz Ck, definimos:

en otras palabras,

C0 (i, j) = 1 si hay un arco de vi a vJ C1 (i, j) = 1 si hay un arco de vi a vJ que no usa otros vértices excepto v1 o v0 C2 (i, j)) = 1 si hay un arco de vi a vJ que no usa otros vértices excepto v2 o v1 o v0

Cn = A

Warshall se percato que Ck (i, j) = 1 solo se puede dar si ocurre uno de los siguientes casos:

a) Se tiene un camino simple de vi a vJ que no requiere usar otros vértices excepto v1 , v2

, … vk-1, por tanto:

Ck-1 (i, j) = 1

b) Se tiene un camino simple de vi a vk y otro camino simple vk a vJ que no requiere usar otros vértices excepto v1 , v2 , … vk-1, por tanto:

Ck-1 (i, k) = 1 y Ck-1 (k, j) = 1

De tal modo los valores de la matriz Ck se pueden obtener por la siguiente afirmación:

Ck (i, j)= Ck-1 (i, j) ( Ck-1 ( i, k ) Ck-1 (k , j) )

3 1 2 22 1 2 13 2 3 22 1 1 1

B=

1111111111111111

C=

1si tenemos un camino simple de vi a vJ que no usa otros vértices aparte de posiblemente v1, v2, …Vk

0En otro casoCk (i, j) =

2.4.2.2. Construcción de Matriz de Camino

Especificación del Tad y los algoritmos

Especificacion GRAFOvariable

C : arreglo matricial lógicom : entero

métodosGRAFO() :no retorna valor.ingresarMatrizDeAdyacencia() :no retorna valor.matrizDeCaminos() :no retorna valor.mostrarMatrizCamino() :no retorna valor.menú() :no retorna valor.

significadoGRAFO se asigna memoria al arreglo dinámico.ingresarMatrizDeAdyacencia se ingresan valores 1 y 0.matrizDeCaminos se genera la matriz de camino(C).mostrarMatrizCamino visualiza la matriz de camino(C).menú se visualizan las alternativas del menú.

Fin_especificacion

Procedimiento matrizDeCaminos()entero : k, i, j Desde k 0 Hasta k< m con incremento 1 Hacer

Desde i 0 Hasta i< m con incremento 1 HacerDesde j 0 Hasta j< m con incremento 1 Hacer

C[i][j]C[i][j] (C[i][k] ^ C[k][j]) Fin_desde

Fin_desde Fin_desde

Fin_procedimiento

Implementación del TAD en C++

#include <iostream>#include <fstream>#include <cstdlib>using namespace std;class GRAFO{

bool **C;int m;public:void menu(){

cout<< "\nMENU DE OPCIONES\n";cout<< "----------------\n" ;cout<<"<1> Ingresar Matriz de Adyacencia\n";cout<<"<2> Mostrar Matriz de Camino\n";cout<<"<3> Salir \n";

}GRAFO(int n){

m=n; C = new bool*[n]; //vector filas for (int i=0;i<n;i++)

C[i] = new bool[n]; } void ingreseMatrizDeAdyacencia(){

for(int i=0; i<m; i++){cout<<"\n fila "<<i<<"\n";

for(int j=0; j<m; j++){cout<<" j="<<j<<": "; cin>>C[i][j];

} }matrizDeCaminos();}void matrizDeCaminos(){

int k,i,j; for(k=0;k<m;k++)

for(i=0;i<m;i++)for(j=0;j<m;j++)

C[i][j]=C[i][j] | (C[i][k] & C[k][j]) ;cout<<"\n SE HA GENERADO MATRIZ DE CAMINO";

}void mostrarMatrizCamino(){

int i,j; cout << "\n\nMATRIZ DE CAMINOS \n\n";for(i=0;i<m;i++){

cout << "\n";for(j=0;j<m;j++)

cout << "\t"<<C[i][j];}

}};int main(){

char opcion;int x;GRAFO g(4);do{

g.menu();cout<<"\ningrese opcion : ";opcion=cin.get();switch(opcion){

case '1': g.ingreseMatrizDeAdyacencia();break;

case '2':g.mostrarMatrizCamino();break;

}cin.ignore();

}while( opcion !='3');system(“pause”);return 0;

}Probemos el programa con el grafo que se muestra a continuación:

V = { A, B, C, D}A = { (A, D) , (D, B), (B, A), (C,D)}

A B C DA 0 0 0 1B 1 0 0 0C 0 0 0 1D 0 1 0 0

A

C

D

B

A =

Como observamos esta es la matriz de adyacencia que ingresaremos al programa al ejecutar la opción 1 del menú.

MENU DE OPCIONES----------------<1> Ingresar Matriz de Adyacencia<2> Mostrar Matriz de Camino<3> Salir

ingrese opcion : 1

fila 0 j=0: 0 j=1: 0 j=2: 0 j=3: 1

fila 1 j=0: 1 j=1: 0 j=2: 0 j=3: 0

fila 2 j=0: 0 j=1: 0 j=2: 0 j=3: 1

fila 3 j=0: 0 j=1: 1 j=2: 0 j=3: 0

SE HA GENERADO MATRIZ DE CAMINO

Una vez ingresada la matriz de adyacencia se genera la matriz de caminos que se puede visualizar con la opción 2 como se observa a continuación:

MENU DE OPCIONES----------------<1> Ingresar Matriz de Adyacencia<2> Mostrar Matriz de Camino<3> Salir

ingrese opcion : 2

MATRIZ DE CAMINOS

1 1 0 1 1 1 0 1 1 1 0 1

1 1 0 1

MATRIZ DE CAMINO

k i j C k(i, j) = C k-1 (i, j) v (C k-1 (i, k) ^ C k-1(k, j))0 0 0 0 0 0 00 0 1 0 0 0 00 0 2 0 0 0 00 0 3 1 1 0 1

0 1 0 1 1 1 00 1 1 0 0 1 00 1 2 0 0 1 00 1 3 1 0 1 1

0 2 0 0 0 0 00 2 1 0 0 0 00 2 2 0 0 0 00 2 3 1 1 0 1

0 3 0 0 0 0 00 3 1 1 1 0 00 3 2 0 0 0 00 3 3 0 0 0 1

ABCDA0001B1001C0001D0100

A1 =


1 1 0 1 1 0 11 1 1 0 0 0 01 1 2 0 0 0 01 1 3 1 1 0 1

1 2 0 0 0 0 11 2 1 0 0 0 01 2 2 0 0 0 01 2 3 1 1 0 1

1 3 0 1 0 1 11 3 1 1 1 1 01 3 2 0 0 1 01 3 3 1 0 1 1


2 1 0 1 1 0 02 1 1 0 0 0 02 1 2 0 0 0 02 1 3 1 1 0 1

2 2 0 0 0 0 02 2 1 0 0 0 02 2 2 0 0 0 02 2 3 1 1 0 1

2 3 0 1 1 0 0

ABCDA0001B1001C0001D1101

A2 =

2 3 1 1 1 0 02 3 2 0 0 0 02 3 3 1 1 0 1


3 1 0 1 1 1 13 1 1 1 0 1 13 1 2 0 0 1 03 1 3 1 1 1 1

3 2 0 1 0 1 13 2 1 1 0 1 13 2 2 0 0 1 03 2 3 1 1 1 1

3 3 0 1 1 1 13 3 1 1 1 1 13 3 2 0 0 1 03 3 3 1 1 1 1

2.4.3. Matriz de Camino mínimo

Dado un grafo dirigido G con m vértices v1, v2,…vm , tal es así que G tiene pesos, en el cual cada arco e de G tiene un valor numérico positivo w(e) denominado peso o también longitud de la arista e. Entonces G es posible escribirla en memoria por su raíz de pesos W que se define como se muestra seguidamente:

W(e)si hay una arista e de vi a vJ

0Si no hay arista de vi a vJ W ( i, j ) =

ABCDA0001B1001C0001D1101

A3 =

ABCDA1101B1101C1101D1101

A4 =

C es una matriz de caminos que nos detalla si hay o no caminos entre los vértices. Pero nuestro objetivo en esta parte es hallar una matriz Q que nos detalle las longitudes de los caminos entre los vértices donde cada (i, j) de Q signifique lo siguiente:

Q ( i, j ) es igual a la longitud del camino mínimo de vi a vJ

Para lo cual definimos una lista de matrices Q0, Q1,…Qm cuyas entradas estarán dadas por:

Cada Qk (i, j) es igual a la menor longitud de los caminos anteriores de vi a vJ o también igual a la suma total de las longitudes de los caminos anteriores de vi a vk y de vk a vJ

.

O mas precisamente:

Q 0(i, j) = mínimo (Q k-1 (i, j) , Q k-1 (i, k) + Q k-1(k, j))

Q0 es en realidad la misma matriz de pesos W con la diferencia que cada 0 de W se reemplaza por un valor numérico muy grande (∞). Así la matriz Qm final será la matriz Q deseada.

Por ejemplo tengamos el grafo siguiente con su respectiva matriz de pesos W:

k i j Q k(i, j) = Mínimo( Q k-1 (i, j) , Q k-1 (i, k) + Q k-1(k, j))0 0 0 0 0 1 0 0 2 0 0 3 1 1 1

0 1 0 2 2 2 0 1 1 4 4 2 0 1 2 2 0 1 3 3 2 1

0 2 0 0 2 1 0 2 2 0 2 3 3 3 1

0 3 0 0 3 1 5 5 0 3 2 0 3 3 1

A

C

D

B

2

13

5

4ABCDA0001B2400C0003D0500

W=

ABCDA1B243C3D5

Q1 =


1 1 0 2 2 4 21 1 1 4 4 4 41 1 2 4 1 1 3 3 3 4 3

1 2 0 21 2 1 41 2 2 1 2 3 3 3 3

1 3 0 7 5 21 3 1 5 5 5 41 3 2 5 1 3 3 8 5 3


2 1 0 2 2 2 1 1 4 4 2 1 2 2 1 3 3 3 3

2 2 0 2 2 1 2 2 2 2 2 3 3 3 3

2 3 0 7 7 2 3 1 5 5 2 3 2 2 3 3 8 8 3

k i j Q k(i, j) = Mínimo( Q k-1 (i, j) , Q k-1 (i, k) + Q k-1(k, j))

ABCDA1B243C3D758

Q2 =

ABCDA1B243C3D758

Q3 =

3 0 0 8 1 73 0 1 6 1 53 0 2 1 3 0 3 1 1 1 8

3 1 0 2 2 3 73 1 1 4 4 3 53 1 2 3 3 1 3 3 3 3 8

3 2 0 10 3 73 2 1 8 3 53 2 2 3 3 2 3 3 3 3 8

3 3 0 7 7 8 73 3 1 5 5 8 53 3 2 8 3 3 3 8 8 8 8

2.4.3.1. Construcción de Matriz de Camino Mínimo

Especificación del TAD y los algoritmos

Especificacion GRAFOvariable

Q : arreglo matricial entero.m : entero

métodosGRAFO(n) :no retorna valor.ingresarMatrizDePesos() :no retorna valor.matrizDeCaminoMinimo() :no retorna valor.mostrarMatrizCaminoMinimo() :no retorna valor.menú() :no retorna valor.MINIMO() :retorna entero.

significadoGRAFO se asigna memoria al arreglo dinámico.ingresarMatrizDeAdyacencia se ingresan valores 1 y 0.matrizDeCaminos se genera la matriz de camino(C).mostrarMatrizCamino visualiza la matriz de camino(C).menu se visualizan las alternativas del menú.MINIMO retorna el mínimo valor de dos números.

Fin_especificacion

Procedimiento matrizDeCaminos()entero : k, i, j Desde k 0 Hasta k< m con incremento 1 Hacer

Desde i 0 Hasta i< m con incremento 1 HacerDesde j 0 Hasta j< m con incremento 1 Hacer

Q[i][j]MINIMO(Q[i][j], Q[i][k] + Q[k][j]) Fin_desde

Fin_desde

ABCDA861B243C1083D758

Q4 =

Fin_desde Fin_procedimiento

Implementación del TAD en C++

#include <iostream>#include <fstream>#include <cstdlib>using namespace std;class GRAFO{

int **Q;int m;public:void menu(){

cout<< "\nMENU DE OPCIONES\n";cout<< "----------------\n" ;cout<<"<1> Ingresar Matriz de Pesos\n";cout<<"<2> Mostrar Matriz de Camino Minimo\n";cout<<"<3> Salir \n";

}GRAFO(int n){

m=n; Q= new int*[n]; //vector filas for (int i=0;i<n;i++)

Q[i] = new int[n];} void ingreseMatrizDePesos(){

char elemento[10]; for(int i=0; i<m; i++){

cout<<"\n fila "<<i<<"\n"; for(int j=0; j<m; j++){

cout<<" j="<<j<<": ";cin>>elemento;if(!strcmp(elemento,"-"))

Q[i][j]=30000;else Q[i][j]=atoi(elemento);

}} matrizDeCaminoMinimo();

}void matrizDeCaminoMinimo(){

int i,j,k;for(k=0;k<m;k++)

for(i=0;i<m;i++)for(j=0;j<m;j++)

Q[i][j]=MINIMO(Q[i][j],Q[i][k] + Q[k][j]) ;} void mostrarMatrizCaminoMinimo(){

int i,j; for(i=0;i<m;i++){

cout << "\n";for(j=0;j<m;j++)

if(Q[i][j]!=30000) cout << "\t"<<Q[i][j]; else cout << "\t-";//ì";

}} int MINIMO(int a, int b){

if(a<b || b<0) return(a); else return(b);

}};int main(){

char opcion;int x;GRAFO g(4);do{

g.menu();cout<<"\ningrese opcion : ";opcion=cin.get();switch(opcion){

case '1': g.ingreseMatrizDePesos();break;

case '2':g.mostrarMatrizCaminoMinimo();break;

}cin.ignore();

}while( opcion !='3');system(“pause”);return 0;

}

El programa funciona de manera similar al anterior programa con la diferencia que la matriz de entrada es la matriz de pesos y la salida es la matriz de camino mínimo. También hay que decir que cada símbolo en el programa se ingresa a través de un guion(-).

2.5. Aplicación

Un grafo es un concepto matemático que tiene múltiples aplicaciones para representar diversos tipos de relaciones que pueden corresponder a diferentes disciplinas: Su aplicación es tan diversa que se da también en la resolución de problemas clásicos

como el problema de los siete puentes de Konigsberg, el problema del cartero chino, el problema del viajante de comercio, etc.

Como modelo matemático su aplicación se presenta en el control de semáforos en una intersección de calles, para el plano de una planta de un edificio, cadenas de Markov, etc

Representación de la World- Wide Web, la red mas famosa del mundo. En todas las áreas de la ingeniería su uso es diverso, tal es así que es adecuado para

describir redes eléctricas, circuitos, contadores o sistemas de apertura, así como también dentro del dibujo computacional.

Uno de sus usos mas conocidos es en la representación o modelamiento de trayectos como por ejemplo el que tienen las líneas de autobuses, en el cual se busca el camino optimo entre dos puntos o ciudades

Su uso también se da en la gestión de proyectos, tal es así que al utilizar en esta disciplina una técnica PERT en la programación de proyectos, una red de tareas es posible describirla gráficamente.

Su aplicación también se da en las ciencias sociales, para describir conceptos de redes sociales, en el cual cada nodo del grafo sustituye a un actor social, verificando su importancia en la red y permitiendo graficar un estructura social.

También es útil en biología al ser una buena forma de representar hábitats, donde un hábitat es representado por un nodo o vértice y los caminos o senderos o migraciones de animales los representan los arcos o aristas.

3. REQUERIMIENTOS O MATERIAL Y EQUIPO

Software Dev C++ 1 Diskete

4. PROCEDIMIENTO

El procedimiento consiste en dos pasos

Especificación del TAD Implementación del TAD

5. EJERCICIOS RESUELTOS

Ejemplo 01

Halle la matriz de camino sin usar Warshall.

Solución:

Ejemplo 02

Halle la matriz de camino sin usar Warshall.

Solución:

A

DB

C

A

DB

C

1 1 1 11 1 1 11 1 1 11 1 1 1

C=

0 0 1 01 1 0 00 0 1 10 1 0 0

0 0 1 11 0 1 00 1 0 10 0 0 0

0 1 1 11 1 1 11 1 1 11 1 1 0

1 1 1 11 1 1 11 1 1 11 1 1 1

B= + + +

A3A2 A4A

0 0 1 01 0 0 01 0 0 00 1 0 1

1 0 0 00 0 1 00 0 1 01 1 0 1

0 0 1 01 0 0 01 0 0 01 1 1 1

1 0 0 00 0 1 00 0 1 01 1 1 1

B= + + +

A3A2 A4A

Ejemplo 03

Halle la matriz de camino usando Warshall.

Solución:

k i j Ck (i, j)= Ck-1 (i, j) (Ck-1 ( i, k ) ^ Ck-1 (k , j))0 0 0 0 0 0 00 0 1 1 1 0 10 0 2 1 1 0 1

0 1 0 1 1 1 00 1 1 1 1 1 10 1 2 1 1 1 1

0 2 0 0 0 0 00 2 1 0 0 0 10 2 2 0 0 0 1


1 1 0 1 1 1 11 1 1 1 1 1 11 1 2 1 1 1 1

1 2 0 0 0 0 11 2 1 0 0 0 11 2 2 0 0 0 1

A

B

C

0 1 1 1 1 1 0 0 0

C1=

1 1 1 1 1 1 0 0 0

C2 =

0 1 1 1 1 1 0 0 0

A=C0=

1 0 0 00 0 1 00 0 1 01 1 1 1

C=


2 1 0 1 1 1 02 1 1 1 1 1 02 1 2 1 1 1 0

2 2 0 0 0 0 02 2 1 0 0 0 02 2 2 0 0 0 0

Ejemplo 04

En función de las siguientes matrices de adyacencia, halle los grafos correspondientes.

1 1 1 1 1 1 0 0 0

C3 = es la matriz de camino

1 0 1 0 01 0 1 0 10 0 0 1 00 1 0 0 00 1 1 0 0

A =c) A

B

E

C DSolución:

Solución:1 0 1 1 0 1 0 0 0

A =a) A

BC

Solución:

1 0 1 01 0 1 00 0 0 10 1 0 0

A =

b) A

B

C

D

Ejercicio 05

Halle la matriz de camino mínimo para cada uno de los siguientes grafos.

5.1. Ejercicios propuestos

1. Halle la matriz de camino para el siguiente grafo sin usar Warshall.



A

C

B

A

C

BD

E

A

C

B D

A

BC

2

3

5

1

3 25 1

Q =

Solución:a)

A

B

D

C

23

72

5

7

2 3 107 2 5 7

Q =

Solución:b)

A

B

E

C D1

3

2 2

6

7

2

4

8

5 2 9 2 3 11 8 6 3 4 2 15 7 10 1 9 14 6 9 10 8 12 4 5 6 6

Q =

Solución:

c)

4. Halle la matriz de camino usando Warshall, para cada caso de los ejemplos 01, 02 y 03.

5. Halle la matriz de camino mínimo para cada uno de los siguientes grafos.

6. Halle el grafo en base a su matriz de adyacencia

A

C

B D

A

C

B D

2 4

5

2

13

10

1

2

1

4a) b)

A

C

B E

A

C

B D

DE

F

1 1

3

2

1

4

11

5

13 2

1

4

1

8

c) d)

ABCDA1001B1001C0101D0000

a)

ABCDA111B1101C0100D0001

b)

ABCA100B010C011

c)

ABCA011B010C011

d)

ABCDEA10010B10001C01010D00000E01001

e)

ABCDA0111B1001C0100D0111

f)

Ejercicio 06

7. Determine que grafos son grafos fuertemente conexos o unilateralmente conexos.

8. De los grafos de la pregunta 06 determine si los caminos son simples o no o ambos.

a) Para el grafo a)De B –ADe C- A

b) Para el grafo b)De C-ADe B-D

c) Para el grafo d)De B-DDe D-A

d) Para el grafo f)De C- ADe C- B

9. Escriba la especificación, el algoritmo y el programa para un grafo cuya matriz de adyacencia se desea implementar usando no arreglos sino mediante asignación dinámica de memoria y enlaces.

10. Escriba la especificación, el algoritmo y el programa para un grafo donde cada matriz A, mas la matriz suma B se quieren meter en una lista. Por ejemplo para el grafo G con 4 vértices:

A

C

B D

A

C

B D

a) b)

A

B D

A

C

B D

c) d)

A

C

B D

A

C

B D

e) f)

A

C

D

B

en el cual sumando las matrices A, A2, A3 y A4 obtenemos como resultado la matriz B:

Observe que en algunas de las matrices A, A2, A3 y A4 existen valores mayores de 1, lo cual significa que hay más de un camino para una longitud determinada.

Se pide ingresar las matrices como se observa en una lista:

11. Escriba la especificación, el algoritmo y el programa para un grafo donde su matriz de adyacencia no se quiere implementar con arreglos ni usando asignación dinámica de memoria, sino usando filas secuenciales.

0010100010010100

1001001001101000 0110100120010010

2001011001201001

+ + +B=

A2 A3 A4A

3122212132322111

B=

A

raíz

A2

A3

A4

nulo

B

guia 10 grafos

Documents