notas/grafo/grafo.md (12589B)
1 # Grafos 2 3 Algoritmos y Estructuras de Datos (CB100) - FIUBA 4 Martin Klöckner - [mklockner@fi.uba.ar](mailto:mklockner@fi.uba.ar) 5 6 \vspace{-1.25em} 7 \rule{\linewidth}{0.5pt} 8 \vspace{-1.25em} 9 10 Los grafos son una estructura de datos compuestos por vértices (o nodos) y 11 unidos por aristas. Tanto los vertices como las aristas pueden contener datos. 12 13 Los grafos pueden ser dirigidos o no, los primeros se representan gráficamente 14 con sus aristas como flechas, mientras que los segundos sus aristas se 15 representan como lineas, sin principio ni fin. 16 17 \begin{figure}[H] 18 \centering 19 \hspace*{-1mm} 20 \begin{subfigure}[t]{0.45\linewidth} 21 \centering 22 \includegraphics[width=\linewidth]{./grafo-dirigido.png} 23 \caption{Grafo dirigido} 24 \end{subfigure} 25 \hspace*{1mm} 26 \begin{subfigure}[t]{0.45\linewidth} 27 \centering 28 \includegraphics[width=\linewidth]{./grafo-no-dirigido.png} 29 \caption{Grafo no dirigido} 30 \end{subfigure} 31 \caption{Representación gráfica de grafos} 32 \end{figure} 33 34 Una posible implementación de las estructura de datos grafo es mediante una 35 matriz en la cual en las filas y columnas se ponen los vértices y en la 36 intersección entre vértices se pone 0 o 1 en función de si existe una arista 37 que los conecte. La contra de esta implementación es que cada vértice puede 38 tener como máximo de aristas la cantidad de vértices total que haya en el grafo. 39 40 <!-- 41 \begin{table}[H] 42 \renewcommand{\arraystretch}{1.2} % Espaciado entre filas 43 \noindent\begin{minipage}{\columnwidth} 44 \centering 45 \begin{tabular}{|c|c|c|c|c|c|c|c|} 46 \hline 47 & \textbf{A} & \textbf{B} & \textbf{C} & \textbf{D} & \textbf{E} & \textbf{F} & \textbf{G} \\ \hline 48 \textbf{A} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 49 \textbf{B} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 50 \textbf{C} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 51 \textbf{D} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 52 \textbf{E} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 53 \textbf{F} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 54 \textbf{G} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 55 \end{tabular} 56 \caption{Representación de un grafo en una matriz} 57 \end{minipage} 58 \end{table} 59 --> 60 61 \begin{table}[H] 62 \renewcommand{\arraystretch}{1.2} % Espaciado entre filas 63 \noindent\begin{minipage}{\columnwidth} 64 \centering 65 \begin{tabular}{|c|c|c|c|} 66 \hline 67 & \textbf{A} & \textbf{E} & \textbf{D} \\ \hline 68 \textbf{A} & 0 & 1 & 1 \\ \hline 69 \textbf{E} & 0 & 0 & 1 \\ \hline 70 \textbf{D} & 0 & 0 & 0 \\ \hline 71 \end{tabular} 72 \caption{Representación de un grafo en una matriz} 73 \end{minipage} 74 \end{table} 75 76 La implementación mas común es mediante una lista enlazada de dos dimensiones, 77 cada nodo representando un vértice, y este a su vez conteniendo una lista de los 78 vertices adyacentes, esta version es mas eficiente que la implementación con 79 matriz. 80 81 ## Definiciones 82 83 ### Camino 84 85 Un camino es una secuencia de vértices conectados por aristas, donde cada 86 vértice está conectado con el siguiente mediante una arista del grafo (un 87 vértice y otro se dicen adyacentes si estas conectados por una arista). La 88 **longitud del camino** se define como la cantidad de aristas del camino. 89 90 #### Camino simple 91 92 En un camino simple no se repiten vértices (excepto, a veces, el primero y el 93 último si es un ciclo). 94 95 #### Camino cerrado 96 97 En un camino cerrado, el primer y último vértice son el mismo, sin importar la 98 repetición de vertices. 99 100 #### Camino abierto 101 102 Por el contrario a un camino cerrado, un camino abierto es un camino en el cual 103 el primer y ultimo vértice difieren. 104 105 ### Recorrido 106 107 Un recorrido es un camino en el cual no se repiten aristas. 108 109 ### Ciclo 110 111 Un ciclo es un camino que contiene vértices distintos excepto el primer y ultimo 112 vértice que son el mismo. Si un grafo no tiene ciclos se dice **acíclico**. 113 114 #### Ciclo Hamiltoniano 115 116 Un ciclo se dice que es Hamiltoniano si visita exactamente una vez todos los 117 vértices del grafo, y por ser un ciclo vuelve al punto de partida. 118 119 ### Subgrafo 120 121 Un subgrafo de un grafo es un grafo en si que se compone de un subconjunto de 122 vértices y aristas del grafo más grande. 123 124 ### Grafo subyacente 125 126 Un grafo subyacente es un grafo no dirigido que se obtiene a partir de 127 reemplazar todas las aristas dirigidas por no dirigidas en un grafo dirigido. 128 129 ### Grafo conexo 130 131 Cuando se puede acceder a todos los vértices mediante un camino de aristas. En 132 el caso de grafos dirigidos, se debe definir si es fuertemente conexo o 133 débilmente conexo, no alcanza con decir que es conexo ya que puede resultar 134 ambiguo. 135 136 ### Grafo dirigido fuertemente conexo 137 138 Un grafo dirigido es fuertemente conexo si y solo si entre cualquier par de 139 vértices existe un camino que los une en ambos sentidos, no necesariamente el 140 camino de vuelta tiene que ser entre los mismos vértices, puede ser que entre 141 dos vértices haya una arista dirigida pero para volver haya que realizar un 142 camino de mayor longitud. 143 144 ### Grafo dirigido débilmente conexo 145 146 Un grafo dirigido es débilmente conexo si no es fuertemente conexo, es decir, no 147 existe un camino entre cualquier par de vértices, pero si es conexo su grafo 148 subyacente, es decir aquel que se obtiene de reemplazar las aristas dirigidas 149 por no dirigidas. Por ejemplo el grafo de la figura 1.1 es débilmente conexo, ya 150 que no se puede acceder al nodo A o E desde el nodo D debido a las direcciones 151 de las aristas, y ademas su grafo subyacente si es conexo. 152 153 ### Punto de articulación 154 155 Un punto de articulación (también llamado vértice de corte) de un grafo no 156 dirigido conexo es aquel vértice que al eliminarlo del grafo este deja de ser 157 conexo 158 159 ### Árbol libre 160 161 Se dice que un grafo es árbol libre si es no dirigido, conexo y sin ciclos. 162 163 ## Recorridos de un grafo 164 165 Los dos recorridos básicos en un grafo son en profundidad y en anchura, cada uno 166 visita o procesa cada vértice del grafo, visitando una y solo una vez cada uno. 167 168 ### En profundidad 169 170 En el recorrido en profundidad (en ingles Depth-First Search o DFS) se toma el 171 primer vértice (como esté almacenado, ya que no hay un "primer vértice" por 172 definición) y se recorre en profundidad los vértices adyacentes de este, 173 marcando en cada visita los vértices como visitados, es decir, para el primer 174 adyacente se recorren los adyacentes de este y así sucesivamente hasta que se 175 llegue a un vértice que no tenga vértices adyacentes o que ya hayan sido 176 visitados. Cuando se llega a este punto se sigue con el próximo vértice que no 177 este visitado (de acuerdo a como están almacenados) y se vuelve a repetir el 178 algoritmo sobre este nodo, así sucesivamente con todos los vértices del grafo. 179 180 La implementación típica es mediante una función recursiva, aunque se puede 181 implementar también de manera iterativa utilizando una cola. 182 183 ### En anchura 184 185 El recorrido en anchura (en ingles Breath-First Search o BFS) es similar al 186 recorrido en profundidad pero en lugar de recorrer todos los nodos adyacentes en 187 profundidad se recorren los nodos adyacentes, marcándose como visitados, y luego 188 se sigue con los próximos vértices no visitados (de acuerdo a como se tienen 189 almacenados) recorriendo sus vértices adyacentes, así sucesivamente con todos 190 los nodos del grafo. 191 192 La implementación típica es utilizando una función iterativa con la ayuda de una 193 cola, la version iterativo no es común ya que es poco eficiente y difícil de 194 implementar. 195 196 ### Topológicos 197 198 Los recorridos topológicos se aplican a grafos dirigidos en los que no hay 199 ciclos (acíclicos) y son un proceso de asignación de orden lineal a los vertices 200 del grafo de modo que se respeten las precedencias indicadas por las relaciones 201 de adyacencia. Se pueden plantear recorridos topológicos como variantes del 202 recorrido en profundidad y en anchura. 203 204 Estos recorridos permiten linealizar un grafo de manera que se cumplan las 205 relaciones de adyacencia entre cada nodo. 206 207 <!-- ## Algoritmo de detección de ciclos --> 208 ## Aplicaciones de DPS 209 210 ### Puntos de articulación 211 212 ### Detección de componentes conexas 213 214 La búsqueda en profundidad también puede usarse para determinar con eficiencia 215 las componentes fuertemente conexas de un grafo dirigido. Una componente 216 fuertemente conexa de un grafo es un conjunto maximal de vertices en el que 217 existe camino entre cualquier par de vertices del conjunto. 218 219 ### Detección de ciclos 220 221 Se puede usar el recorrido en profundidad para determinar si un grafo tiene o 222 no ciclos (si es acíclico) 223 224 ## Algoritmo de Dijkstra 225 226 El algoritmo de Dijkstra tiene muchas aplicaciones, una de ellas se aplica a 227 grafos y sirve para hallar el camino mínimo entre dos vértices cuando la arista 228 tiene peso no negativo. 229 230 Este algoritmo se caracteriza por usar la estrategia *voraz* (o *greedy* en 231 inglés) que se basa en tomar la mejor solución local (sin considerar resultados 232 previos) para avanzar con el algoritmo y llegar a un objetivo el cual solo se 233 alcanza mediante sucesivas decisiones, la estrategia termina cuando se evalúan 234 todas las posibles combinaciones de soluciones. 235 236 ## Programación dinámica 237 238 La programación dinámica es una técnica de resolución de problemas en 239 computación. Se utiliza cuando un problema puede descomponerse en subproblemas 240 más pequeños y solapados, y sus soluciones parciales pueden reutilizarse para 241 resolver el problema más grande original. Es muy similar a la técnica "divide y 242 vencerás" (en la cual se divide un problema mas grande en otros mas chicos para 243 luego combinar las soluciones) solo que en la programación dinámica los 244 problemas mas chicos a resolver están superpuestos y los resultados se guardan 245 en memoria para evitar repetir cálculos. Un ejemplo de divide y vencerás es el 246 algoritmo de ordenamiento Mergesort, en este se divide el vector a ordenar por 247 partes y cada parte se ordena de por si para luego combinar cada parte ordenada, 248 un ejemplo de programación dinámica es el calculo de Fibonacci, en el cual el 249 calculo para un numero se calcula el Fibonacci de un numero anterior y se guarda 250 en memoria, luego la solución final es la resta de todos los valores calculados 251 previamente. 252 253 ## Algoritmo de Floyd-Warshall 254 255 El Algoritmo de Floyd-Warshall es similar al Algoritmo de Dijkstra en el sentido 256 que se usa para encontrar el camino mas corto entre dos nodos. En este algoritmo 257 se aplica la técnica de programación dinámica. Es poco eficiente ya que tiene 258 una complejidad de $\mathcal{O}(n^3)$ 259 260 ## Cerradura transitiva 261 262 ## Árbol abarcador de costo mínimo 263 264 Un árbol abarcador de costo mínimo (en inglés Minimum Spanning Tree o MST) es un 265 subgrafo de un grafo no dirigido, ponderado y conectado, que conecta todos los 266 nodos con el coste total mínimo, es decir, consiste en eliminar las aristas que 267 no sean mínimas de un grafo ponderado no dirigido. 268 269 Para construir un MST se utilizan principalmente dos algoritmos, ambos 270 equivalente, el algoritmo de Kruskal y el algoritmo de Prim. 271 272 ### Algoritmo de Kruskal 273 274 El algoritmo de Kruskal es un algoritmo greedy que encuentra el árbol de 275 expansión mínima (Minimum Spanning Tree, MST) de un grafo no dirigido y 276 ponderado. 277 278 Construye un árbol con el peso total mínimo, que conecta todos los nodos del 279 grafo sin formar ciclos. 280 281 #### Pasos 282 283 1. Inicializa un conjunto vacío para el MST. 284 2. Ordena las aristas E por peso ascendente. 285 3. Para cada arista (u, v) en orden, si u y v están en componentes distintas (no 286 conectados): 287 * Añadir (u, v) al MST. 288 * Unir los conjuntos de u y v. 289 290 4. Detener cuando el MST tenga n - 1 aristas (donde n es el número de nodos). 291 292 ### Algoritmo de Prim 293 294 El algoritmo de Prim es un algoritmo greedy que encuentra el árbol de expansión 295 mínima (MST) de un grafo no dirigido y ponderado, conectando todos los vértices 296 con el menor costo total sin formar ciclos. 297 298 ## Algoritmo de Ford-Fulkerson 299 300 Este algoritmo se utiliza para encontrar el flujo máximo en una red de flujo. 301 Una red de flujo esta compuesta por: 302 303 1. Un grafo dirigido 304 2. Un vértice fuente desde donde se inicia el flujo 305 3. Un vértice sumidero donde termina flujo 306 4. Capacidades en las aristas que determinan el flujo máximo a través de ellas 307 308 ## Backtracking 309 310 La estrategia de backtracking (o retroceso) es un método de resolución de 311 problemas que pueden ser expresados en términos de elecciones de decisiones 312 secuenciales. En esta técnica se explora todas las posibles configuraciones de 313 una solución de manera sistemática y eficiente, retrocediendo cuando se 314 determina que una elección particular no conduce a una solución viable. Esta 315 técnica se puede aplicar por ejemplo para resolver un sudoku, o un laberinto, 316 representados como grafos.