Download - Mpinning Gy Alg10(Busqueda)
![Page 1: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/1.jpg)
1
Búsqueda en Grafos
❚ Anchura
❚ Profundidad
![Page 2: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/2.jpg)
2
Definiciones Adicionales
❚ Def. Supongamos que R A B. La inversa de R, denotada por R-1, es la relación {(y,x)|(x,y) R}.
Ejemplo:
a b c a b c
![Page 3: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/3.jpg)
3
❚ Def. Suponga R1 A B y R2 B C. La composición de R1 y R2, denotada por R1 R2, es la relación {(x,z)| (x,y) R1 (y,z) R2}.
Ejemplo:
a b
c
a b
c dR1 R2
![Page 4: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/4.jpg)
4
a b
cd
R1 R2
![Page 5: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/5.jpg)
5
❚ Def. Un grafo sin loops se llama grafo simple. El número de vértices de G se llama orden de G y el número de aristas de G se llama tamaño de G.
❚ Teorema. En cada árbol no trivial, hay al menos un vértice de grado 1.
❚ Teorema. Un grafo G es un árbol ssi G no tiene ciclos y | E | = | V | - 1.
![Page 6: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/6.jpg)
6
Breadth First Search❚ Entrada: Grafo conexo con vértices v1, v2, ..., vn.
❚ Salida: T, árbol de cobertura de G.
❚ Algoritmo:❙ 1. (Inicio) Sea v1 la raíz de T, sea V = {v1}
❙ 2. (Agrega aristas) Para cada vértice x V, agregar la arista {x, vk} a T, donde k es el menor índice tal que al agregar la arista {x, vk} a T no se forma un ciclo. Si no hay más aristas para agregar, parar. T es el árbol de cobertura.
❙ 3. (Actualizar) Reemplazar V por los hijos v en T de los vértices x de V donde las aristas {x,v} se agregaron en el paso 2. Repetir paso 2 para el nuevo conjunto V.
![Page 7: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/7.jpg)
7
a
b
d
c
f
e
g
ij
k
h
Ejemplo:
![Page 8: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/8.jpg)
8
a
b
d
c
f
e
g
ij
k
h
a
G
T
![Page 9: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/9.jpg)
9
a
b
d
c
f
e
g
ij
k
h
a
b
d
G
T
![Page 10: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/10.jpg)
10
a
b
d
c
f
e
g
ij
k
h
a
b
d
c
G
T
![Page 11: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/11.jpg)
11
a
b
d
c
f
e
g
ij
k
h
a
b
d
c
e
G
T
![Page 12: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/12.jpg)
12
a
b
d
c
f
e
g
ij
k
h
a
b
d
c
f
e
g
G
T
![Page 13: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/13.jpg)
13
a
b
d
c
f
e
g
ij
k
h
a
b
d
c
f
e
g
h
G
T
![Page 14: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/14.jpg)
14
a
b
d
c
f
e
g
ij
k
h
a
b
d
c
f
e
g
ij
k
h
G
T
![Page 15: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/15.jpg)
15
Depth First Search❚ Entrada: Grafo conexo con vértices v1, v2, ..., vn.
❚ Salida: T, árbol de cobertura de G.
❚ Algoritmo:❙ 1. (Visita vértice) Sea v1 la raíz de T, sea L = {v1}
❙ 2. (Encuentra aristas y vértices no visitados adyacentes a L) Para todos los vértices adyacentes a L, elegir arista {L, vk} donde k es el menor índice tal que al agregar la arista {L, vk}} a T no se forma un ciclo. Si no hay tal arista, ir a paso 3; en caso contrario agregar {L, vk}}a T y hacer L = vk. Repetir paso 2 con el nuevo valor de L
❙ 3. (Backtrack o fin) Si x es padre de L en T, hacer L = x y aplicar paso 2 al nuevo valor de L. Si L no tiene padres en T (o sea, L = v1), terminar.
![Page 16: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/16.jpg)
16
a
b
d
c
f
e
g
ij
k
h
a
G
T
![Page 17: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/17.jpg)
17
a
b
d
c
f
e
g
i
j
k
h
a
b
G
T
![Page 18: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/18.jpg)
18
a
b
d
c
f
e
g
ij
k
h
a
bc
G
T
![Page 19: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/19.jpg)
19
a
b
d
c
f
e
g
ij
k
h
a
b
d
c
G
T
![Page 20: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/20.jpg)
20
a
b
d
c
f
e
g
ij
k
h
a
b
d
c
e
G
T
![Page 21: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/21.jpg)
21
a
b
d
c
f
e
g
ij
k
h
a
b
d
c
f
e
G
T
![Page 22: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/22.jpg)
22
a
b
d
c
f
e
g
ij
k
h
a
b
d
c
f
e
g
G
T
![Page 23: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/23.jpg)
23
a
b
d
c
f
e
g
ij
k
h
a
b
d
c
f
e
g
h
G
T
![Page 24: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/24.jpg)
24
a
b
d
c
f
e
g
ij
k
h
a
b
d
c
f
e
g
i
h
G
T
![Page 25: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/25.jpg)
25
a
b
d
c
f
e
g
ij
k
h
a
b
d
c
f
e
g
ij
h
G
T
![Page 26: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/26.jpg)
26
a
b
d
c
f
e
g
ij
k
h
a
b
d
c
f
e
g
ij
k
h
G
T
![Page 27: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/27.jpg)
27
Recuerdos (Grafos planares)
❚ Teorema. Si G es un grafo plano, entonces la suma de los grados de las regiones determinadas por G es 2·|E|, donde |E| es el número de aristas de G.
❚ Fórmula de Euler. SI G es un grafo plano, entonces |V| - |E| + |R| = 2 (Euler 1752)❙ |V|: número de vértices
❙ |E|: número de aristas
❙ |R|: número de regiones
![Page 28: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/28.jpg)
28
❚ Corolario. En un grafo conexo plano (simple) G, con |E| > 1:❙ a) |E| 3·|V| - 6, y
❙ b) hay un vértice v en G tal que grado(v) 5
❚ Teorema. Un grafo completo Kn es planar ssi n 4.
❚ Teorema. Un grafo bipartito completo Km,n es planar ssi m 2 o n 2
![Page 29: Mpinning Gy Alg10(Busqueda)](https://reader034.vdocumento.com/reader034/viewer/2022052316/559e7daa1a28ab8d118b45c4/html5/thumbnails/29.jpg)
29
Más recuerdos (Grafos Hamiltonianos)
❚ Teorema de Dirac. Un grafo simple con n vértices (n 3) en el cual cada vértice tiene grado al menos n/2, tiene un ciclo hamiltoniano.