Presentado por:
Oscar Leonardo Ramírez
John Freddy Sandoval
Leidy Paola Vera
DEFINICIÓN DE GRAFOS
Un grafo en el ámbito de las ciencias de la computación es
una estructura de datos, en concreto un tipo abstracto de
datos (TAD), que consiste en un conjunto de nodos
(también llamados vértices) y un conjunto de arcos
(aristas) que establecen relaciones entre los nodos.
El concepto de grafo TAD desciende directamente del
concepto matemático de grafo. En este contexto árboles y
grafos se refiere a estructuras de datos que permiten
organizar y mantener información en un computador.
VERTICES
Son los puntos o nodos
con los que esta
conformado un grafo.
Llamaremos grado de un
vértice al número de
aristas de las que es
extremo. Se dice que un
vértice es `par' o `impar'
según lo sea su grado.
ARISTAS
Son las líneas con las que
se unen las aristas de un
grafo y con la que se
construyen también
caminos.
TIPOS DE GRAFOS
Dirigidos: Cada arco No dirigidos: El par de
está representado por un vértices que representa
par ordenado de vértices. un arco no está
ordenado.
REPRESENTACIÓN DE GRAFOS
Las representaciones de grafos más habituales están
basadas en matrices de adyacencia.
Matriz de adyacencia
Se asocia cada fila y cada columna a cada nodo del
grafo, siendo los elementos de la matriz la relación
entre los mismos, tomando los valores de 1 si existe la
arista y 0 en caso contrario.
EJEMPLO
LISTAS DE ADYACENCIAS
Se asocia a cada nodo del grafo una lista que contenga
todos aquellos nodos que sean adyacentes a él.
Ejemplo:
RECORRIDOS DE GRAFOS
Recorrer un grafo significa tratar de alcanzar todos los
nodos que estén relacionados con uno que llamaremos
nodo de salida. Existen básicamente dos técnicas para
recorrer un grafo: el recorrido en anchura y recorrido
en profundidad.
RECORRIDO EN ANCHURA
Supone recorrer el grafo, a partir de un nodo dado, en
niveles, primero los que están a una distancia de un arco
del nodo de salida, después los que están a dos arcos de
distancia, y así sucesivamente hasta alcanzar todos los
nodos a los que se pudiese llegar desde el nodo salida.
Este método comienza visitando el vértice de partida A,
para continuación visitar los adyacentes que no
estuvieron ya visitados. Así sucesivamente con los
adyacentes.
RECORRIDO EN PROFUNDIDAD
Trata de buscar los caminos que parten desde el nodo de
salida hasta que ya no es posible avanzar más. Cuando ya
no puede avanzarse más sobre el camino elegido, se vuelve
atrás en busca de caminos alternativos.
EJEMPLOS DE GRAFOS
En general es una teoría que se usa para solucionar o
buscar alternativas a diferentes problemas o para
visualizar el problema es su conjunto.
Algoritmo de Dijkstra: También llamado algoritmo
de caminos mínimos. Este algoritmo construye el
árbol de caminos de longitud mínima entre un vértice
fijado V y los restantes vértices en un grafo ponderado.
1. Utilizar el algoritmo de Dijkstra para encontrar los
caminos más cortos que van desde el nodo a hasta los
restantes nodos, en el siguiente grafo dirigido partir del
resultado, encontrar cuál es el camino más corto desde a
hasta d.
2. Supongamos que unas líneas aéreas realizan vuelos
entre las ciudades conectadas por líneas la estructura de
datos que refleja esta relación recibe el nombre de grafo.
Algoritmo de Floyd-Warshall
Es un algoritmo de análisis sobre grafos para encontrar
el camino mínimo en grafos dirigidos ponderados.
Compara todos los posibles caminos a través del grafo
entre cada par de vértices. El algoritmo es capaz de
hacer esto con sólo V3 comparaciones (esto es notable
considerando que puede haber hasta V2 aristas en el
grafo, y que cada combinación de aristas se prueba). Lo
hace mejorando paulatinamente una estimación del
camino más corto entre dos vértices, hasta que se sabe
que la estimación es óptima.
