Índice
Pág.
Introducción……………………………………….……………. 4
Grafos- Conceptos.…..…......................................................5
Trayectorias…………………………………….………............6
Ciclos………………………………………...............................7
Grafos Dirigidos……………...................................................8
Grafos en Programas ………………….................................9
Matrices dispersas ..............................................................11
Aristas ponderadas .............................................................12
Representaciones ligadas.....................................................14
Representación de directorio de nodos................................15
Representación de multi- lista...............................................17
Recorrido de grafos ,amplitud y profundidad........................19
Conclusión ……………………………………………………...25
Introducción
En este trabajo se tratará de explicar lo que son los grafos, sus tipos, y algunas derivaciones de ellos, así como su representación gráfica y en algunos casos, su representación en algún programa informático, así como en la memoria.
En este trabajo, se explica de manera muy sencilla los conceptos y algunas metodologías con un lenguaje no tan rebuscado para su mayor entendimiento.
Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de diversas índoles
Grafos
Un grafo es un conjunto de puntos y un conjunto de líneas con cada línea se une un punto a otro. Los puntos se llaman los nodos del grafo, y las líneas se llaman aristas. Denotemos al conjunto de nodos de un grafo dada G, por VG y, al conjunto de aristas, por EG .Por ejemplo, en el grafo G de la figura 7-1, VG = ( a,b,c,d ) y EG= (1,2,3,4,5,6,7,8). El número de elementos de VG es llamado el orden del grafo G. Un grafo nulo es un grafo con orden cero.
Una aristas está determinada por los nodos que conecta .La arista 4, por ejemplo ,conecta los nodos c y d y se dice que es de la forma (c,d).Un grafo está completamente.
Figura 7-1 Ejemplo de grafo
Definido por sus conjuntos de nodos y aristas .La posición real estos elementos en la página no tiene importancia .La gráfica de la figura 7-1 es equivalente al grafo de la figura 7-2.
Figura 7-2 Grafo equivalente a la figura 7-4
Nótese que puede haber varias aristas conectando a dos nodos, por ejemplo, los arcos 5,6 y 7 todos son de la forma (b,d). Algunos pares de nodos pueden estar desconectados
Por ejemplo, no hay aristas de la forma (a,c) o (a,d) Algunas aristas pueden conectar un nodo a si mismo, por ejemplo la arista 8 es de la forma (a,a), a aristas se le llaman BUCLES
Un grafo G se llama grafo simples las siguientes condiciones son válidas.
1.No tiene ciclos, esto es, no existe una arista EG de la forma (vv), donde V esta en VG
2.No hay mas de una arista uniendo un par de nodos, esto es, no existe mas de una arista en EG de la forma (v1, v2), para cualquier par de elementos v1 y v2 en VG.
La figura 7-3 muestra un grafo simple derivado del ejemplo mostrado en la figura 7-4.
Un grafo que no es simple algunas veces es llamado multigrado. Encontrará, que las aristas también se les conocen como arcos y a los nodos como vértices.
Un grafo conexo es una gráfica que no se puede dividir en dos gráficas, sin eliminar por lo menos una de las aristas. El grafo de la figura 7-4 es un grafo no conexo.
Figura 7-3 Ejemplo de grafo simple derivado de la figura 7-1.
Figura 7-4 Ejemplo de un grafo desconectado.
Trayectorias
Una trayectoria en un grafo es una, secuencia de una o mas aristas que conecta a dos nodos. Denotamos por P(Vp Vj) a una trayectoria que conecta a los nodos Vi y Vj. Para que P(Vp Vj) exista, debe hacer en EG una secuencia de arcos de la siguiente forma:
P(Vp Vj) = (Vp V1) (Xp X2) . . . (Xn-p Xn) (Xn’ Vj)
La longitud de la trayectoria es el número de aristas que la componen. En el grafo simple de la figura 7-3 se tienen las siguientes trayectorias entre los nodos b y d:
P(b,d)= (b,c) (c,d) de longitud
P(b,d)= (b,c) (c,d) (b,c) (c,d) de longitud
P(b,d)= (b,d) de longitud
P(b,d)= (b,c) (c,d) (b,d) de longitud
En general, sólo estamos interesados en trayectorias en las cuales un nodo dado es “visitado” no mas de una vez. Esto restringe nuestro interés a la primera y tercera trayectorias anteriores. La segunda trayectoria visita dos veces a los nodos b y c, la cuarta trayectoria visita al nodo b dos veces. Siempre estaremos interesados en no recorrer la misma arista dos veces en una trayectoria. Esto evitará que nuestros algoritmos se tarden mucho por regresar sobre sus pasos.
Ciclos
Un ciclo es una trayectoria sobre la cual se cumple con las siguientes dos condiciones:
1.Ninguna arista puede aparecer mas de una vez en una secuencia de aristas.
2.El nodo inicial de la trayectoria es el mismo que el nodo Terminal, es decir, P(v,v).
En otras palabras, un ciclo regresa a su punto de inicio. El grafo de la figura 7-2 tiene varios ciclos, por ejemplo:
P(a,a) = (a,a)
P(b,b)= (b,c) (c,d)
P(b,b)= (b,c) (c,d) (d,b)
P(d,d)= (d,b) (b,c) (c,d)
P(d,d)= (d,b) (b,d)
Un grafo sin ciclos se dice que es acíclica. Las figuras 7-5 a) y b) representan grafos acíclicos.
Figura 7-5 Ejemplo de grafos aciclicos
Grafos Dirigidos
Otro caso especial de la estructura de grafos general es le grafo dirigido, en el cual se les asigna dirección a las aristas de la gráfica. Se proporciona un ejemplo en la figura 7-6.
Figura 7-6 Ejemplo de un grafo dirigido
Cada arista del grafo dirigido incluye una flecha para indicar la dirección.
El grado interno de un nodo en un grafo es el número de aristas que terminan en un nodo; el grado externo de un nodo, es el número de aristas que salen de este nodo. El grado de un nodo es la suma de sus grados internos y externos . Por ejemplo, en la figura 7-6 los valores son:
Grado-interno(a)= 1 Grado- externo(a)= 2 Grado(a)= 3
Grado-interno (b)= 4 Grado- externo(b)= 2 Grado(b)= 6
Grado-interno(c)= 1 Grado- externo(c)= 2 Grado(c)= 3
Grado-interno (d)= 2 Grado- externo(d)= 2 Grado(d)= 4
A lo largo de este capítulo nos referimos a los nodos de los grafos por sus etiquetas.
En realidad, un nodo puede contener cualquier clase de información. Tendremos a ignorar el contenido de estos nodos, sin embargo, no olvide que en última instancia el propósito de gráficas y árboles es el de representar la estructura lógica de esta información.
Grafos en Programas
Tal y como hemos estudiado otras estructuras de datos en capítulos anteriores, el tipo de datos llamados grafos no esta predefinido en los lenguajes de programación comunes.
Por esto, las características del grafo se simulan, alojándolas en otra estructura de datos.
Existen tres formas principales para representar grafos, representación matricial, representación de lista y representación de multi-lista. Después de considerar cada una de éstas entraremos en la discusión de algunas de las operaciones mas comunes sobre grafos: recorrido de gráficas y análisis de trayectorias
Representación de la Matriz de Adyacencias
Considere un grafo G con un conjunto de nodos VG y un conjunto de arcos EG . Suponga que la gráfica es de orden N, para N> =1 .Una de representar esta gráfica es utilizando una matriz de adyacencias,la cual es de un arreglo de A de N-por-N, donde
1 si y solo si la arista Vi,Vj está en EG
A(i,j) =
0 en otro caso
Si hay una arista que conecta los nodos i y j, entonces A (i,j)=1 La matriz del grafo no dirigida, mostrada en la figura 7-7 es ;
figura 7-7 Ejemplo de grafo no-dirigido
i\j 1 2 3 4 5 6
1 0 1 0 0 0 0
2 1 1 1 0 0 0
3 0 1 0 1 1 1
5 0 0 1 0 0 0
6 0 0 1 0 0 0
Grafos dirigidos
Una arista de un grafo dirigido tiene su fuente en un nodo y su final en otro nodo,Por convención, la arista (VpVj) denota la dirección del nodo dirigido de la figura 7-8 es
figura 7-1 Ejemplo de grafo dirigido
i\j 1 2 3 4 5 6
1 0 1 0 0 0 0
2 0 1 1 0 0 0
3 0 0 0 0 1 1
5 0 0 0 0 0 0
6 0 0 0 0 0 0
Matrices dispersas
Un grafo de orden N tiene una matriz de adyacencia de N-por-N .En muchos casos estas matrices de adyacencia son matrices dispersas y se pueden almacenar como arreglo dispersos . En estos casos , la representación matricial en general no es tan recomendado como la forma de listas ligadas
La matriz de adyacencia de un grafo no dirigido es simétrica. Por lo tanto, aun cuando la matriz no sea dispersa, los requerimientos de almacenamiento pueden reducirse casi a la mitad al almacenar sólo el triángulo superior (o inferior ) de la matriz.
Definición de grafos en COBOL y en PASCAL
La siguiente definición del arreglo puede ser usado para declarar un grafo llamado GRAFICA, de orden 24,en COBOL.La gráfica requiere de una matriz de adyacencias de 24 por 24
01 GRAFO
02 REGLÓN OCCURS 24 TIMES
03 COLUMNA OCCURS 24 TIMES
04 ARCO PIC 9
El ARCO ( I, J ) tiene entonces el valor de 1 si existe una arista entre los nodos I y J y 0
En otro caso otra forma para interpretar una matriz de adyacencia es como un tipo de datos boléanos .Por ejemplo , en Pascal:
Type grafo: array [ 1….24,1…..24] of bolean
Aquí el grafo [i,j] tiene el valor de trae (verdadero) si existe una arista entre los nodos i y j, y false (falso) en otro caso
Cálculo de aristas
Por lo general es conveniente hacer aritmética en matrices de adyacencia. Por ejemplo, el grado del nodo i en un grafo es:
N
∑ A( i ,j )
J=1
El grado interno de un nodo i en un grafo dirigido es la suma de las columnas de la matriz:
N
∑ A( k ,i )
k=1
Y el grado externo del nodo i es la suma de los reglones de la matriz:
N
∑ A( i ,k )
k=1
Discutiremos otros resultados comunes de la manipulación de datos adyacentes más adelante en el capítulo. Si la matriz de adyacencia se define de tipo booleano , entonces estas manipulaciones comunes no son realmente tan simples. En lugar de sumas, se requiere de una serie de operaciones booleanas ( and y or )
Aristas ponderadas
Existen muchas aplicaciones de grafos en las cuales la matriz de adyacencia es la representación adecuada. Considérese la gráfica que se muestra en la figura 7-9 la cual se puede ser usar en un sistema de información de una compañía de transporte. Este seria un ejemplo de un grafo de aristas ponderadas. Los nodos representan a las ciudades y las aristas representan las trayectorias de tráfico entre las ciudades. Cada arista se etiqueta con la distancia entre un par de ciudades interconectadas. En lugar de usar un matriz de bits para representar este sistema de transporte, podemos usar una matriz de aristas ponderadas
Figura 7-9 Ejemplo de grafo que muestra las distancias entre ciudades
Donde el nodo 1=ABQ 6=HST 11=ORD 16=SPK
2=CVJ 7=KNC 12=PHX
3=DFW 8=LAX 13=SEA
4=DNV 9=NSH 14=SFO
5=ELP 10=NOR 15=SLC
Las aristas ponderadas se usan con frecuencia en aplicaciones de transporte, donde los pesos representan normalmente las distancias, como en las figuras anteriores. En aplicaciones de flujos, los pesos representan las capacidades. Por ejemplo, los nodos en un grafo pueden representar la capacidad en litros por minuto, de una línea de ductos de transporte de líquidos entre diversas localidades, o la capacidad en bits /seg. De comunicación de red de computadora.
En otras aplicaciones, el peso de las aristas representa el tiempo. Por ejemplo, pueden utilizar las graficas para representar redes de actividades, donde cada arista representa una tarea o actividad. Cada nodo representa un evento: la terminación del conjunto de actividades representadas por las aristas que llevan a cada nodo.
Representaciones ligadas
La representación de un grafo,usando la técnica de matriz de adyacencias requiere de almacenamiento de infomación de las aristas, para cada posible par de nodos. P ara una grafica de N nodos, con pocas aristas en relación a las NxN posibles conexiones, una representación ligada resulta ser mas adecuada. La representación ligada solamente almacena la información de las aristas que existen. A medida que las aristas se suman o se borran de la gráfica ligada, se debe modificar la representación en consecuencia. Existen dos tipos fundamentales de estructuras ligadas para representar grafos: una se lama representación de directorio de nodos y la otra representación de multi-lista.
Representación de directorio de nodos
La representación de directorio de nodos incluye dos partes; un directorio y un conjunto de listas ligadas. Hay una entrada en el directorio para cada nodo del grafo. La entrada del directorio para el nodo i apunta a una lista ligada, que representa los nodos que están conectados al nodo i. Cada registro de la lista ligada tiene dos campos; el primero es una identificación del nodo, y el otro es una lista liga al siguiente elemento de la lista. El directorio representa nodos y, la lista ligada representa aristas.
Figura 7-11 Representación de directorio de nodos de la figura 7-7
Un grafo dirigido de orden N con E aristas, requiere de N entradas en el directorio y E entradas de listas ligadas.
La lista ligada encabezada por la i-ésima entrada del directorio corresponde al i-ésimo renglón de la matriz de adyacencia. Las entradas del directorio se ordenan secuencialmente de acuerdo al identificador del nodo. Aunque también hemos ordenado las entradas de la lista ligada según el nodo identificador, podrán haber aparecido en cualquier orden, puesto que cada entrada contiene la identidad del nodo.
Aristas ponderadas
Representar un grafo con aristas ponderadas, requiere reservar espacio en la estructura de datos para el almacenamiento de los pesos. La figura 7-13 muestra un grafo dirigido con aristas ponderadas. Este ejemplo en particular es el de un grafo d actividades: cada nodo representa un evento y cada arista representa una tarea que, al contemplarse ayuda a dispersar el siguiente evento, que inicia otras tareas. Cada peso de arista es su tiempo requerido. Esta clase de grafo es comúnmente usada en sistemas de administración de proyectos.
Una representación de directorio de nodos para este grafo se muestra en la figura 7-14. El registro para cada entrada de arista y un apuntador al siguiente nodo, que tenga el mismo nodo fuente.
NODO PESO SIGUIENTE
Figura 7-14 Representación de direcciones de grafo de la figura 7-13
Cálculo de aristas
Para determinar el gado de un nodo, en un grafo no dirigido, se requiere contar el número de entradas en su lista ligada. El grado externo de un nodo, en un grafo dirigido, también puede ser determinado contando el número de entradas en su lista ligada.
Para facilitar la localización de nodos anteriores y la determinación de los grados internos puede utilizarse un directorio auxiliar de aristas que llegan a los nodos.
Algunos tipos de de análisis de grafos se facilitan mas al usar matrices de adyacencias, en lugar de listas ligadas. Si un grafo tiene una estructura altamente volátil, entonces puede requerir menos trabajo el agregar o borrar aristas en una representación de matriz de adyacencia, que en la de un directorio de nodos. Cambiar una entrada a una matriz es, generalmente mas rapido que agregar (o borrar) otras entradas en una lista ligada.
Representación de multi- lista
Es una representación de multi-lista de estructuras de grafos, hay que considerar de nuevo dos partes: un directorio de información de nodos y un conjunto de listas ligadas de información de aristas. Hay una entrada en el directorio de nodos para cada nodo del grafo. La entrada del directorio para el nodo i apunta a una lista ligada de adyacencia para el nodo i. Cada registro de la lista ligada aparece en dos listas de adyacencia; una para cada nodo en cada extremo de la arista representada. Usando la estructura de datos de la figura 7-15, para cada entrada d la arista (Vp Vj).
NODO 1 NODO 2
ID ADJ ID ADJ
Una representación alternativa, basada en el conjunto de aristas {(2,1),(2,2),(2,3),(3,4),(5,3),(3,6)} se muestra en la figura 7-17. Si el grafo fuera dirigido, no habría tal flexibilidad en la selección de identificadores para las aristas.
Figura 7-16 Representación multi-lista de la figura 7-7
Una declaración en Pascal de una representación multi-lista para un grafo ponderado de orden 24, es la que sigue:
Type id-nodo= 0..24
tipo-nodo= 1 info-arco;
apt-arco= 1 info-arco
info-arco= record nodo-.1: id-nodo;
nodo-2: id-nodo;
lista-adj-1: apt-arco;
lista-adj-2: apt-arco;
peso: integer
End;
Grafo = array [1..24] of tipo ¡-nodo;
Figura 7-17 Otra representación de multi- lista de la figura 7-7
Recorrido de grafos
En muchas aplicaciones es necesario visitar todos los nodos de un grafo por ejemplo; al necesitar imprimir todos los eventos de un grafo de actividades (por ejemplo, figura7-13), o para determinar que ciudades están influidas en un mapa de distancias (figura 7-9), o determinar total entre ciudades. En el mapa de distancias.
Las dos técnicas básicas de recorrido de grafos que representamos aquí son: recorrido en amplitud y recorrido profundidad.
Recorrido en amplitud
En un recorrido de amplitud de grafos, un nodo se selecciona como posición inicial, éste se visita y se marca después, todos los nodos no visitados, adyacentes a ese nodo, visitan y se marcan en algún orden secuencial.
El recorrido en amplitud del grafo (figura 7-13) resulta n le orden siguiente: 1,2,3,4,5,6,7,8. La secuencia 1,3,2,6,5,4,7,8 también es un orden de visita válida para el recorrido en amplitud.
El algoritmo de recorrido utiliza una cola para almacenar los nodos, de cada “nivel” del grafo que se visita. Estos nodos almacenados son tratados uno por uno, luego sus nodos adyacentes son visitados, y así sucesivamente hasta que todos los nodos hayan sido visitados.
El algoritmo puede implantarse en Pascal como sigue:
Type id-nodo= 0... orden-grafo
apt-arco= 1 info-arco
tipo nodo= record marca: 0..1;
lista-ady: apt-arco;
End;
Info-arco= record nodo:id-nod;
Peso: integer;
Sig: apt-arco
End;
Tipo-grafo = array [1..orden-grafo] of tipo-nodo;
Var gráfica: tipo-gráfico;
Primer-nodo:id-nod;
El procedimiento iteractivo puede programarse como sigue:
Procedure amplitud (primer-nodo:id-nodo);
Var: estructura-cola;
Nodo-guardado: id-nodo;
Apt-ady: apt-arco;
Begin {aquí visita al primer nodo}
Grafo[primer-nodo].marca : = 1;
Insertar (primer-nodo);
While g.frente<>0
Do begin suprimir (nodo-guardado);
Apt-ady: =grafo [nodo-guardado].lista-ady;
{Visita el nodo adyacente al nodo-guardado}
While apt-ady <> nil
Do begin nodo-guardado: = apt-ady l .nodo;
If (grafo {nodo-guardado}.marca = 0)
Then begin insertar (nodo-guardado);
{Aquí se visita el nodo-guardado}
Grafo {nodo-guardado}.marca: = 1
End:
Apt-ady : = apt l. sig
End;
End;
End;
Recorrido en profundidad
Mientras que el recorrido en amplitud procede nivel por nivel, el recorrido en profundidad sigue primero una trayectoria desde el nodo inicial hasta un nodo Terminal, después otra trayectoria desde el mismo punto inicial hasta alcanzar otro nodo final, y así sucesivamente hasta que todos los nodos hayan sido visitados.
Una secuencia igualmente válida como resultado del recorrido en profundidad es el siguiente: 1,3,6,7,8,5,4.
El recorrido en amplitud se describió fácilmente usando un procedimiento iteractivo; el recorrido en profundidad conduce hacia una definición recursiva.
El código en Pascal para implantar el recorrido de gráficas en profundidad es como sigue:
Procedure profundidad (var este-nodo: id-nodo)
Var nodo-guardado: id-nodo;
Apt-ady: apt-arco;
Begin {este-nodo es visitado aqui}
Grafo {este-nodo}.marca: = 1;
Apt-ady. = grafo [este-nodo].lista-ady;
While apt-ady <> nil
Do begin nodo-guardado: = apt-ady l.nodo;
If (grafo[nodo-guardado].marca = 0)
Then profundidad (nodo-guardado);
Apt-ady: = apt-ady l.sig
End;
End;
La multiplicación de matrices convencional se usa para encontrar A2. Es decir, el elemento i j-ésima de A2 es el resultado de multiplicar e renglón i por la columna j de A:
El problema de determinar cuando un par de nodos están, o no, conectados, se resuelve entonces encontrando:
N
∑ Ak ,Ak )
k=1
Cuyo resultado es una matriz llamada cerradura transitiva de A, con frecuencia denotada por A. En realidad no se necesita realizar la suma de N veces, donde N es el orden de la gráfica, sino solo tantas veces como la longitud de la trayectoria mas larga. La cerradura transitiva de A es también es denominada como matriz de alcance de A.
Trayectorias más cortas
Además de determinar si el nodo j se puede alcanzar el nodo i es de común interés encontrar la trayectoria mas corta desde el nodo i al nodo j. El desarrollo del algoritmo se deja como ejercicio y solo haremos un par de observaciones acerca de la trayectoria mas corta aquí.
Hay varias rutas posibles entre muchos pares de ciudades. Note que:
1.Las trayectorias mas cortas se detectan en orden no decreciente de sus distancias, es decir, el siguiente nodo destino es aquel con la distancia mínima desde el nodo fuente de todos aquellos nodos que aun no son seleccionados.
2.La trayectoria mas corta al siguiente nodo destino pasa a través de los nodos que ya fueron seleccionados.
S i los pesos de aristas tuviesen que representar costos en lugar de distancias, el mismo algoritmo podría usarse para detectar las trayectorias mas económicas. Si esos pesos representasen velocidades (por ejemplo, kilobits/seg), entonces el algoritmo podría modificarse fácilmente para detectar las trayectorias mas rápidas.
DNV – ABQ 334
DNV – SLC 371
DNV – KNC 558
DNV – ABQ - ELP 334 + 229 =563
DNV – ABQ – PHX 334 + 330 =664
DNV – SLC – SPK - 371 + 550 =921
DLV – SLC – SFO - 371 + 600 =971
DNV - KNC – ORD – 558 + 414 =972
Conclusión
Estamos en una época en la que queremos que las máquinas piensen por nosotros. El esfuerzo que debe realizar la máquina (y su diseñador) es infinitamente superior a la cantidad de trabajo que alivia a cada usuario. Esta tarea de investigación es, sin embargo, necesaria para el desarrollo de la sociedad de la información.
La complejidad del conocimiento crece de manera exponencial a medida que vamos incorporándolo a nuestro saber. Por esto necesitamos aislar un conocimiento de otro y trabajar con cada uno de manera separada y eficiente. Podemos ayudarnos de las máquinas para procesar este conocimiento por nosotros.
Este trabajo nos facilitará en la solución de problemas en la que nos vemos ligados día a día