Algoritmo de recorrido y búsqueda

Recorrer un grafo significa tratar de alcanzar todos los nodos que estén relacionados con uno que llamaremos nodos de salida. Existen básicamente dos técnicas para recorrer un grafo: el recorrido en anchura y el recorrido en profundidad.

Así, para recorrer un grafo consiste en visitar todos los vértices alcanzables a partir de uno dado. Hay dos formas.

·         Recorrido en profundidad (DFS)

·         Recorrido en anchura (BFS)

Recorrido en anchura

El algoritmo de recorrido en anchura o BFS, explora sistemáticamente todas las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices más cercanos a un nodo inicial.

Para la implementación de este algoritmo se utiliza globalmente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el recorrido. El algoritmo BFS requiere también un vector de cola auxiliar para gestionar los vértices no visitados.

En muchos casos es necesario ejecutar este algoritmo empezando en los nodos más alejados del nodo escogido como nodo inicial.

Recorrido en profundidad

El algoritmo de recorrido en profundidad o DFS, explora sistemáticamente las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices adyacentes a los visitados más recientemente. De esta forma se va "profundizando" en el grafo, es decir, alejándose progresivamente del nodo inicial [2]. Esta estrategia admite una implementación simple en forma recursiva, utilizando globalmente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el orden del recorrido.

ALGORITMO DE BUSQUEDA

Un algoritmo de búsqueda es un algoritmo cuyo propósito es encontrar todos los vértices de un grafo G= (V, E) que satisfacen un propiedad particular. Diferentes variables de un algoritmo de búsqueda aparecen en una gran variedad de problemas. Un vértice está marcado si se sabe que es alcanzable desde el origen. Sea X el conjunto de los vértices marcados  y  Y el conjunto de los vértices no marcados (Y= V- X). Inicialmente X consta de solamente del vértice “r”. Se observa que si uE Y y uV E e, entonces se pueden marcar v. Un algoritmo de búsqueda recorre los vértices marcados en cierto orden. Se escribe ord (u) para indicar el orden de u en el recorrido.

El camino más corto

Una gráfica con pesos es una gráfica en la cual se asignan valores a las aristas y que la longitud de una ruta (camino) en una gráfica de pesos es la suma de los pesos de las aristas en la ruta. Sea w (i, j) el peso de la arista (i, j). En la graficas con pesos, con frecuencias queremos determinar la ruta más corta(es decir, un camino de longitud mínima) entre dos vértices dados.

Algoritmo de Dijkstra

El algoritmo de Dijkstra determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. Algunas consideraciones:

§  Si los pesos de mis aristas son de valor 1, entonces bastará con usar el algoritmo de BFS.

§  Si los pesos de mis aristas son negativos no puedo usar el algoritmo de Dijsktra, para pesos negativos tenemos otro algoritmo llamado Algoritmo de Bellmand-Ford.

Referencias:

Callejas Aboytes Ariana, S. V. (n.d.). Algoritmos de Recorrido y Búsqueda. Retrieved from Instituto Tecnológico de Querétaro, Matemáticas Discretas: http://trabajoenequipoitq.wixsite.com/matematicas-discreta/63-algoritmos-de-bsqueda

Hernandez, B. C. (n.d.). Algoritmos de recorrido y busqueda. Retrieved from SCRIBD: https://www.scribd.com/document/190139396/Algoritmo-de-recorrido-y-busqueda

Representación de los grafos

                          

El uso de matrices para representar sistemas de ecuaciones, relaciones  o grafos permite una rápida y clara manipulación de la información, así como el determinar algunas propiedades de los grafos que de otra manera serían más difíciles de obtener. Además de esto se tiene que en la computadora es más fácil el manejo de matrices, ya que se pueden tratar como arreglos o listas doblemente ligadas.

A continuación se describen las representaciones matriciales de los grafos.

•          Matriz de adyacencia (Ma)

Es una matriz cuadrada en la cual los vértices del grafo se indican como filas y como columnas: el orden de los vértices es el mismo que guardan las filas y las columnas de la matriz. Se coloca un 1 como elemento de la matriz cuando existe una relación entre uno y otro vértice, o bien un 0 cuando no exista relación alguna.

•          Matriz de incidencia (Mi)

En esta matriz se colocan los vértices del grafo como filas y las aristas como columnas.

Representación Matemática y Computacional de los grafos

En matemáticas y ciencias de la computación, la teoría de grafos, también llamada teoría de las gráficas estudia las propiedades de los grafos (también llamados graficas) Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de partes de vértices llamados aristas. 

Matemáticamente, la representación de un grafo G (V, A) es a través de una matriz M, de n x n con lo cual representamos el valor ponderado de la aristas a_ij en la entrada (i, j) de la matriz M. 

Computacionalmente un grafo se representa como una matriz de ceros y unos. Donde un cero en la posición (i, j) representa que hay camino del vértice i al vértice j y un uno, que si hay camino. En programación, una matriz se representa como un arreglo bidimensional.

Referencias:

MURILLO, J. A. (2009). Grafos. In J. A. MURILLO, Matemáticas para la computación (pp. 292-294). México: Alfaomega.

Ramírez, M. (2005, Septiembre 01). Retrieved from http://www.cimat.mx/~amor/Omi/Entrenamiento/Grafos/Capitulo1.htm

Elementos, características y componentes de los grafos

¿Qué es…?

Un grafo G es un conjunto no vacío V (de vértices) y un conjunto A (de aristas) extraído de la colección de subconjuntos de dos elementos de V. Una arista de G es, pues, un subconjunto {a, b}, con a, b ∈ V, a = b.

Un grafo (G) es un diagrama que consta de un conjunto de vértices (V) y un conjunto de lados (L).

•          Vértices (nodos)

Se indican por medio de un pequeño círculo y se les asigna un número o letra.

•          Lados (ramas o aristas)

Son las líneas que unen un vértice con otro y se les asigna una letra, número o una combinación de ambos.

•          Lados paralelos

Son aquellas aristas que tienen relación con un mismo par de vértices.

•          Lazo

Es aquella arista que sale de un vértice y regresa al mismo vértice

•          Valencia de un vértice

Es el número de lados que salen o entran a un vértice.

Tipo de Grafos

•          Grafos simples

Son aquellos grafos que no tienen lazos ni lados paralelos.

•          Grafo completo de n vértices (Kn)

Es el grafo en donde cada vértice está relacionado con todos los demás, sin lazos ni lados paralelos. Se indica como Kn, en donde n es el número de vértices del grafo.

•          Complemento de un grafo (G ')

Es el grafo que le falta al grafo G, de forma que entre ambos forman un grafo completo de n vértices. Este grafo no tiene lazos ni ramas paralelas.

•          Grafo bipartido

Es el grafo que está compuesto por dos conjuntos de vértices, A = {a1, a2, a3..., an} y B = {b1, b2,…., bm} en donde los elementos del conjunto A se relacionan con los del conjunto B, pero entre los vértices de un mismo conjunto no existe arista que los una.

•          Grafo bipartido completo (Kn> m)

Es el grafo que está compuesto por dos conjuntos de vértices, uno de ellos

A = {a1, a2, a3,..., an} y otro B = {b1, b2,..., bm], y en el que cada vértice de A esta unido con todos los vértices de B, pero entre los vértices de un mismo conjunto no existe arista que los una. El grafo bipartido completo se índice como Knm.

Referencias:

Murillo, J. A. (n.d.). Matemáticas para la computación. In J. A. Murillo, Matemáticas para la computación (pp. 287-292). México: Alfaomega.