Download Matemáticas Discretas - Ciencias Computacionales

Coordinación de Ciencias Computacionales - INAOE
Grafos
Matemáticas Discretas
Grafos
Definiciones básicas
Caminos y ciclos
 Grafos eulerianos y hamiltonianos
 Isomorfismo
 Árboles


Cursos Propedéuticos 2010
Ciencias Computacionales
INAOE
Dr. Luis Villaseñor Pineda
[email protected]
http://ccc.inaoep.mx/~villasen
2
Generalidades
¿Qué son?
Los grafos son estructuras discretas compuestas por
vértices y aristas que conectan pares de esos puntos
 Son una abstracción útil para modelar situaciones
tales como:








Un grafo es una representación gráfica de objetos y
relaciones binarias entre éstos.

Redes de computadoras
Estructuras de datos
Redes eléctricas y telefónicas
Circuitos eléctricos
Sistemas carreteros
Sistemas de toma de decisiones
Un grafo se representa gráficamente por medio de puntos o
pequeños círculos, que designan vértices, y líneas que los
unen, que representan las aristas
2
3
1
5
4
3
4
1
Grafos dirigidos

Grafos simples
Un grafo dirigido/dígrafo G = (V, E) consiste de un
conjunto de vértices V (o nodos) y un conjunto de
aristas (o arcos) dirigidas E  VV

Note que las aristas (a, b) tiene una dirección; un vértice
fuente/origen a y un vértice terminal b

V={1,2,3,4,5}
E = {(1,3), (2,3), (3,4),
(4,3), (5,3), (5,4), (5,5)}

2

3
1
Un grafo no dirigido G = (V,E) sin auto lazos se
denomina grafo simple

E se determina por una relación simétrica, antireflexiva, tal
que {a,b} E si y solo si (a,b)R

V={1,2,3,4,5}
E = {{1,2}, {1,3}, {2,3},
{3,4}, {3,5}, {4,5}, {2,5}}
2
3
1
5
5
4
4
5
Definiciones
6
Representación de grafos simples
Si e={u, v} es una arista entonces se dice que los
vértices u y v son los extremos de e
 Un vértice y una arista son incidentes si el vértice es
uno de los extremos de la arista
 Dos vértices u y v son adyacentes si {u, v} es una
arista

{1,2}
1
2
{2,3}
{1,3}
{2,4}
{3,4}
3
4
{1,4}
7
8
2
Ejemplo: vértices

Ejemplo: vértices
¿Cuáles vértices son adyacentes a 1?

¿Cuáles vértices son adyacentes a 1?


1
2
e1
e3


1 es adyacente a 2 y 3
2 es adyacente a 1 y 3
3 es adyacente a 1 y 2
4 no es adyacente a vértice alguno
e2
3
1
e4
e3
4
Ejemplo: vértices




e4
4
10
Definiciones
¿Cuáles aristas son incidentes a 1?

e2
3
9
2
e1
Dos aristas asociadas al mismo par de vértices son
aristas paralelas
 Una arista incidente en un sólo vértice es un ciclo
 Un vértice que no es incidente en ninguna arista es un
vértice aislado

e1, e2, e4 son incidentes a 2
2 es incidente con e1, e2, e4
3 es incidente con e2, e3
4 no es incidente con ninguna arista
1
2
e1
e3
e2
3
e4
4
11
12
3
Matriz de adyacencia

Ejemplo

Forma de representar grafos y relaciones
2
1
3
4
1

0
0

0

1
1
0
0
1
1
1
0
1

1
1

1
¿Cuál es la matriz de adyacencia del grafo de la
figura?
1
2
3
4
0

2
1

0

2
2
1
0
13
0

0
0

1 
14
Tipos de grafos
Grafos completos
Un grafo no dirigido sin auto lazos (un ciclo sobre un
mismo vértice) se denomina grafo simple
 Un grafo con aristas paralelas (dos aristas pueden
conectar un mismo par de vértices) es llamado
multigrafo
 Un grafo completo es un grafo con arcos entre cada
