TEORA DE LOS GRAFOS

TEORA DE LOS GRAFOSUn grafo G es un par ordenado G (V,E), donde:V es un conjunto no vacio, cuyos elementos son llamados vrtices.E es un conjunto de pares de elementos de V, que son llamados arcosEj.:G1G2123abcTEORA DE LOS GRAFOSUn arco es (no) orientado o (no) dirigido si (no) hay una direccin asignada a l. Un grafo es (no) orientado si todos sus arcos son (no) orientados

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 = {,}GRAFOS NO ORIENTADOS: G = (V,E)Los vrtices 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.

El grado o valencia del vrtice i (di) es el nmero de arcos incidentes sobre i.Ej.: En G3.- d1 = 3, d2 = 2, d3 = 2, d4 = 12341G31 y 2 son adyacentes1 y 3 son adyacentes(1,4) es incidente sobre 1 y 4GRAFO COMPLETOG es completo si tiene n(n-1) 2 arcos (Kn)Donde Kn = el grafo completo de n vrticesEj.:SUBGRAFO: Dado un grafo G, el grafo no orientado H = (V1,E1) es un subgrafo de G = (V,E) si V1 V, E1 EEj.: Un subgrafo de K4 es:1234n = 4Kn = 6K4123K3K3 es subgrafo de K4CAMINOCAMINO: Un camino del vrtice i1 al vrtice ik es una secuencia de vrtices P = i1 i2 i3 i4ik, tal que (ij, ij+1) E, j = 1,2, .. , k-1Ej.: En K4, P = 1,2,4 es un camino de 1 a 4.CAMINO SIMPLE: El camino P es simple si ningn vrtice se repite, exceptuando posiblemente el primero y el ltimo vrtices, 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)

CICLOUn ciclo es un camino simple y cerrado (los vrtices extremos son idnticos)

Ej. En k4:P = 2,3,1,2 es ciclo P = 2,3,1,4,2 es ciclo

GRAFO CONEXOUn grafo G = (V,E) es conexo (conectado), si para cada par de vrtices distintos i,j, existe un camino de i a j.Ej.: ADBEFGCABCDEFG8G9NO ES CONEXONO ES CONEXOEl 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 CONEXOABCDEFG8BICONEXIDADv es un punto de articulacin para un grafo G si existen vrtices distintos x y w v, tal que v est en todo camino de x a w.G es biconexo si no tiene puntos de articulacin.

Una componente biconexa de un grafo G es un subgrafo de G que es biconexo maximal.ABCDG10312465G1131246524Componentes bsicas de G11RBOLESUn grafo es acclico, si no tiene ciclos.

Un rboles un grafo acclico y conexoABCDABCDGRAFOS ORIENTADOSEl arco orientado es incidente a j, incidente desde i. El vrtice i es adyacente a j, y j es adyacente desde i.

inINVALENCIA: El grado de entrada del vrtice i (di ) es el nmero de arcos incidentes a i.

outEXVALENCIA: El grado de salida del vrtice i (di ) es el nmero de arcos incidentes desde i. 132 es incidente a 2 es incidente desde 1G es completo, si tiene n(n-1) arcos K0nUn Subgrafo es otro grafo con un subconjunto de vrtices del conjunto de vrtices.Un camino orientado es una secuencia de vrticesUn ciclo orientado es un camino orientado, donde el vrtice inicial es a su vez el vrtice final. El ciclo orientado a su vez se conoce como Circuito.

213CEDABCDE no es un caminoABCD es un camino simpleABCEA es un ciclo orientadoUn grafo es fuertemente conexo si para cada par de vrtices distintos i j existe un circuito que los contiene.Ej.:

G20G21Si es fuertemente conexoNo es fuertemente conexo

Una componente fuertemente conexa es un subgrafo fuertemente conexo maximal. Ej.:1234432112341234G22H1 y H2 son comp. fuertemente conexas de G22H1H2Una secuencia de vrtices P = i1, i2, , ik, es un semicamino o cadena en G si E E, ambos estn en E.

P = 1,2,3,4 es un semicamino

Semicamino simple: es un camino en el cual, ningn vrtice o arco se repite.

