GRAFOS

GRAFOS

Las estructura de datos no lineales se caracterizan por no
existir una relación de adyacencia, entre sus elementos, es
decir, un elemento puede estar relacionado con cero, uno o
más elementos.
􀂾 Entre las múltiples aplicaciones que tienen estas estructuras
podemos mencionar:
􀂙 Los grafos son estructuras que se utilizan para modelar diversas
situaciones tales como: sistemas de aeropuertos, flujo de tráfico,...
􀂙 Los grafos también son utilizados para realizar planificaciones de
actividades, tareas del computador, planificar operaciones en
lenguaje de máquinas para minimizar tiempo de

DEFINICION

Un grafo G (N, A, f) es un conjunto no vacío de:
􀂙 N={n1, n2, ... , nM) nodos o vértices,
􀂙 A={a1, a2, ..., a K} aristas y
􀂙 la función f : R → Μ × Μ que indica los pares de nodos que están
relacionados.
􀂾 Hay dos tipos de grafos, los dirigidos o digrafos y los no
dirigidos, según que sus relaciones tengan dirección o no,
respectivamente.
􀂾 La representación gráfica de un grafo se define con un
círculo o rectángulo para los nodos y las relaciones con
líneas o flechas según sea un grafo no dirigido o un digrafo,
respectivamente

EJEMPLO
Digrafo, donde D = {N, A, f} tiene
N = {1, 2, 3, 4},
A = {a, b, c, d, e, g, h} y
f(a) = (1, 2), f(b) = (2, 3), f(c) = (1, 3), f(d) = (3, 4),
f(e) = (1, 4), f(g) = (4, 2), f(h) = (4, 1).

CONCEPTOS BASICOS

Se dice que el aj ∈ A asociado al par de nodos ( ni , nj ) donde ni , nj ∈ N,
comienza en ni y termina en nj. Así, ni es el nodo inicial y nj es el nodo
terminal. Ejemplo: si ni = 1, nj = 2 y aj = a en el digrafo D, entonces 1 es
el nodo inicial de a y 2 es el nodo terminal de a.
􀂾 Arco incidente: aj es un arco incidente sobre nk , si nk es el nodo
terminal de aj. Ejemplo: a es el arco incidente sobre 2, pero no sobre 1.
􀂾 Arcos adyacentes: ai y aj son arcos adyacentes si ai y aj son incidentes en
el mismo nodo. Ejemplo: c y b son arcos adyacentes, pero c y d no lo
son.
􀂾 Arcos paralelos: Dos arcos son paralelos si ellos comienzan y terminan
en los mismos nodos. Ejemplo: En D no hay arcos paralelos. Si anexamos
a D el arco p cuya f(p) = (1, 2), entonces a y p son arcos paralelos.

Camino: Un camino C del digrafo D es una secuencia de
arcos (a1, a2, ..., an) tal que para todo par (ai, aj) de arcos
consecutivos en C, el fin de ai coincide con el inicio de aj.
Ejemplo: b, d es un camino, pero a, c no lo es.
􀂾 Camino simple: Es el camino que no recorre el mismo
arco dos veces. Ejemplo: b, d, g es un camino simple, pero
b, d, g, b no es un camino simple.
􀂾 Camino elemental: Es el camino que no visita un mismo
nodo más de una vez. Ejemplo: b, d es un camino
elemental, pero b, d, g no lo es.