par de vértices
 Un grafo pesado es aquel que tiene pesos asociados a
nodos y/o arcos


1
1
0
0
Se llama grafo completo (o clique) en n vértices a un
grafo con n vértices v1, v2, …, vn donde para todo a y
b que pertenecen a V existe una arista {a, b}. Este
grafo se denota Kn, y el número de aristas de Kn es
n(n-1)/2
Cada par de vértices distintos comparte un arista
15
16
4
Grados

El grado de un vértice v de un grafo es el número
g(v) de aristas incidentes con él. Si g(v) = 0 se dice
que v es un vértice aislado


Ejemplo: grado de un vértice

¿Cuál es grado del vértice 2?

g(2)=1+1+1+2+2=7
En grafos dirigidos existen grado de entrada y grado de
salida
1
La sucesión de grados de un grafo se obtiene
ordenando en forma creciente los grados de todos los
vértices
e3
e1
e2
e6
e4
2
e5
3
17
Ejemplo: grado de un vértice

Teorema de Euler
¿Cuáles son los grado de entrada y salida de los
vértices del grafo mostrado en la figura?






g-(1) = 0
g-(2) = 3
g-(3) = 4
g+(1) = 2
g+(2) = 3
g+(3) = 2

En todo grafo G=(V, E) se cumple
g (v )  2 E


v V
2
1
18

3
19
Las aristas se pueden contar considerando cuantas son
incidentes en cada vértice y sumando todos los números
obtenidos. Pero asi cada arista resulta contada dos veces,
una para cada uno de sus extremos
20
5
Ejemplos

Si un grafo tiene una sucesión de grados 0, 1, 1, 2,
3, 4, ¿Cuántas aristas tiene?


Subgrafos

(0+1+1+2+3+4)/2=5
¿Existe algún grafo cuya sucesión de grados sea 1,
1, 2, 3, 4?

Si G = (V, E) y H = (W, F) son grafos tales que
W  V y F  E, entonces se dice que H es un
subgrafo de G y que G es un supergrafo de H.
Cada arista de F es incidente con vértices en W
No, dado que 1+1+2+3+4=11 es impar
21
Ejemplo
22
Caminos y ciclos

b
a
c
b
e
a
b
c
e
Un camino de longitud n es un grafo G = (V, E) con
V = {v0, v1, v2, . . . , vn} y E = {v0v1, v1v2, . . . ,
vn−1vn}. Un camino se representa dando la sucesión
v0v1 . . . vn de sus vértices, entendiendo que las aristas
son v0v1, v1v2,. . . , vn−1vn. A v0 y vn se les llama
extremos del camino.


d
d

d

23
Camino: Secuencia ordenada de vértices y arcos.
Camino cerrado: Cuyo inicio es igual que el final
Camino simple: Sin aristas repetidas.
Camino elemental: Sin vértices repetidos.
24
6
Caminos y ciclos

Ejemplo
Un ciclo de longitud n es un grafo G = (V,E) de orden
n≥3, con vértices v0, v1, . . . , vn−1 y aristas v0v1, v1v2,.
. . , vn−2vn−1 y vn−1v0.



Camino de a-b


Camino de b a f

Camino de f a a

Camino de c a c

Ciclo: Camino elemental cerrado.
Circuito: Camino simple cerrado.
{a, b},{b, d}, {d, c}, {c, e},
{e, d}, {d, b}


a
b
b–c–d–e–c–f
c
d
{f, c}, {c, e}, {e, d}, {d, a}
c–e–d–c
e
f
25
26
Distancia y diámetro
Grafo conexo
La distancia d(u, v) entre dos vértices u y v de un
grafo es la longitud del camino más corto de u a v. Si
no existe ningún camino de u a v entonces d(u, v) =
∞.
 El diámetro de G es la máxima distancia entre dos