Semiciclo: es un semicamino simple cerrado1432G23Un grafo orientado G = (V,E) es dbilmente conexo si para cada par de vrtices distintos i j existe un semicamino en G de i a j.Ej.:2413H1H2G24G23 s es dbilmente conexoG24 no es dbilmente conexoH1 y H2 son las componentesdbilmente conexas de G24RBOL ORIENTADOUn rbol orientado es un grafo orientado que es dbilmente 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 vrtice tiene grado de entrada 0 y los otros tienen grado de entrada 1.Ej.:4312RazREPRESENTACIN DE GRAFOS1. MATRIZ DE ADYACENCIAA = [aij] ; A : n * nCASO NO ORIENTADO.-1: si existe el arco (i,j) Eaij =0: de otro modoEj.:123450 1 1 0 00 1 1 01 1 0 0 10 1 0 0 10 0 1 1 0A =En general, A es simtrica, la diagonal principal es nula1. MATRIZ DE ADYACENCIAB) CASO ORIENTADO.-1: si Eaij =0: de otro modoEj.:21340 1 0 00 0 1 00 0 0 00 1 0 0A =En general, A no es simtricaC) GRAFO (ORIENTADO O NO) CON PESOS.-W(i,j) :si (i,j) Eaij = EC : de otro modo (C: Constante)Ej.:

1. MATRIZ DE ADYACENCIA13254525106321614C 25 C C CC C 10 14 C C C C 16C 6 C C CC C C 32 CA = C: Valor muy grande si es utilidad (M). Si W es costo, M es pequeoG262. LISTAS ENLAZADAS DE ADYACENCIANILVrticeEj.: Lista de adyacencia de G25:21123NIL4NIL325NIL5NIL4NIL3123452. LISTAS ENLAZADAS DE ADYACENCIAEj.: Lista de adyacencia de G26:245210NILNIL3NILNILNIL41234525141663215RBOLES PARCIALES MNIMOSUn rbol parcial para un grafo G = (V,E) es un subgrafo que es rbol y contiene a todos los vrtices 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 mnimo es un rbol parcial de peso mnimo o de costo mnimo.Ej.:1321322213222111Sus rbolesParcialesMnimos:El rbol parcialMnimo no esnicoALGORITMO DIJKSTRA / PRIMVrtice de rbol: es un vrtice que ya est en el rbol que se ha construido hasta ese momento.Vrtice vecino: es un vrtice que no es del rbol, pero que es adyacente a uno.Vrtice no visto: es un vrtice que no es del rbol y tampoco es vecino.

Un arco candidato del vrtice vecino y, es el arco (x,y) con x vrtice del rbol que es de peso mnimo.El algoritmo sera:Seleccionar un vrtice vecinoMientras hay vrtices vecinos hacer:Seleccionar un arco de peso mnimo entre un vrtice de rbol y un vrtice vecino.Aadir tal arco y vrtice vecino al rbolFin Mientras

ALGORITMO DIJKSTRA / PRIMEj.:ABFIGHC7235462143ABGF237rbolVecinosABGF372C4ABGF372C4IH13ABGF352C4IH13ABGF352C2IH13WT = 16

ALGORITMO VORAZUn algoritmo voraz es un algoritmo para problemas de optimizacin 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 solucin del algoritmo de Dijkstra / Prim s es ptima.RBOLES PARCIALES DE COSTO MNIMOALGORITMO DE DIJKSTRA / PRIMSeleccionar un vrtice vecinoMientras hay vrtices vecinos hacer:Seleccionar un arco de peso mnimo entre un vrtice de rbol y un vrtice vecino.Aadir tal arco y vrtice vecino al rbolFin MientrasRBOLES PARCIALES DE COSTO MNIMOALGORITMO DE KRUSKALProcedimiento Kruskal (G,T,n){G = (V,E), N = |V|}ET = 0 ; E = E ; i = 0Mientras E 0 AND i n-1 hacerSea (u,w) un arco de costo mnimo de EE = E- {(u,w)}Si (u,w) no crea un ciclo en T entonces ET = ET U {(u,w)} i = i + 1Fin SiFin MientrasFin Procedimiento KruskalALGORITMO KRUSKALEj.:ABFIGHC7235462143ARCOIGHCABAGGHBCIHFIGBFACOSTO1223344567ABFIGHC7235462143XXXXWT = 16 (1+2+2+3+3+5)El algoritmo Kruskal es vorazLa solucin que proporciona s es ptimaPROBLEMA DE CAMINOS MS CORTOSSea 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=1PROBLEMA:Sea G = (V,E,W) un grafo con pesos, y sean v, w V. Hallar un camino ms corto de v a w.

