Grafos-conceptos

2. Introducción
2.1 Definición de Grafos
Un Grafo es una estructura de datos que representa información de una manera no lineal ni jerárquica. Estos elementos son la representación adecuada de problemas específicos. Ejemplos de estos problemas pueden ser los mapas de carreteras, las rutas de vuelos entre ciudades de una aerolínea, diagramas de circuitos o diagramas de flujos. Su importanciaestá en las conexiones o relaciones que muestran entre diversas partes del diagrama.

Inicio

s=0

320 250

280

1.0 0.4

A
0.4 0.2

B

t = 2s
240 270 290

0.7 200 0.2

F

C t>10 V t
180

D
0.3

(c)

(b)

Fin

(a) Figura 1

La figura 1 muestra varios tipos de diagramas de grafos, (a) muestra un diagrama de flujo de un programa sencillo, (b) representa cincoalmacenes de una compañía de transporte y las rutas que los unen, con indicaciones de las respectivas distancias. (c) muestra la probabilidad que tiene una rata puesta en una de cuatro jaulas de moverse a cualquiera de las otras tres o permanecer en su jaula. Cada grafo consta de una colección de objetos (rectángulos, círculos o puntos) y líneas que los unen. Algunas veces las líneas tienen dirección,es decir, tiene una punta de flecha que indica hacia donde fluye la ruta, otras veces los objetos y líneas están etiquetados.

Lo más importante de un grafo son sus objetos y líneas. Por ejemplo, en la figura 1(b), los objetos representados por puntos se llaman vértices, y las líneas que los unen se llaman arcos o aristas. El grafo de la figura 1(b) tiene cinco vértices y ocho arcos. En lafigura 1(c), los arcos que unen el vértice A con el vértice B se llaman arcos múltiples o paralelos. Y el arco que une el vértice B con el mismo se llama lazo. En la teoría de grafos, lo que interesa son los arcos que se unen para formar un camino. Para ilustrarlo, se tiene la figura 2(a), similar a la figura 1(c) pero con sus vértices y arcos etiquetados de otra forma. Como ejemplos de caminos setiene d b f e en la figura 2(b), y c f e b a en la figura 2(c). La figura en si no dice de qué camino se está hablando: la figura 2(c) también presenta los caminos b a f e c y c a f e b. En los caminos se permite la repetición de arcos: b a b e f a a b es un camino. La Longitud de un camino es la cantidad de arcos que tiene. Entonces, b a b e f a a b tiene longitud 8.
a V b W c d e f d e f e V b W Vb a

W c f

X (a)

Y

X (b)

Y

X (c)

Y

Figura 2

Los arcos adyacentes en un camino tienen un vértice común. Por tanto, un camino determina una sucesión de vértices. Las sucesiones de vértices correspondientes a los caminos antes mencionados son: Camino dbfe cfeba bafec cafeb Sucesión de vértices XVWYV VWYV W W VWWYVW VWWYVW

Camino babefaab

Sucesión de vértices VWWVYWWWVHay que tener en cuenta el siguiente detalle. El número de vértices en una sucesión de vértices, supera en uno al número de arcos en un camino. Cuando hay un lazo en el camino el vértice se repite en la sucesión. En la sucesión de vértices no se distinguen arcos paralelos, por lo que dos caminos distintos como b a f e c y c a f e b tienen la misma sucesión de vértices. Cuando un grafo no tienearcos paralelos ni lazos, entonces la sucesión de vértices determina el camino de manera única. En ese caso, se pueden describir los arcos enlistando los dos vértices que conectan un camino por la sucesión de vértices. Un camino es camino cerrado si el primero y último vértice de la sucesión de vértices son el mismo. En la figura 2(a), algunos caminos cerrados son b a b e f a a b y d c f e d,cuya sucesión de vértices es X V W Y V X y f e b con sucesión W Y V W. Un ciclo es un camino cerrado “eficiente” en el sentido de que no repite arcos y en la sucesión de vértices, todos son distintos, excepto el primero y el último. Por tanto, f e b es un ciclo. El camino cerrado d c f e d repite el arco d y en su sucesión de vértices X V W Y V X se repite el vértice V. El camino cerrado c a f e...