Ejemplos de Utilización de Grafos en la vida real

Observemos este video explicativo, de como utilizamos la teoria de grafos para la aplicación de casos de la vida real:

En la figura se aplica el Algoritmo de Prim en el grafo, para hallar el árbol, recubrir
mínimo o en otras palabras la ruta optima para ahorrar la distancia del cableado.

Este tipo de grafos son aquellos que se usan en el modelizado de redes neuronales: los llamados grafos Small World o 'de pequeño mundo'.

Como representamos los grafos
Anteriormente mencionamos que existen dos maneras de represetar un grafo, en esta seccion vamos a agregar un poco mas de información acerca de sus tipos de representaciones, y dando un ejemplo.

MATRIZ DE ADYACENCIA

La matriz de adyacencia M es un array de dos dimensiones que representa las conexiones entre pares de vertices. Sea un grafo G con un conjunto de nodos V y de aristas A. Supongamos que el grafo es de orden N, en donde N > = 1. La matriz de adyacencia  M se representa por un Array  N, X  > N donde:

                    1 si existe una arista (Vi, Vj) en Ao, Vi es adyacente a Vj
M(i,j) =        0, en caso contrario

Las columnas y las filas de la matriz representan los vertices del grafo . Si existe una arista desde i a j (esto es, el vertice i es adyacente a j), el peso de la arista de i a j se introduce: si no exite la arista , se introduce un 0; logicamente , los elementos de la diagonal principal son todos ceros , ya que el costo de la arista i a i es 0.

Si G es un grafo no  dirigido , la matriz es simetrica M(i,j) = M(j,i).

LISTA DE ADYACENCIA 

El segundo metodo utilizado para representar un grafo es util cuando un grafo tiene muchos vertices y pocas aristas ; es la lista de adyacencia. En esta representacion se utiliza una lista enlazada por cada vertice V del grafo que tenga vertices adyacentes desde él.

El grafo completo incluye dos partes: un directorio y un conjunto de listas enlazadas . Hay una entrada en el directorio por cada nodo del grafo. La entrada en el  directorio del nodo i apunta a una lista enlazada que representa los nodos que son conectados a i . Cada registro de la lista enlazada tiene dos campos : un identificador del nodo, otro es un enlace al siguiente elemento de la lista ; la lista enlazada representa arcos.

Un Ejemplo 

Analisis del problema:

Se trata de una función recursiva que compara nodo a nodo la informacion almacenada en ambos árboles. Las condiciones de salida del proceso recursivo seran :

*Que se termine de recorrer uno de los dos arboles.

*Que terminen de recorrer ambos.

*Que encontremos diferente informacion en los nodos comparados.

Si los arboles terminaron de recorrerse simultaneamente es que ambos tienen el mismo número de nodos y nunca ha sido diferente  la informacion comparada; por lo tanto, la funcion devolvera verdad ; en otro caso devolvera falso.

funcion iguales (E:punt; raiz1; raiz2)

inicio

       si (raiz1 = nulo) Entonces

           si (raiz2 = nulo) Entonces

                    devolver (verdad)

           fin-si

       si-no

            si (raiz2 = nulo) Entonces 

                   devolver (Falso)

           si-no

                 si (raiz1----.elemento <> raiz2 ----.elemento)  Entonces

                          devolver (Falso)

                 si-no

                        devolver (iguales (raiz1----.Izquierdo, raiz2----.Izquierdo))

                                       (iguales (raiz1.----Derecho, raiz2------.Derecho))

                  fin-si

       fin-si

fin.

ALGUNAS IMPLEMENTACIONES

Búsqueda en amplitud o anchura 

struct tcola *cola;
void visitar(int k) // listas de adyacencia
{
  struct nodo *t;
  encolar(&cola,k);
  while (!vacia(cola))
  {
    desencolar(&cola,&k);
    val[k]=++id;
    for (t=a[k]; t!=z; t=t->sig)
    { 
      if (val[t->v]==0)
      {
        encolar(&cola,t->v);
        val[t->v]=-1;
      }
    } 
  }
}

Búsqueda en profundidad 

int id=0;
int val[V];

void buscar()
{
  int k;
  for (k=1; k<=V; k++)
    val[k]=0;
  for (k=1; k<=V; k++)
    if (val[k]==0) visitar(k);
}

void visitar(int k) // matriz de adyacencia
{
  int t;
  val[k]=++id;
  for (t=1; t<=V; t++)
    if (a[k][t] && val[t]==0) visitar(t);
}

