Please enable JavaScript.
Coggle requires JavaScript to display documents.
GRAFOS - Coggle Diagram
GRAFOS
DEFINICIÓN
par (v, w) : v, w ∈ V . Si este par es ordenado, entonces el grafo es dirigido
-
define como un par G = (V, E) V es un conjunto de vértices y E es un conjunto de aristas
grafo no dirigido (w, v) es equivalente a (v, w) por tanto w es adyacente v y v es adyacente a w.
vértice w es adyacente a otro v ⇐⇒ (v, w) ∈ E
grafo secuencia de vértices w1, w2, ..., wn : (wi , wi+1) ∈ E, ∀ 1 ≤ i < n. Si w1 = wn camino cerrado
-
-
IMPLEMENTACIÓN
-
matriz bidimensional, llámese donde para cada arista (u, v) del grafo
hacemos a[u][v] = 1, y si no existe dicha arista a[u][v] = 0
-
usar peso muy grande o muy pequeño (∞, ∞)
-
TIPOS DE PROBLEMAS
-
-
-
-
Variantes
-
∀(u, v) | u, v ∈ V pide encontrar el camino más corto de u a v
de un origen s a todos los posibles destinos d, uno a uno
ÁRBOLES DE EXPANSION
-
dado un grafo conexo y no-dirigido G = (V, E)
-
-
-
OPERACIONES BÁSICAS
Next (v, i): envía el índice posterior a i de entre los vértices adyacentes a v.
Vertex (v, i): envía el vértice cuyo índice i está entre los vértices adyacentes a v
-
LISTA DE ADYACENCIA
-
-
una operación habitual en grafos es encontrar todos los vértices adyacentes consiste en recorrer la lista de adyacencia del vértice en cuestión
-
-