GRAFOS1

Vista previa del material en texto

1
Grafos
Rafa Caballero - Matemática Discreta - UCM 06
1
2
Introducción
Origen etimológico: trazar
Representación gráfica: conjunto de puntos (vértices) conectadas con líneas (arcos)
Un grafo es un objeto combinatorio: un conjunto de vértices y un conjunto de arcos tomado de entre el conjunto de todos los arcos posibles que unen cada par de vértices 
Un grafo es una estructura de datos no lineal, dinámica
1
4
2
7
3
6
5
b
e
a
d
c
Ejemplo 1
Ejemplo 2
3
Definiciones y terminología
Un grafo G es un conjunto en el que hay definida una relación binaria G=(V,A) donde:
V ={v1,…,vn} es un conjunto de vértices
A = {e1,…,em} es un conjunto de aristas o arcos,
con cada ek  (vi, vj), con vi, vj  V, vi ≠ vj
Si x, y  V puede ocurrir:
(x, y)  A x, y están unidos con un arco
(x, y) no está en A, x, y no están unidos 
Ejemplo: G = (V,A)
V = {a, b, c, d }
A = {(a, b), (b, c), (a, c), (a, d), (d, b) }
4
Tipos de Grafos
Ejemplo: red de computadoras
5
Tipos de grafos
Un mismo grafo puede tener diferentes representaciones gráficas
Ejemplo:
 
Dos representaciones del mismo grafo
G = ({a, b, c, d, e, f},{{a, b},{a, e},{a, f}{e, f},{b, c}, {c, d},{e, d},{d, f}})
6
Tipos de Grafos
Si el orden influye en la aristas se habla de grafos dirigidos:
Si las aristas tienen asociada una dirección el grafo es dirigido: las aristas (x, y) y (y, x) no son equivalentes
Caso contrario, si (x, y)=(y, x) el grafo es no dirigido
7
Tipos de Grafos
Si se permite que haya más de una arista entre dos vértices se habla de multigrafos:
8
Tipos de Grafos
Las aristas o los vértices pueden tener asociada información (etiquetas).
Si la etiqueta es un número, se llama peso, costo o longitud y el grafo es ponderado o etiquetado
9
Tipos de Grafos
Un grafo dirigido es simétrico si para toda arista (x, y)  A, la arista (y, x) tambíen  A.
Un grafo dirigido es antisimétrico si dada una arista (x, y)  A implica que (y, x) no pertenece a A.
El vértice x es incidente al vértice y si hay un arco que va de x a y: (x, y)  A, x es el origen del arco, y es el extremo del arco. También y es adyacente a x. 
En grafo no dirigido si x es adyacente a y, entonces y también es adyacente a x. 
10
Conceptos Básicos
Dos arcos son adyacentes si tienen un vértice común que es origen de uno y extremo del otro
Camino de un grafo es una sucesión de arcos adyacentes
C= {(v1,v2),(v2,v3),…(vk,vk+1) para vi  A}
Longitud del camino es el número de arcos que comprende, en grafos ponderados es la suma de los pesos de los arcos que lo forman.
El grado de entrada de un vértice v, gr(v) es el número de arcos incidentes en v. El grado de salida de un vértice v es el número de arcos adyacentes a el.
11
Conceptos Básicos
Ejemplo:
12
Conceptos Básicos
Camino simple si sus arcos son distintos
Camino elemental si no utiliza un mismo vértice dos veces
Camino Euleriano es simple y contiene todos los arcos del grafo.
Circuito (ciclo en grafos no dirigidos) es camino en el que coinciden los vértices inicial y final.
Circuito simple, con arcos distintos
Circuito elemental, con vértices distintos
Longitud del circuito es el número de sus arcos
13
Conceptos Básicos
Bucle es un circuito de longitud 1
Circuito Hamiltoniano es circuito elemental que incluye a todos los vértices del grafo
Grafo simple, no tiene bucles y no existe más que un camino para unir dos nodos
14
Conceptos Básicos
Para cada n≥1 se llama grafo completo de orden n, y se representa por Kn, al grafo de n vértices conectados de todas las formas posibles:
Grafo no dirigido: No. Aristas = n(n-1)/2
Grafo dirigido: No. Aristas= n(n-1), n= No. vértices
15
Conceptos Básicos
Se llama ciclo de grado n, y se denota Cn, a G=({v1, …, vn}, 
		 {{v1, v2}, {v2, v3},…, {vn-1, vn}, {vn, v1}} )
Nota: A menudo sólo se consideran ciclos para n≥3
16
Representación de Grafos
Frecuentemente se usa la matriz de adyacencia
Las filas y las columnas corresponden a los vértices. Se pone un 0 para indicar que 2 vértices no son adyacentes, y un 1 para indicar que sí lo son:
En una computadora se utilizan matriz de valores lógicos (booleanos). True  hay arista, False no hay arista
1
2
3
4
5
6
 1 2 3 4 5 6
G
Matriz de Adyacencia de G
17
Representación de Grafos
En el caso de un grafo no dirigido la matriz será simétrica. No ocurre lo mismo para grafos dirigidos:
Se supone que la fila representa el vértice origen, y la columna el vértice destino del arco
18
Representación de Grafos
La matriz de adyacencia también permite representar grafos ponderados
El valor guardado es el coste de la arista/arco
En lugar de 0, a menudo se emplea un valor especial  para indicar que dos vértices no están conectados
19
Representación de Grafos
A menudo se usa la lista de adyacencia
A cada vértice le corresponde una lista con sus adyacentes:
G
Lista de Adyacencia de G
20
Subgrafos
Sea G=(V,A). G’=(V’,A’) se dice subgrafo de G si: 
V’  V
A’  A
(V’,A’) es un grafo
21
Subgrafos
Ejemplo:
G1 y G2 son subgrafos de G
22
Caminos y conectividad
Ejemplo:
G
a,b,e,c,d es un camino
23
Caminos y conectividad
Si existe un camino entre dos vértices se dice que están conectados
Si para todo par de vértices de un grafo están conectados se dice que el grafo es conexo 
Las componentes conexas de un grafo G son los mayores subgrafos conexos de G
24
Caminos y conectividad
Ejemplo. Consideramos el grafo:
Se tiene que:
G no es conexo: no hay camino entre a y b, por ejemplo.
[a] = {a,c,e} [c] = {a,c,e} [e]={a,c,e} [b]={b,d} [d]={b,d}
G/R = {[a],[b]}
G tiene dos componentes conexas:
25
GRACIAS