Repaso de Grafos PDF

Algunos conceptos de grafos Análisis de Algoritmos Noviembre de 2024 Definición y componentes de un grafo Matemáticamente: G = {V, A}, donde: Ejemplo: V = {v1, v2, v3, …., vn} (nodos o vértices) V = {0, 1, 2, 3, 4}...

Algunos conceptos de grafos Análisis de Algoritmos Noviembre de 2024 Definición y componentes de un grafo Matemáticamente: G = {V, A}, donde: Ejemplo: V = {v1, v2, v3, …., vn} (nodos o vértices) V = {0, 1, 2, 3, 4} A = {(0,2), (0, 3), (1, 2), (1, 4), (2,0), (2, 1), (2, 3), A = {(vi, vj), vi y vj pertenecen a V} (Aristas) (2, 4), (3, 0), (3, 2), (4, 1), (4, 2)} Graph = Grafo o gráfica Aristas: Arcos o edges 0 3 Una arista es un par ordenado de nodos, donde uno es nodo de partida y el otro es nodo de destino. 2 Se dice que esos dos nodos son adyacentes. 1 4 Arista: Conexión entre un par de nodos Camino: Secuencia de aristas que permiten ir de un nodo hacia otro en el grafo Tipos de grafos Grafos no dirigidos: Grafos dirigidos: Las aristas no tienen una dirección Cada arista si tienen una dirección específica; ambos nodos son inicio específica; uno de los nodos es y fin de la arista. inicio y el otro es fin de la arista. 0 1 0 1 2 3 2 3 A = {(0,1), (1,0), (0,2), (2,0), (0,3),(3,0), (2,3), (3,2)} A = {(0,3), (0,1), (1, 2), (3,0), (3,3)}  Representación de un grafo Matriz de adyacencia Lista de adyacencia Destino G 0 1 2 3 0 1 2 3 0 0 1 1 1 1 0 origen 1 1 0 0 0 2 1 0 0 1 2 0 3 3 1 0 1 0 3 0 2 Grafo representado: A = {(0,1), (1,0), (0,2), (2,0), (0,3),(3,0), (2,3), (3,2)}  Un grafo es ponderado o etiquetado cuando las aristas tienen un valor o peso. El valor de la arista se llama etiqueta y puede representar cualquier cosa: Distancia Grafos ponderados Nombre Valor….  Camino: Secuencia de aristas entre dos puntos o nodos del grafo. Camino simple: De una sola arista. Caminos compuestos: De dos o más aristas consecutivas. Entre cualquier par de nodos puede haber cero, uno o varios caminos. Camino circular: El punto de partida es Conceptos útiles el punto de llegada. Nodo fuente: Aquel nodo del cual parten varias aristas, pero no llega ninguna. Nodos sumidero: Aquel nodo del cual no parte ninguna arista, pero llegan varias. Nodo aislado: Aquel nodo del cual no parten no llegan aristas.