5.2 Representación de los grafo

Matriz de adyacencia

1.    Se crea una matriz cero, cuyas columnas y filas representan los nodos del grafo.

2.    Por cada arista que une a dos nodos, se suma 1 al valor que hay actualmente en la ubicación correspondiente de la matriz.

Si tal arista es un bucle y el grafo es no dirigido, entonces se suma 2 en vez de 1.

Finalmente, se obtiene una matriz que representa el número de aristas (relaciones) entre cada par de nodos (elementos).

Existe una matriz de adyacencia única para cada grafo (sin considerar las permutaciones de filas o columnas), y viceversa.

Matriz de incidencia

1.    Las columnas de la matriz representan las aristas del grafo.

2.    Las filas representan a los distintos nodos.

3.    Por cada nodo unido por una arista, ponemos un uno (1) en el lugar correspondiente, y llenamos el resto de las ubicaciones con ceros (0).

https://sites.google.com/site/matedicreta/6-2-1-matematica

5.21 Matemática

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 gráficas) 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. 

https://sites.google.com/site/matedicreta/6-2-1-matematica

5.22 Computacional

Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos, usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices y aunque frecuentemente se usa una combinación de ambos.

https://sites.google.com/site/matedicreta/6-2-2-computacional

5.3 Algoritmos 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. Los algoritmos de búsqueda en grafos nacen por la necesidad de crear un mecanismo de navegación autónoma, bien sea de robots, coches, o personajes en un videojuego.

http://itpn.mx/recursosisc/1semestre/matematicasdiscretas/Unidad%20VI.pdf

5.31 El camino más corto.

En la Teoría de grafos, el problema de los CAMINOS más cortos es el problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima. Un ejemplo es encontrar el camino más rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representan las ciudades, y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas. Formalmente, dado un grafo ponderado (que es un conjunto V de vértices, un conjunto E de aristas y una función de variable real ponderada f: E → R) y un elemento v ∈ V encuentra un camino P de v a v' ∈ V, tal que: es el mínimo entre todos los caminos que conectan v y v'.

El problema es también conocido como el problema de los caminos más cortos entre dos nodos, para diferenciarlo de la siguiente generalización:

· El problema de los caminos más cortos desde un origen en el cual tenemos que encontrar los caminos más cortos de un vértice origen v a todos los demás vértices del grafo.

· El problema de los caminos más cortos con un destino en el cual tenemos que encontrar los caminos más cortos desde todos los vértices del grafo a un único vértice destino, esto puede ser reducido al problema anterior invirtiendo el orden.

· El problema de los caminos más cortos entre todos los pares de vértices, el cual tenemos que encontrar los caminos más cortos entre cada par de vértices (v, v') en el grafo.

http://itpn.mx/recursosisc/1semestre/matematicasdiscretas/Unidad%20VI.pdf

5.32 A lo ancho.

Búsqueda en anchura es un algoritmo para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación, para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol. Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución.

El algoritmo no usa ninguna estrategia heurística. Sea G = (V, A) un grafo conexo, V’ = V un conjunto de vértices, A’ un vector de arcos inicialmente vacío y P un vector auxiliar inicialmente vacío:

1. Se introduce el vértice inicial en P y se elimina del conjunto.

2. Mientras V’ no sea vacío repetir los puntos 3 y 4. En otro caso parar.

3. Se toma el primer elemento de P como vértice activo.

4. Si el vértice activo tiene algún vértice adyacente que se encuentre en V’: Se toma el de menor índice. Se inserta en P como último elemento. Se elimina de V’. Se inserta en A’ el arco que le une con el vértice activo. Si el vértice activo no tiene adyacentes se elimina de P.

http://itpn.mx/recursosisc/1semestre/matematicasdiscretas/Unidad%20VI.pdf

5.33 En profundidad.

Una Búsqueda en profundidad es un algoritmo que permite recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa, de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado. 

Se comienza en el vértice inicial (vértice con índice 1) que se marca como vértice activo. Hasta que todos los vértices hayan sido visitados, en cada paso se avanza al vecino con el menor índice siempre que se pueda, pasando este a ser el vértice activo. Cuando todos los vecinos al vértice activo hayan sido visitados, se retrocede al vértice X desde el que se alcanzó el vértice activo y se prosigue siendo ahora X el vértice activo.

http://itpn.mx/recursosisc/1semestre/matematicasdiscretas/Unidad%20VI.pdf