grafos

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA
DEPARTAMENTO DE ELECTRONICA
ELO320 Estructuras de Datos y Algoritmos

23/6/2010

Grafos
Tomás Arredondo Vidal
La teoría de los grafos estudia las propiedades de colecciones de objetos llamados nodos
(o vértices) conectados por vínculos llamados enlaces (varios otros nombres son: arcos,
aristas, elementos). Los enlaces de un grafo pueden o notener orientación.

1.Definiciones
Grafo
Un grafo es un par G = (V, E), donde
•

V es un conjunto de puntos, llamados nodos, y

•

E es un conjunto de pares de nodos, llamados enlaces.

•

Un enlace {n,m} se puede denotar nm.
n

m

Grafos se pueden usar para modelar, estudiar y optimizar muchos tipos de redes y
sistemas por ejemplo: redes de routers en internet, carreteras queconectan ciudades, redes
y circuitos eléctrico, redes de alcantarillados, manejo de proyectos complejos, etc.

Nodos adyacentes
•

Dos nodos son adyacentes si existe solo un enlace entre ellos.

1

Isomorfismos
En la teoría de los grafos, sólo queda lo esencial del dibujo de un grafo. La forma de los
nodos no son relevantes, sólo importan sus enlaces. La posición de los nodos se
puedenvariar para obtener un grafo más claro, y hasta sus nombres se pueden cambiar.
Estos cambios se llaman isomorfismos de grafos. Generalmente, se considera que colocar
los vértices en forma de polígono regular da grafos muy legibles.

Lazos (o bucles)
•
•

Un lazo o bucle en un grafo es un enlace cuyos puntos finales son el mismo
nodo.
Un grafo se dice simple si no tiene lazos y existecomo mucho un enlace entre
cada par de nodos (no hay enlaces en paralelo).

Grado de incidencia (o valencia)
•

El grado de incidencia de un nodo es el numero de enlaces que son incidentes en
el.

•

Si los enlaces tienen dirección entonces el grado entrante es el numero de
enlaces que entran en el nodo.

•

El grado saliente es el numero que sale de el.

•

El grado de un nodoseria la suma de ambos. Un lazo cuenta por dos enlaces en
el calculo de grado de incidencia.

Ejemplo:
Un grafo simple con nodos V = {1, 2, 3, 4, 5, 6} y enlaces E = {{1,2}, {1,5}, {2,3},
{2,5}, {3,4}, {4,5}, {4,6}}.
•
Los nodos 1 y 3 tienen una valencia de 2, los nodos 2,4 y 5 la tienen de 3 y el
nodo 6 la tiene de 1.
•
Los vértices 1 y 2 son adyacentes, pero no así los 2 y 4.
•
Elconjunto de vecinos para un vértice consiste de
aquellos vértices adyacentes a él mismo.
•
El vértice 1 tiene dos vecinos: el vértice 2 y el nodo 5.

2

Camino o Trayectoria
•
•
•
•

Un camino es una sucesión de vértices tal que de cada uno de sus vértices existe
una arista hacia el vértice sucesor.
Se dice que un camino A es simple si no se repite ningún vértice en él.
Dos caminosson independientes si no tienen ningún vértice en común excepto el
primero y el último.
La longitud de un camino es el número de enlaces que tiene el camino. Por
ejemplo, (1, 2, 5, 1, 2, 3) es un camino con longitud 5, y (5, 2, 1) es un camino
simple de longitud 2.

Ciclo o Circuito
•

Un ciclo (o circuito) es un camino que empieza y acaba en el mismo vértice. Los
ciclos de longitud 1 sonlos lazos (o bucles). En el ejemplo, C1 = (1, 2, 3, 4, 5, 2,
1) es un ciclo de longitud 6.

•

Un ciclo simple es un ciclo que tiene como longitud al menos 3 y en el que el
nodo del comienzo sólo aparece una vez más y como nodo final, y los demás sólo
aparecen una vez. En el grafo C2 = (1, 5, 2, 1) es un
ciclo simple.

•

Un grafo se dice acíclico si no contiene ningún ciclo
simple.Conexo o conectado
•

Si es posible formar un camino desde cualquier nodo a cualquier otro en el grafo,
decimos que el grafo es conexo.

•

Un grafo es k-conexo si contiene k caminos independientes entre cualesquiera dos
vértices. El ejemplo es conexo (y por tanto 1-conexo), pero no es 2-conexo.

•

Un punto de articulación (o vertex de corte) es un nodo tal que si lo quitamos...