grafos y Árboles (algoritmo)
Post on 27-Oct-2015
47 Views
Preview:
TRANSCRIPT
TEORÍA DE LOS GRAFOS
Un grafo G es un par ordenado G (V,E), donde:V es un conjunto no vacio, cuyos elementos son llamados
vértices.E es un conjunto de pares de elementos de V, que son llamados
arcosEj.:
G1 G2
1
2
3
a
b c
TEORÍA DE LOS GRAFOS
Un arco es (no) orientado o (no) dirigido si (no) hay una dirección asignada a él. Un grafo es (no) orientado si todos sus arcos son (no) orientados
<i,j> denota el arco dirigido de i a j(i,j) denota el arco no dirigido
Ej.:G1 = (V1,E1) V1 = {1,2,3}
E1 = {(1,2),(2,3),(1,3)}
G2 = (v2,E2) V2 = {a,b,c}E2 = {<a,b>,<a,c>}
GRAFOS NO ORIENTADOS: G = (V,E)
1. Los vértices i y j son adyacentes si (i,j) ϵ E, y se dice que (i,j) es incidente sobre i y j. Por lo tanto es adyacente si existe un arco que los conecte.
2. El grado o valencia del vértice i (di) es el número de arcos incidentes sobre i.
Ej.: En G3.- d1 = 3, d2 = 2, d3 = 2, d4 = 1
2
3
4
1
G3 1 y 2 son adyacentes
1 y 3 son adyacentes
(1,4) es incidente sobre 1 y 4
GRAFO COMPLETO
G es completo si tiene n(n-1) 2 arcos (Kn)
Donde Kn = el grafo completo de n vérticesEj.:
SUBGRAFO: Dado un grafo G, el grafo no orientado H = (V1,E1) es un subgrafo de G = (V,E) si V1 ᴄ V, E1 ᴄ E
Ej.: Un subgrafo de K4 es:
1 2
3 4
n = 4Kn = 6
K4
1 2
3
K3
K3 es subgrafo de K4
CAMINO
CAMINO: Un camino del vértice i1 al vértice ik es una secuencia de vértices P = i1 i2 i3 i4……ik, tal que (ij, ij+1) ϵ E, j = 1,2, ….. , k-1
Ej.: En K4, P = 1,2,4 es un camino de 1 a 4.CAMINO SIMPLE: El camino P es simple si ningún vértice se repite, exceptuando posiblemente el primero y el último vértices, y los arcos son diferentes.Ej.: en K4, P = 1,2,1 (no es camino simple) P = 1,2,3,1 (si es simple y es un camino cerrado) P = 1,2,3,4 (es simple)
CICLO
Un ciclo es un camino simple y cerrado (los vértices extremos son idénticos)
Ej. En k4: P = 2,3,1,2 es ciclo P = 2,3,1,4,2 es ciclo
GRAFO CONEXO
Un grafo G = (V,E) es conexo (conectado), si para cada par de vértices distintos i,j, existe un camino de i a j.Ej.:
A D
B
E
F
G
C
A
B
C
D
E
FG8
G9
NO ES CONEXO
NO ES CONEXO
El subgrafo G1 = (V1,E1) del grafo G = (V,E) es una componente conexa, si G1 es un subgrafo conexo maximal, esto es, no existe un subgrafo G2 = (V2,E2) conexo tal que V1 ᴄ V2 y E1 ᴄ E2.
COMPONENTE CONEXO
A
B
C
D
E
FG8
BICONEXIDAD1. v es un punto de articulación para un grafo G si existen vértices
distintos x y w <> v, tal que v está en todo camino de x a w.2. G es biconexo si no tiene puntos de articulación.
3. Una componente biconexa de un grafo G es un subgrafo de G que es biconexo maximal.
A B
C D
G10
3
1 24
6
5
G11
3
1 24
6
52
4
Componentes básicas de G11
ÁRBOLES
Un grafo es acíclico, si no tiene ciclos.
Un árboles un grafo acíclico y conexo
A
B
C
D
A B
C D
GRAFOS ORIENTADOS
• El arco orientado <i,j> es incidente a j, incidente desde i. El vértice i es adyacente a j, y j es adyacente desde i.
in• INVALENCIA: El grado de entrada del vértice i (di ) es el
número de arcos incidentes a i.
out
• EXVALENCIA: El grado de salida del vértice i (di ) es el número de arcos incidentes desde i.
1
3
2
<1,2> es incidente a 2 es incidente desde 1
• G es completo, si tiene n(n-1) arcos K0n
• Un Subgrafo es otro grafo con un subconjunto de vértices del conjunto de vértices.
• Un camino orientado es una secuencia de vértices• Un ciclo orientado es un camino orientado, donde el vértice
inicial es a su vez el vértice final. El ciclo orientado a su vez se conoce como Circuito.
2
1
3
C
E
D
A
B
CDE no es un caminoABCD es un camino simpleABCEA es un ciclo orientado
• Un grafo es fuertemente conexo si para cada par de vértices distintos i ≠ j existe un circuito que los contiene.Ej.:
G20 G21Si es fuertemente conexo No es fuertemente conexo
• Una componente fuertemente conexa es un subgrafo fuertemente conexo maximal. Ej.:
1
2 3
4
4
32
1
1
2 3
4
1
2 3
4
G22 H1 y H2 son comp. fuertemente conexas de G22
H1
H2
• Una secuencia de vértices P = i1, i2, ……, ik, es un semicamino o
cadena en G si <ij, ij+1> ϵ E ó <ij+1, ij> ϵ E, ó ambos están en E.
P = 1,2,3,4 es un semicamino
• Semicamino simple: es un camino en el cual, ningún vértice o arco se repite.
• Semiciclo: es un semicamino simple cerrado
1
4
3
2G23
• Un grafo orientado G = (V,E) es débilmente conexo si para cada par de vértices distintos i ≠ j existe un semicamino en G de i a j.Ej.:
2
4
1
3
H1
H2
G24
G23 sí es débilmente conexoG24 no es débilmente conexo
H1 y H2 son las componentesdébilmente conexas de G24
ÁRBOL ORIENTADO
• Un árbol orientado es un grafo orientado que es débilmente conexo y que no posee semiciclos.Ej.: G23
• ÁRBOL CON RAIZ: Un árbol con raiz o enraizado es un árbol orientado en la que un solo vértice tiene grado de entrada 0 y los otros tienen grado de entrada 1.Ej.:
4
3
1
2Raíz
REPRESENTACIÓN DE GRAFOS
1. MATRIZ DE ADYACENCIA
A = [aij] ; A : n * n
A) CASO NO ORIENTADO.-
1: si existe el arco (i,j) ϵ Eaij =
0: de otro modoEj.:
1 2
3 4
5
0 1 1 0 01 0 1 1 01 1 0 0 10 1 0 0 10 0 1 1 0
A =
En general, A es simétrica, la diagonal principal es nula
1. MATRIZ DE ADYACENCIA
B) CASO ORIENTADO.-
1: si <i,j> ϵ Eaij =
0: de otro modoEj.:
21
34
0 1 0 00 0 1 00 0 0 00 1 0 0
A =
En general, A no es simétrica
C) GRAFO (ORIENTADO O NO) CON PESOS.-
W(i,j) : si (i,j) ϵ Eaij = <i,j> ϵ E
C : de otro modo (C: Constante)Ej.:
1. MATRIZ DE ADYACENCIA
1
3
2
5
4
5
25
10
6
3216
14C 25 C C CC C 10 14 C5 C C C 16C 6 C C CC C C 32 C
A =
C: Valor muy grande si es utilidad (M). Si W es costo, M es pequeño
G26
2. LISTAS ENLAZADAS DE ADYACENCIANIL
Vértice
Ej.: Lista de adyacencia de G25:
2
1
1
2
3NIL
4NIL3
2
5NIL
5NIL
4NIL3
1
2
3
4
5
2. LISTAS ENLAZADAS DE ADYACENCIA
Ej.: Lista de adyacencia de G26:
2
4
5
2
10
NIL
NIL3
NIL
NIL
NIL4
1
2
3
4
5
25
14
16
6
32
1 5
ÁRBOLES PARCIALES MÍNIMOS• Un árbol parcial para un grafo G = (V,E) es un subgrafo que es
árbol y contiene a todos los vértices de G.Sea G = (V,E,W) un grafo con pesos, el peso de un subgrafo es la suma de los pesos de los arcos del subgrafo.Un árbol parcial mínimo es un árbol parcial de peso mínimo o de costo mínimo.Ej.:
1
32
1
32
2
2
1
32
2 2
11
1
Sus árbolesParcialesMínimos: El árbol parcial
Mínimo no esúnico
ALGORITMO DIJKSTRA / PRIM1. Vértice de árbol: es un vértice que ya está en el árbol que se ha construido
hasta ese momento.2. Vértice vecino: es un vértice que no es del árbol, pero que es adyacente a
uno.3. Vértice no visto: es un vértice que no es del árbol y tampoco es vecino.
Un arco candidato del vértice vecino “y”, es el arco (x,y) con x vértice del árbol que es de peso mínimo.El algoritmo sería:
Seleccionar un vértice vecinoMientras hay vértices vecinos hacer:
Seleccionar un arco de peso mínimo entre un vértice de árbol y un vértice vecino.Añadir tal arco y vértice vecino al árbol
Fin Mientras
ALGORITMO DIJKSTRA / PRIM
Ej.: A B
F
I
G
H
C
7
2
3
5
4
6
21
4
3
A
B
G
F
2
37
Árbol Vecinos
A
B
G
F
3
72
C4
A
B
G
F
3
72
C4
I
H
1
3
A
B
G
F
3 5
2 C4
I
H
13
A
B
G F
3
5
2
C2
I
H
1
3
WT = 16
ALGORITMO VORAZ
• Un algoritmo voraz es un algoritmo para problemas de
optimización en la que se hacen elecciones óptimas
localmente en cada paso.
• El resultado final no es necesariamente óptimo.
• El algoritmo de Dijkstra / Prim es voraz.
• La solución del algoritmo de Dijkstra / Prim sí es óptima.
ÁRBOLES PARCIALES DE COSTO MÍNIMO
1. ALGORITMO DE DIJKSTRA / PRIM
Seleccionar un vértice vecino
Mientras hay vértices vecinos hacer:
Seleccionar un arco de peso mínimo entre un vértice de árbol y
un vértice vecino.
Añadir tal arco y vértice vecino al árbol
Fin Mientras
ÁRBOLES PARCIALES DE COSTO MÍNIMO
2. ALGORITMO DE KRUSKALProcedimiento Kruskal (G,T,n){G = (V,E), N = |V|}ET = 0 ; E´ = E ; i = 0
Mientras E´≠ 0 AND i ≠ n-1 hacerSea (u,w) un arco de costo mínimo de E´E´ = E´- {(u,w)}Si (u,w) no crea un ciclo en T entonces ET = ET U {(u,w)}
i = i + 1Fin Si
Fin MientrasFin Procedimiento Kruskal
ALGORITMO KRUSKAL
Ej.:A B
F
I
G
H
C
7
2
3
5
4
6
21
4
3
ARCOIGHCABAGGHBCIHFIGBFA
COSTO1223344567
A B
F
I
G
H
C
7
2
3
5
4
6
21
4
3
XX
XX
WT = 16 (1+2+2+3+3+5)
El algoritmo Kruskal es vorazLa solución que proporciona sí es óptima
PROBLEMA DE CAMINOS MÁS CORTOS
Sea G = (V,E,W) grafo orientado o no con pesos.Sea P = u1, u2, …., uk un camino de u1 al uk. El peso o longitud de P se define: k-1
W(P) = Ʃ W (ui, ui+1) i=1
PROBLEMA:Sea G = (V,E,W) un grafo con pesos, y sean v, w ϵ V. Hallar un camino más corto de v a w.
SOLUCIÓN:Utilizando el siguiente algoritmo de Dijkstra: Sea z un vértice vecino, tal que z es adyacente a por lo menos un vértice del árbol Vk, entonces existe un camino más corto de v a vk.
Sea P = v, v1, v2, …, vk un camino=> P´= v, v1, v2, …, vk, Z es un camino de v a z
dist (v,z) = d (v,vk) + w(vkz) distancia distancia temporal permanente
El algoritmo:x = vMientras x ≠ w hacer Seleccionar un arco candidato xy tal que dist (v,y) = d (v,x) + w(xy) es mínimo entre todos los vértices vecinos añadir y, (x,y) al árbol d (v,y) = d(v,x) + w(xy) x = yFin Mientras
Ejemplo:
2A B
F
I
G
H
C
9 5
1
4
6
52
4
5
Hallar un camino más corto de A a F
A
B
F
G
2
95
Árbol Vecinos
dist (A,B) = 2
dist (A,F) = 9
dist (A,G) = 5
A
B
F
G
9
52
C4
6
dist (A,F) = 9
dist (A,G) = 5
dist (A,C) = 6
Vecinos
Iteración 1:
Iteración 2:
SOLUCIÓN:
A
G
B
I
2
25
H5
C
F
4
9
dist (A,C) = 6
dist (A,F) = 9
dist (A,I) = 7
dist (A,H) = 10
Iteración 3:
A
G
BI2
2
5 H5
C
F49 dist (A,F) = 9
dist (A,I) = 7
dist (A,H) = 10
A
G
B
F2
1
5H5
C
I
4
2
dist (A,F) = 8
dist (A,H) = 10
Iteración 4:
Iteración 5:
Hallar los caminos más cortos entre todos los pares de vértices i, j, tal que i ≠ j, utilizando el algoritmo de Warshall.
Ck(i,j) = longitud de un camino más corto de i a j que no pasa por vértices intermedios con índices mayor que k
∞ i = jC0(i,j) = ∞ (i,j) ϵ E (<i,j> ϵ E)
W(i,j) (i,j) ϵ E (<i,j> ϵ E)
Supongamos que ya se generó Ck-1, para generar Ck se consideran dos casos:1. El camino más corto de i a j que no pasa por ningún vértice intermedio mayor a k, tampoco pasa por k, entonces su costo es Ck-1(i,j)2. El camino más corto de i a j que no pasa por ningún vértice intermedio mayor a k, sí pasa por k, entonces su costo es Ck-1(i,k) + Ck-1(k,j)
Entonces:Ck(i,j) = min (Ck-1(i,j), Ck-1(i,k) + Ck-1(k,j) k >= 1
ALGORITMO DE WARSHALL:FOR K = 1, N FOR I = 1, N FOR J = 1, N
C (i,j) = min {C(i,j), C(i,k) + C(k,j)} END
ENDEND
V1
V3
V2
6
2
4
11
3
∞ 4 116 ∞ 23 ∞ ∞
∞ 4 116 10 23 7 14
10 4 6 6 10 2 3 7 9
9 4 65 9 23 7 9
C0 =
C2 =
C1 =
C3 =
RECORRIDO DE GRAFOSRecorrer significa visitar cada vértice del grafoEsto implica examinar, visitar o procesar todos los vértices y arcos del grafo
A. BÚSQUEDA PRIMERO A LO ANCHOSe realiza una búsqueda por niveles. Se visitan los vértices que están máscerca al vértice de partida, luego, los vértices que estén a continuacióndel vértice de partida, y así, sucesivamente.Los vértices son visitados en el orden de su distancia del vértice de partida.
Procedure BFS (v) [Breadth First Search){Q es una cola inicializada en 0}Visitar, marcar vInsertar v en QMientras Q ≠ 0 hacer
x = valor en el frente de la cola eliminar x de Q Para cada vértice w adyacente a x no marcado hacer
visitar y marcar winsertar w en Q
Fin ParaFin Mientras
A B
F
I
G
H
C
BFS (A)
Q : A F B I G C H
X = A F B I G C H
(H: Vértice más alejado del origen A)
B. BÚSQUEDA PRIMERO EN PROFUNDIDAD
PROCEDURE DFS (v) [Depth First Search] Visitar y marcar v Mientras hay un vértice w no marcado adyacente a v hacer
DFS (w) Fin Mientras
C GNILB
F BNILA
A B
F
I
G
H
C
DFS (A) v, mA DFS (B) v, mB DFS (C)
v, mC DFS (H) v, mH
DFS (I) v, mI DFS (G) v,mG FinFin
FinFin
Fin DFS (F) v, mF
top related