vértices de G y se denota diam(G).


27
Un grafo G = (V, E) es conexo si para cualquier par
de vértices u, y v existe un camino en G que los une,
es decir un camino con extremos u y v.
Equivalentemente, G es conexo si diam(G) < ∞
28
7
Ejemplo

Problemas de Caminos y Circuitos
Sea G=(V, E) un grafo no dirigido en V={a, b, c, d, e,
f, g}


El grafo no es conexo
Los dos sub-grafos son conexos
a
e
g
b
Encontrar si existe un camino entre un par de vértices
 Encontrar el camino más corto entre un par de
vértices
 Encontrar camino que pase por cada arista una sola
vez (Euler)
 Encontrar circuito que pase por cada vértice una sola
vez (Hamilton)

c
d
f
29
Camino simple de Euler

Camino simple de Euler
Un camino simple de Euler es un camino que pasa
por todas las aristas exactamente una sola vez.

30
Teorema:
 (a) Si un grafo conexo tiene más de dos nodos con
grado impar, no existe un camino simple de Euler.
 (b) Si existen exactamente dos vértices de grado
impar, el grafo se puede recorrer, pero el camino ha
de empezar en uno de los dos vértices de grado impar
y terminar en el otro.
 (c) Si no existen vértices de grado impar, el grafo se
puede recorrer. El camino siempre será cerrado.
Los puentes de Königsberg
31
32
8
Ciclo de Hamilton

Ejemplo
Sean G=(V, E) un grafo, se dice que G tiene un ciclo
de Hamilton si existe un ciclo en G que incluye todos
y cada uno de los vértices en V.

En el grafo de la figura, las aristas {a, b}, {b, c}, {c,
f}, {f, e}, {e, d}, {d, g}, {g, h} y {h, i} producen una
camino de Hamilton
a
b
c
d
e
f
g
h
i
33
¿Existe solución?

Dado un grafo cualquiera, ¿es posible determinar si
posee un camino Hamiltoniano?

Es una pregunta muy parecida a la de Euler, así que
se esperaría una respuesta del mismo tipo…

34
Clique
Grafo completo: cada par de nodos distintos son
adyacentes
 Conjunto completo: subconjunto W de G que induce
un subgrafo completo de G
 Clique: subconjunto de nodos que es conjunto
completo y máximo (no hay un conjunto completo
que lo contenga)

Sin embargo, se trata de un problema NP-completo
(Teorema de Garey-Johnson)
35
38
9
Cliques
Cliques
39
Cliques
40
Isomorfismo

41
Dos grafos G={V, E} y G’={V’, E’} son isomorfos si
existe una biyección f: V  V’ que preserva la
relación de adyacencia, es decir tal que

{u, v}  E si y solo si {f(u), f(v)}  E’

Dos grafos isomorfos deben tener el mismo número de
vértices. Todas las propiedades que se deriven de la
relación de adyacencia deben ser idénticas: mismo número
de aristas y sucesiones de grado
42
10
Ejemplo: isomorfismo

Ejemplo
Los dos grafos representados en la figura son
isomorfos:
a
b
w
x
c
d
y
z
Grafos isomorfos
43
Ejemplo
44
Tipos de isomorfismos

b
v
d
a
e
f

u
c
x
Isomorfismo de subgrafos

Doble isomorfismo de subgrafos


z
correspondencia 1:1 entre dos grafos G1 - G2

w
y
Isomorfismo de grafos
correspondencia entre un grafo G1 y los subgrafos de G2
correspondencia entre los subgrafos de G1 y los subgrafos
de G2
Grafos no isomorfos
45
46
11
Búsqueda con backtracking

Búsqueda con backtracking
Se construye un árbol en el que las trayectorias
corresponden a isomorfismos:




