Grafos y Árboles (algoritmo)
-
Upload
walter-sotelo -
Category
Documents
-
view
47 -
download
0
Transcript of Grafos y Árboles (algoritmo)
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