UNIVERSIDAD NACIONAL DE INGENIERIA
SEDE : UNI-NORTE
INVESTIGACION DE OPERACIONES II
Teoría de Grafos
Maestro
Ing. Julio Rito Vargas Avilés
I semestre 2009
GRAFOS

Introducción

Definición de grafo

Conceptos importantes

Grafos dirigidos

Grafos no dirigidos

Ejemplos
2
GRAFOS
La Teoría de Grafos nace del análisis sobre una inquietud
presentada en la isla Kueiphof en Koenigsberg
(Pomerania) ya que el río que la rodea se divide en dos
brazos.
Sobre los brazos estaban construidos siete puentes y para
los habitantes era motivo de distracción descubrir un
itinerario de manera que pudieran regresar al punto de
partida, después de haber cruzado por los siete puentes
pero pasando sólo una vez por cada uno de ellos.
3
GRAFOS





Es un conjunto de vértices o nodos y un conjuntos
de arcos. Se representa por G = (V, A). G, grafo;
V, vértice y A, arco.
Es una estructura no lineal que representa un conjunto
de objetos donde no hay restricción a la relación entre
ellos.
Es un concepto matemático que se utiliza para
representar circuitos eléctricos, redes transporte,
de alcantarillado, redes de comunicaciones, mapa
de carreteras, etc.
La teoría de los grafos se aplica en el estudio de
problemas complejos que surgen en áreas como
la informática, investigación operativa, química,
ingeniería eléctrica, etc.
Los grafos se clasifican en dirigidos y no dirigidos.
4
GRAFOS
Bogotá
1.500 kms
Brasilia
800 kms
Lima
900 kms
Montevideo
Santiago
2.000 kms
Buenos Aires
G = (V, A)
V(G) = nodos o vértices
(ciudades)
A(G) = arcos o aristas
(medio de conexión)
5


Un grafo es dirigido si los pares de nodos
que forman los arcos son ordenados,
es decir, un nodo puede ser
apuntado por otros nodos,
se representa con u v
El conjunto de vértices
V = {C,D,E,F,H} y
el conjunto de arcos
A = { (C,D), (D,F),
(E,H), (H,E), (E,C) }
forman el grafo dirigido G = {V, A}.
6


Un grafo no dirigido es el que tiene los arcos
formados por pares de nodos no ordenados,
un nodo está relacionado con otro nodo, se
representa con u v
El conjunto de vértices
V = {1,4,5,7,9}
y el conjunto de arcos A = { (1,4),
(5,1), (7,9), (7,5), (4,9), (4,1),
(1,5), (9,7), (5,7), (9,4) } forman
el grafo no dirigido
G = {V, A}.
7
GRAFOS
Vértice
Longitud de un camino
Arista
Grafo completo
Camino simple
Grafo Valorado
Grafo conexo
Grado de un nodo
Bucle
Orden
8







Vértice: también es llamado nodo.
Arista: es la conexión de un nodo con otro adyacente.
Camino: secuencia de aristas recorridas para ir desde
un nodo origen hasta uno destino.
Un camino simple es un camino desde un nodo a otro
en el que ningún nodo se repite (no se pasa dos
veces). Si el camino simple tiene como primer y último
elemento al mismo nodo se denomina bucle.
Longitud de un camino: es el número de arcos que
componen el camino.(es la suma de los valores
numéricos asociados a los arcos que lo constituyen)
Bucle: camino que une un nodo consigo mismo.
Comienza y termina en el mismo nodo.
Orden: es el número de nodos (vértices) del grafo.
9




Nodos Adyacentes: dos nodos son adyacentes si
comparten la misma arista.
Grado de un nodo x: en un grafo no dirigido, es el
número de aristas que contiene a x. En un nodo
dirigido grado de entrada, es el número de arcos
que llegan a x, y grado de salida es el número de
arcos que salen de x.
Grafo valorado: cuando los arcos tienen asociados
un factor de peso.
Grafo conexo: es un grafo no dirigido tal que para
cualquier par de nodos existe al menos un camino
que los une.
10





Grafo finito: un grafo es finito si su numero de
nodos es finito.
Multigrafo: es un grafo con varias aristas entre
sus nodos.
Grafo regular: un grafo es regular si todos sus
nodos tienen el mismo grado.
Un camino es cerrado si sus nodos extremos
coinciden. Un ciclo es un camino cerrado.
Grafo fuertemente conexo: es un grafo dirigido tal que
para cualquier par de nodos existe un camino que los une.
11


Según el número de aristas que contiene, un
grafo es completo si cuenta con todas las aristas
posibles (es decir, todos los nodos están
conectados con todos), disperso si tiene
relativamente pocas aristas y denso si le faltan
pocas para ser completo.
El número de distintos pares de vértices (v(i), v(j)),
con v(i) <> v(j), en un grafo con n vértices es
n*(n-1)/2. Este es el número máximo de arcos en
un grafo no dirigido de n vértices. Un grafo no
dirigido que tenga exactamente n*(n-1)/2 arcos
se dice que es un grafo completo.
En el caso de un grafo dirigido de n vértices el
número máximo de arcos es n*(n-1).
12
Grafo conexo: es un grafo no dirigido tal
que para cualquier par de nodos existe al
menos un camino que los une.
Grafo fuertemente conexo: es un grafo
dirigido tal que para cualquier par de
nodos existe un camino que los une.
13
Grafo valorado: cuando los arcos
tienen asociados un factor de peso.
Grafo valorado dirigido: cuando
los arcos tienen asociados un
factor de peso.
14
GRAFOS
 Los nodos c y e tienen grado 4, el
nodo d tiene grado 6 y los demás
nodos tiene grado 5
Existe un lazo o bucle en el nodo d
Es multigrafo ya que existen dos
aristas que unen los vértices a y b
a
b
Existen varios caminos que unen el
nodo a y el nodo d Ej. a-b-c-d-a, ae-d , a-d o a-c-d
El camino a-c-d-a es un camino
cerrado
El camino a-c-d-a es un camino
simple, mientras que a-c-b-d-c no
lo es.
e
c
El camino a-c-d-a es un camino
cíclico
No es un Grafo conexo ya que todos
los nodos no tienen
un camino a
otro nodo
d
f
No es un Grafo completo ya que
todos los nodos no se conectan con
los demás
El nodo f es un nodo aislado
15
Descargar

Grafo - MSc. Ing. Julio Rito Vargas Avilés