se toma un nodo de G1 y todas sus posibles
correspondencias en G2 (primer nivel)
se buscan los nodos conectados a los nodos
correspondientes del primer nivel (segundo nivel)
se continua hasta que no existan correspondencias
las trayectorias en el árbol corresponden a isomorfismos
de subgrafos entre G1 y G2
A/A’
A/A’’
B/B’
C/C’ C/C’’
47
48
Árboles
Ejemplo
Un árbol es un grafo conexo y acíclico
 Sea G(V, E) un grafo. Las afirmaciones siguientes
son equivalentes:






G es un árbol
Dos vértices cualesquiera de G están unidos por un único
camino
G es conexo pero si se le quita cualquier arista deja de serlo
G es acíclico pero si se le agrega una arista cualquiera deja
de serlo
El grafo de la izquierda es un árbol pero el de la
derecha no
a
b
c
c
d
d
e
49
a
b
f
e
f
50
12
Árbol
Árbol
Hoja o nodo terminal: grado 1
 Nodo rama o interno: grado > 1


Propiedades:



Hay una trayectoria simple entre cada par de nodos
El número de nodos = número de aristas + 1
Un árbol con 2 o más nodos tiene al menos dos nodos hoja
51
52
Árbol dirigido
Árboles dirigidos
Árbol (enraizado): un nodo con grado de entrada 0
(raíz) y los demás con 1
 Poliárbol (árbol dirigido): se vuelve un árbol al
quitar las direcciones


Terminología:






53
Raíz: vértice con grado de entrada 0
Hoja: vértice con grado de salida 0
Interno: vértice con grado de salida > 0
Hijo / Padre: arista de A a B, A es padre de B y B es
hijo de A
Hermanos: tienen el mismo padre
Descendientes / Ascendientes: camino de A a B, A es
ascendiente de B y B es descendiente de A
54
13
Árbol dirigido

Teoremas
Terminología:




Subárbol con raíz A: A y todos sus descendientes
Subárbol de A: subárbol con hijo de A como raíz
Árbol ordenado: aristas salientes de cada nodo
etiquetados con enteros
Árbol de aridad “m”: cada nodo rama (raíz o interno)
tiene máximo m hijos. Es regular si c/u tiene
exactamente m hijos (binario m =2)

Si G=(V, E) es un grafo no dirigido, entonces G es
conectado si y sólo si G tiene un árbol de cobertura

En cualquier árbol T=(V, E), |V|=|E|+1
55
56
Recorridos en árboles

Ejemplos
1
Sea T un árbol con raíz r. Si t no tiene otros vértices,
entonces las raíz constituye los recorrido pre-order y postorder. Si |V| > 1, sean T1, T2, …, Tk los subárboles de T de
izquierda a derecha:


2
El recorrido en pre-order de T primero visita r y después recorre los
vértices de T1 en pre-order, luego los vértices de T2 en pre-order y así
sucesivamente hasta que los vértices de Tk son recorridos en preorden
El recorrido post-order de T recorre en post-order los subárboles T1,
T2, .., Tk y después visita la raíz
5
11 12


57
4
3
6
13 14
7
8
9
10
15 16
17
Recorrido en pre-order: 1, 2, 5, 11, 12, 13, 14, 3, 6, 7, 4, 8, 9,
10, 15, 16, 17
Recorrido en post-order: 11, 12, 13, 14, 5, 2, 6, 7, 3, 8, 9,15,
16, 17, 10, 4, 1
58
14
Recorrido in-order

Ejemplo
r
Sea T=(V, E) un árbol binario con raíz en el
vértice r:


a
Si |V| = 1, entonces el vértice r constituye el recorrido
in-order de T
Si |V| > 1, sea TL y TR los subárboles izquierdo y
derecho de T. El recorrido in-order de T visita primero
los vértices de TL in-order y después visita la raíz y
finalmente recorre in-order los vértices de TR
j
f
p

59
e
d
c
h
n
t
u
q
Recorrido en orden: f, c, p, j, q, a, d, r, h, e, t, n, u
60
15