SOLUCIN:Utilizando el siguiente algoritmo de Dijkstra: Sea z un vrtice vecino, tal que z es adyacente a por lo menos un vrtice del rbol Vk, entonces existe un camino ms 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 permanenteEl algoritmo:x = vMientras x w hacer Seleccionar un arco candidato xy tal que dist (v,y) = d (v,x) + w(xy) es mnimo entre todos los vrtices vecinos aadir y, (x,y) al rbol d (v,y) = d(v,x) + w(xy) x = yFin Mientras

Ejemplo:2ABFIGHC951465245Hallar un camino ms corto de A a FABFG295rbolVecinosdist (A,B) = 2

dist (A,F) = 9

dist (A,G) = 5ABFG952C46dist (A,F) = 9

dist (A,G) = 5

dist (A,C) = 6VecinosIteracin 1:Iteracin 2:SOLUCIN:AGBI225H5CF49dist (A,C) = 6

dist (A,F) = 9

dist (A,I) = 7

dist (A,H) = 10Iteracin 3:AGBI225H5CF49dist (A,F) = 9

dist (A,I) = 7

dist (A,H) = 10AGBF215H5CI42dist (A,F) = 8

dist (A,H) = 10Iteracin 4:Iteracin 5:Hallar los caminos ms cortos entre todos los pares de vrtices i, j, tal que i j, utilizando el algoritmo de Warshall.

Ck(i,j) = longitud de un camino ms corto de i a j que no pasa por vrtices intermedios con ndices mayor que k

i = jC0(i,j) = (i,j) E ( E) W(i,j)(i,j) E ( E)

Supongamos que ya se gener Ck-1, para generar Ck se consideran dos casos:1. El camino ms corto de i a j que no pasa por ningn vrtice intermedio mayor a k, tampoco pasa por k, entonces su costo es Ck-1(i,j)2. El camino ms corto de i a j que no pasa por ningn vrtice 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 >= 1ALGORITMO DE WARSHALL:FOR K = 1, N FOR I = 1, N FOR J = 1, NC (i,j) = min {C(i,j), C(i,k) + C(k,j)} END ENDENDV1V3V2624113 4 116 23 4 1110 23 7 14 4 6 6 10 2 3 7 99 4 65 9 23 7 9C0 =C2 =C1 =C3 =RECORRIDO DE GRAFOSRecorrer significa visitar cada vrtice del grafoEsto implica examinar, visitar o procesar todos los vrtices y arcos del grafoBSQUEDA PRIMERO A LO ANCHOSe realiza una bsqueda por niveles. Se visitan los vrtices que estn mscerca al vrtice de partida, luego, los vrtices que estn a continuacindel vrtice de partida, y as, sucesivamente.Los vrtices son visitados en el orden de su distancia del vrtice de partida.Procedure BFS (v) [Breadth First Search){Q es una cola inicializada en 0}Visitar, marcar vInsertar v en QMientras Q 0 hacerx = valor en el frente de la cola eliminar x de Q Para cada vrtice w adyacente a x no marcado hacervisitar y marcar winsertar w en Q Fin ParaFin MientrasABFIGHCBFS (A)

Q : A F B I G C H

X = A F B I G C H (H: Vrtice ms alejado del origen A)B. BSQUEDA PRIMERO EN PROFUNDIDADPROCEDURE DFS (v) [Depth First Search] Visitar y marcar v Mientras hay un vrtice w no marcado adyacente a v hacerDFS (w) Fin MientrasCGNILBFBNILAABFIGHCDFS (A) v, mA DFS (B) v, mB DFS (C) v, mC DFS (H) v, mHDFS (I) v, mI DFS (G) v,mG FinFin FinFin Fin DFS (F) v, mF