PDF de programación - Grafos

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA

DEPARTAMENTO DE ELECTRONICA
ELO320 Estructuras de Datos y Algoritmos

12/7/2014

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 no tener orientación.

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

• V es un conjunto de puntos, llamados nodos, y
•
• Un enlace {n,m} se puede denotar nm.

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

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 que conectan 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
pueden variar 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 existe como 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 nodo seria 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.
El conjunto 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 caminos son 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 son los 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.

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

nos quedamos con un grafo disconexo (no conexo).

• Un puente es una enlace tal que si lo quitamos nos quedamos con un grafo

disconexo.

• Un conjunto de corte es un conjunto de nodos que al ser eliminado desconecta el

grafo.

3

Completo

• Un grafo completo es un grafo simple en el que cada nodo es adyacente a

cualquier todo otro nodo.
El grafo completo en n nodos se denota a menudo por Kn. Tiene n(n-1)/2 enlaces.

•

Arbol

• Un árbol es un grafo conexo simple acíclico. Algunas veces, un nodo del árbol es

distinguido llamándolo raíz.
Enlaces de los arboles se denominan ramas.

•

Densidad

•

•

•

La densidad es el promedio de los grados de incidencia de los nodos. Si sumamos
los grados de incidencia se tendrá un valor 2E (se cuenta dos veces cada enlace).
Entonces la densidad (D) resulta: D = 2E/V.
Si un grafo tiene una densidad proporcional a V entonces es denso (el numero de
enlaces sera proporcional a V2 en caso contrario es un grafo liviano (sparse).

Subgrafos

• Un subgrafo (S) de un grafo G es un grafo en el cual sus sets de vertices y enlaces

(VS , ES) son subconjuntos de los conjuntos de vertices y enlaces (V, E) de G.

Grafos dirigidos u orientados
En grafos dirigidos se impone un sentido a los enlaces, por ejemplo, si se quiere
representar la red de las calles de una ciudad con sus inevitables direcciones únicas. Los
enlaces son entonces pares ordenados de nodos, con (a,b) ≠ (b,a), como en el ejemplo:
En este grafo hay un enlace en el nodo
(c) que tiene su inicio y termino en el
mismo, es un lazo (o rizo, bucle).
También hay un enlace sin flecha:
significa que el enlace se puede recorrer
en cualquier sentido: es bidireccional,
y corresponde a dos enlaces orientados.
G = (V, E), V = { a, b, c, d, e }, y E = { (a,c), (d,a), (a,e), (b,e), (c,a),(c,c), (d,b) }.
Del vértice d sólo salen enlaces: es una fuente (source). Al vértice e sólo entran enlaces:
es un pozo (sink).

4

Grafos ponderados, con pesos

• Un grafo ponderado asocia un valor (o costo) a cada enlace en el grafo.
•

El peso de un camino en un grafo ponderado es la suma de los pesos de todos los
enlaces atravesados.

Árbol de cobertura (spanning tree) y minimo árbol de cobertura
Dado un grafo conectado, sin dirección, un árbol de cobertura es un sub-grafo (que es
un árbol) que conecta todos los nodos. Un grafo puede
tener muchos posibles arboles de cobertura.

•

•

Si el árbol tiene asignados pesos a cada enlace
entonces se puede calcular un costo a cada
posible árbol de cobertura al sumar el costo de
travesar los enlaces.
El mínimo árbol de cobertura (minimum
spanning tree o MST) es un árbol de cobertura
que tienen un peso menor que o igual al peso de
todos los otros arboles de cobertura posibles.

Ejemplos del uso del MST abundan por ejemplo en Internet cuando de quiere hacer un un
broadcast (transmisión a multiples destinos) las redes de routers calculan el MST y
cuando quieren hacer un broadcast cada router reenvía paquetes a los routers en el MST.
Prim y Kruskal so dos algoritmos comúnmente usados para calcular el MST.

Busca de ruta mínima (routing algorithms)
Muchas veces se quiere encontrar la ruta mínima entre dos nodos en una red. Se
considera una red a un grafo con enlaces orientados y con pesos. Es el caso del Internet
en el cual se quiere determinar la ruta con el mínimo costo para enviar paquetes desde un
origen a un destino. Ya que los terminales están conectados a un router origen el
problema se reduce a determinar rutas de mínimo costo desde un router fuente a un router
destino. El algoritmo Dijkstra comúnmente set utiliza para calcular la ruta de mínimo
costo de un router otros a todos los otros routers de la red.

5

2.Representaciones
Se puede representar un grafo como una matriz de adyacencia, como una lista de
adyacencia o como un conjunto de enlaces.

Matriz de adyacencia
Se emplea una matriz cuadrada (V-1, V-1) donde V
es el número de nodos:

•

•

•

Se coloca un 1 en (v, w) si existe un enlace
de v hacia w; 0 en caso contrario.
La matriz es simétrica si el grafo no es
dirigido.
Si no se aceptan lazos, la diagonal está formada por ceros.

Lista de adyacencia
Para cada nodo (de 0 a V-1) se listan los nodos adyacentes.

0: 1 3 5
1: 0 2 4
2: 1
3: 0
4: 1 5
5: 0 4

Matrices como argumentos

•

•

Si se pasa una matriz a una función, la declaración del argumento debe incluir la
dimensión de la columna.
La dimensión del renglón es irrelevante, ya que se pasa un puntero: f(int m[ ] [4])
ó f(int (*m)[4])

6

Matrices dinámicas en C (Sedgewick)
Declaración de un grafo

struct graph {

int V; //Número de vértices
int E; //Número de enlaces
int **adj; // Matriz de adyacencias

};
typedef struct graph *Graph;

Declaración de un enlace
Un enlace puede describirse por:

typedef struct
{

} Edge;

// nodo inicial. Desde.

int v;
int w; // nodo final. Hasta.

Función para crear un enlace

Edge EDGE(int v, int w)
{

Edge t;
t.v=v;
t.w=w;
return (t);

}

La siguiente definición crea un enlace y EDGE lo inicializa para ir del nodo 1 al 2:

Edge enlace;
enlace= EDGE(1,2);

7

Las variables usadas para la creación de un grafo
Se define un grafo G, cuya matriz de adyacencias se define según un arreglo de r punteros
(filas) para almacenar los arreglos de c enlaces (columnas):

Graph G = malloc(sizeof *G);
int **t = malloc(r * sizeof(int *));
G->adj = t; //Pega el arreglo de punteros
for (i = 0; i < r; i++)

// Crea la cabecera del grafo.
// Crea arreglo de r renglones de punteros

// Crea y pega los renglones de c columnas:

t[i] = malloc(c * sizeof(int));

El siguiente diagrama ilustra las variables.

G



V
E
adj

t

t[i] o *(t+i)

t[i][j] o *(t+i*c+j)

8

Funciones para grafos descritos por su matriz de adyacencias

Funciones para la creación de un grafo vacío con V nodos:

Graph GRAPHinit(int V)
{

Graph G = malloc(sizeof *G);
G->V = V; G->E = 0;
G->adj = MATRIXinit(V, V, 0);
return G;

}

// Crea cabecera del grafo
// Con V nodos y 0 enlaces
// Lo inicia con ceros

MATRIXinit crea la matriz de r renglones, c columnas y la inicializa con val.

int **MATRIXinit(int r