void visitar(int k) // listas de adyacencia
{
  struct nodo *t;
  val[k]=++id;
  for (t=a[k]; t!=z; t=t->sig)
    if (val[t->v]==0) visitar(t->v);
} 

en JAVA

Recorrido en Anchura

public String

toStringBFS

{(return array To String (toArrayBFS( )) ;}

}

public int[ ]

to Array BFS ( )
{

int res[ ] = new int [numVertices( ) +  1 ];

visitados = new int [numVertices( ) + 1];

ordenVisita = 1;

q = new Array Cola < Integer > ( );

for ( int i = 1; i <= numVertices( ); i++ )

if (visitados[i] == 0) toArrayBFS(i, res);

return res;

}

Implementaciones en Pseudo

campo convexo
se trata de determinar si un grafo no dirigido es convexo o no

funcion campoconvexo (g:es grafo) dev (g:es grafo; n: es natural)
{pre: g es un grafo no dirigido}
PARA cada V perteneciente a V hacer
    V.visitado:= 'no visto'; v.ncc:= 0
fin-para
nc:=0;
PARA cada V pertn V hacer
    Si V.visitado = 'No visto' entonces
        nc:= nc + 1;
        g:= conexo (g, v, nc)
    fin.si
fi-para
devolver (g, nc);
fin.

Pseudo para numerar vertices

función NUMERAR_VERTICES (g es grafo)  dev  (g es grafo)
{Pre: g es un grafo no dirigido}
Para cada v pert a  V hacer
         v.visitado:=‘no_visto’; v.num-dfs:=0; v.num-invdfs:=0;
fin-para
ndfs:=0;
ninv:=0;
Para cada v pert a   V hacer
         si (v.visitado=’no visto’) entonces
               (g,ndfs,ninv):=NV_1 (g,v,ndfs,ninv);
        fin-si
fin-para
dev (g);
fin.

CICLO

Pseudo para ir desde la raiz al vertice actual, si un vertice aparece mas de una vez ese camino hay ciclo

Funcion Ciclo (g: es grafo) devolv (B: es boolean)
{Pre: g es un grafo dirigido}
Para cada v pert a V  Hacer
       v.visitado:= 'no_visto';
        v.en_camino:= FALSO:
    {no hay ningun vertice en el camino de la raiz al vertice actual}
fin-para
b:=falso:
Para cada v pert a V Hacer
     si ( v.visitado = 'no_visto')  entonces
         (g, b1):= ciclos_1(g,v)
         b:= b1 v B;
    fin-si
fin-para
{los vertices del grafo han sido recorridos según el orden de recorrido en profundidad y b= ciclico(G)}
devolv (b);
fin.

HERRAMIENTAS

HERRAMIENTAS PARA CONOCER Y COMPRENDER COMO FUNCIONAN LOS GRAFOS:

"Grafos" es una herramienta informática para la construcción, edición y análisis de grafos que pretende ser de utilidad para la docencia, aprendizaje y práctica de la teoría de grafo. Es desarrollada por Alejandro Rodriguez Villalobos (Dpto. de Organización de Empresas. Escuela Politécnica Superior de Alcoy. Universidad Politécnica de Valencia), esta desarrollada en un entorno Visual Basic 2005, el codigo implementado en .NET 2005.

