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

5.11 Tipos de grafos.

Grafos simples. - Un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Un grafo que no es simple se denomina multigrafo.

Grafo completo. - Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une. El conjunto de los grafos completos es denominado usualmente K, siendo Kn el grafo completo de n vértices. Un Kn, es decir, grafo completo de n vértices tiene exactamente n(n-1) /2 aristas. La representación gráfica de los como los vértices de un polígono regular da cuenta de su peculiar estructura.

Grafos bipartitos.- Un grafo G es bipartito si puede expresarse como G = {V1 U V2, A} (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones: · V1 y V2 son disjuntos y no vacíos. · Cada arista de A une un vértice de V1 con uno de V2. · No existen aristas uniendo dos elementos de V1; análogamente para V2. Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y puzles en los que debe unirse un elemento de la columna A con un elemento de la columna B.

Grafos Planos. - Un grafo G es planar si admite una representación en el plano de tal forma que las aristas no se cortan, salvo en sus extremos. A dicha representación se le denomina grafo plano. Se dice que un grafo es plano si puede dibujarse en el plano de manera que ningún par de sus aristas se corte. A ese dibujo se le llama representación plana del grafo.

Grafo conexo. - Un grafo se dice que es conexo si cada par de sus vértices están conectados. Es decir, G es conexo ⇐⇒ ∀u, v: ∃µ = [u, v] En caso contrario, diremos que G es un grafo desconexo.

Grafos ponderados. - Llamamos grafos ponderados a los grafos en los que se asigna un número a cada una de las aristas. Este número representa un peso para el recorrido a través de la arista. Este peso podrá indicar, por ejemplo, la distancia, el costo monetario o el tiempo invertido, entre otros. Definimos la longitud de un camino en un grafo ponderado como la suma delos pesos de las aristas de ese camino.

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

5.1 Elementos, características y componentes de los grafos.

Un grafo, G, es un par ordenado de V y A, donde V es el conjunto de vértices o nodos del grafo y A es un conjunto de pares de vértices, a estos también se les llama arcos o ejes del grafo. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente a dos vértices.

Los grafos representan conjuntos de objetos que no tienen restricción de relación entre ellos. Un grafo puede representar varias cosas de la realidad cotidiana, tales como mapas de carreteras, vías férreas, circuitos eléctricos, etc. La notación G = A (V, A) se utiliza comúnmente para identificar un grafo.

Los grafos se constituyen principalmente de dos partes: las aristas, vértices y los caminos que pueda contener el mismo grafo.

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