Disponible en (http:// http://arodrigu.webs.upv.es/grafos/doku.php?id=software)

"GeoGebra" es un software de matemáticas dinámicas para todos los niveles educativos que reúne geometría, álgebra, hoja de cálculo, gráficos, estadística y cálculo en un solo programa fácil de usar. GeoGebra es también una comunidad en rápida expansión, con millones de usuarios en casi todos los países. GeoGebra se ha convertido en el proveedor líder de software de matemática dinámica, apoyando la educación en ciencias, tecnología, ingeniería y matemáticas (STEM: Science Technology Engineering & Mathematics) y la innovación en la enseñanza y el aprendizaje en todo el mundo.

• Conectamos geometría, álgebra y hoja de cálculo de forma completamente dinámica
• Interfaz muy fácil de usar, a pesar de contar con poderosas herramientas
• Herramienta de autoría para crear materiales de aprendizaje interactivos como páginas web
• Disponible en varios idiomas, para nuestros millones de usuarios en todo el mundo
• Software de código abierto disponible gratuitamente para usos no comerciales

Disponible en (http://www.geogebra.org/download)

!Comencemos¡
¿Que es un Grafo?

El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos podrían ser: un gráfico de una serie de tareas a realizar, grafos matematicos que representan las relaciones binarias,una red de carreteras, la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad, una red de trabajo en un oficina. En cada caso,es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos(vértices)con líneas conectándolos (arcos). 

Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Su estudio podría dividirse en dos grandes b
loques:

• Grafos Dirigidos.
• Grafos no Dirigidos(pueden ser considerados un caso particular de los anteriores).

 A la hora de diseñar el TDA grafo hay que tener en cuenta que hay que manejar datos correspondientes a sus vértices y aristas,  pudiendo cada uno de ellos estar o no etiquetados. Además hay que proporcionar operaciones primitivas que permitan manejar el tipo de dato sin necesidad de conocer la implementación. Así,los tipos de datos que se usarán y las operaciones primitivas consideradas son las siguientes: 

Los nuevos tipos aportados por el TDA grafo son los siguientes:

• grafo.
• vertice.
• arista.

Representación de grafos

Una característica especial en los grafos es que podemos representarlos utilizando dos estructuras de datos distintas. En los algoritmos que se aplican sobre ellos veremos que adoptarán tiempos distintos dependiendo de la forma de representación elegida. En particular, los tiempos de ejecución variarán en función del número de vértices y el de aristas, por lo que la utilización de una representación u otra dependerá en gran medida de si el grafo es denso o disperso.

Para nombrar los nodos utilizaremos letras mayúsculas, aunque en el código deberemos hacer corresponder cada nodo con un entero entre 1 y N (número de vértices) de cara a la manipulación de los mismos.

Representación por matriz de adyacencia

Es la forma más común de representación y la más directa. Consiste en una tabla de tamaño N x N, en que la que a[i][j] tendrá como valor 1 si existe una arista del nodo i al nodo j. En caso contrario, el valor será 0. Cuando se trata de grafos ponderados en lugar de 1 el valor que tomará será el peso de la arista. Si el grafo es no dirigido hay que asegurarse de que se marca con un 1 (o con el peso) tanto la entrada a[i][j] como la entrada a[j][i], puesto que se puede recorrer en ambos sentidos.

Representación por lista de adyacencia

Otra forma de representar un grafo es por medio de listas que definen las aristas que conectan los nodos. Lo que se hace es definir una lista enlazada para cada nodo, que contendrá los nodos a los cuales es posible acceder. Es decir, un nodo A tendrá una lista enlazada asociada en la que aparecerá un elemento con una referencia al nodo B si A y B tienen una arista que los une. Obviamente, si el grafo es no dirigido, en la lista enlazada de B aparecerá la correspondiente referencia al nodo A.

Las listas de adyacencia serán estructuras que contendrán un valor entero (el número que identifica al nodo destino), así como otro entero que indica el coste en el caso de que el grafo sea ponderado

 A la hora de explorar un grafo, nos encontramos con dos métodos distintos. Ambos conducen al mismo destino (la exploración de todos los vértices o hasta que se encuentra uno determinado), si bien el orden en que éstos son "visitados" decide radicalmente el tiempo de ejecución de un algoritmo, como se verá posteriormente.

En primer lugar, una forma sencilla de recorrer los vértices es mediante una función recursiva, lo que se denomina búsqueda en profundidad. La sustitución de la recursión (cuya base es la estructura de datos pila) por una cola nos proporciona el segundo método de búsqueda o recorrido, la búsqueda en amplitud o anchura.

 Algunos conceptos Claves

Grafos no dirigidos
Grado de un vertice: número de arista que lo contienen.

 

Grafos dirigidos:

Grado de salida de un vertice V: número de arcos cuyo vertice inicial es V

Grado de entrada de un vertice V: Número de vertices cuyo vertice final es V.

Nodos/vertices adyacentes: arcos/aristas con un vértice común.

 Bucle: arco/arista cuyo vértice inicial y final coinciden.

Camino: sucesión de arcos adyacentes tal que el vertice final de cada arco coincide con el inicial del siguiente.

Circuito o ciclo: camino que acaba y comienza con el mismo vertice.

Grafo conexo: un grafo no dirigido es un grafo conexo si para todo par de nodos U y V existe un camino de U a V.

Componentes conexas: cada uno de los conjuntos maximales conexos. 

 

TIPOS DE GRAFOS:

 Grafo Etiquetado: cada arista o vertice tiene asociado una etiqueta o valor.

Grafo Ponderado (grafo con pesos): grafo etiquetado en el que existe un valor numerico asociado a cada arista o arco.

Multigrafo: grafo en el que se permite que entre dos vertices exista mas de un arista o arco.

Arbol: grafo conexo que no tiene ciclos.