Edición de «Resumen (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 1: | Línea 1: | ||
= Segundo Parcial = | = Segundo Parcial = | ||
Línea 6: | Línea 4: | ||
* Un circuito C en un grafo G se llama un circuito euleriano si C pasa por todos los ejes de G una y sólo una vez. Un grafo es euleriano si contiene un circuito euleriano. | * Un circuito C en un grafo G se llama un circuito euleriano si C pasa por todos los ejes de G una y sólo una vez. Un grafo es euleriano si contiene un circuito euleriano. | ||
** Teorema de Euler: Un grafo conexo es euleriano si y sólo si todos sus nodos tienen grado par. | ** Teorema de Euler: Un grafo conexo es euleriano si y sólo si todos sus nodos tienen grado par. | ||
* Un camino euleriano en un grafo G es un camino que pasa por cada eje de G una y sólo una vez. | * Un camino euleriano en un grafo G es un camino que pasa por cada eje de G una y sólo una vez. | ||
** Un grafo conexo tiene un camino euleriano si y sólo si tiene exactamente dos nodos de grado impar y el resto de los nodos tiene grado par. | ** Un grafo conexo tiene un camino euleriano si y sólo si tiene exactamente dos nodos de grado impar y el resto de los nodos tiene grado par. | ||
* Un grafo orientado o digrafo, se dice euleriano si tiene un circuito orientado que pasa por cada eje de G una y sólo una vez. | * Un grafo orientado o digrafo, se dice euleriano si tiene un circuito orientado que pasa por cada eje de G una y sólo una vez. | ||
** Un digrafo conexo es euleriano si y sólo si para todo nodo v de G se verfica que <math> | |||
** Un digrafo conexo es euleriano si y sólo si para todo nodo v de G se verfica que <math>d_in (v) = d_out (v)</math> | |||
* El problema de grafos eulerianos está bien resuelto para todas estas versiones. | * El problema de grafos eulerianos está bien resuelto para todas estas versiones. | ||
Línea 27: | Línea 31: | ||
=== Viajante de comercio === | === Viajante de comercio === | ||
* El problema del viajante de comercio consiste en hallar un circuito hamiltoniano de | * El problema del viajante de comercio consiste en hallar un circuito hamiltoniano de longitud minima en un grafo. | ||
* No es un problema bien resuelto, hay muchas heurísticas para resolverlo. Si las distancias en el grafo son euclideanas, entonces algunas heurísticas son epsilon aproximadas. | * No es un problema bien resuelto, hay muchas heurísticas para resolverlo. Si las distancias en el grafo son euclideanas, entonces algunas heurísticas son epsilon aproximadas. | ||
Línea 36: | Línea 40: | ||
* <math>K_5</math> y <math>K_{3,3}</math> son grafos no planares. <math>K_{5}</math> es el grafo no planar con el menor número de nodos y <math>K_{3,3}</math> es el que tiene el menor número de ejes. | * <math>K_5</math> y <math>K_{3,3}</math> son grafos no planares. <math>K_{5}</math> es el grafo no planar con el menor número de nodos y <math>K_{3,3}</math> es el que tiene el menor número de ejes. | ||
=== Teorema de Kuratowski === | === Teorema de Kuratowski === | ||
* Subdividir un eje e = (v,w) de un grafo G, consiste en agregar un nodo | * Subdividir un eje e = (v,w) de un grafo G, consiste en agregar u un nodo a G y reemplazar el eje e por dos ejes e'= (v,u) y e" = (u,w). | ||
* Un grafo G' es una subdivisión de otro grafo G si G' se puede obtener de G por sucesivas operaciones de subdivisión. | * Un grafo G' es una subdivisión de otro grafo G si G' se puede obtener de G' por sucesivas operaciones de subdivisión. | ||
* Dos grafos G y H se dicen homeomorfos si hay un | * Dos grafos G y H se dicen homeomorfos si hay un issomorfismo entre una subdivisión de G y una de G'. | ||
* Un grafo es planar si y sólo si no contiene ningún subgrafo homeomorfo a <math>K_{3,3}</math> o <math>K_{5}</math>. | * Un grafo es planar si y sólo si no contiene ningún subgrafo homeomorfo a <math>K_{3,3}</math> o <math>K_{5}</math>. | ||
Línea 63: | Línea 65: | ||
* La frontera de una región es el circuito que rodea a la región (puede tener nodos y ejes repetidos). | * La frontera de una región es el circuito que rodea a la región (puede tener nodos y ejes repetidos). | ||
* El grado o tamaño de la región es el número de ejes que tiene su frontera. Por ejemplo, <math>K_{2}</math> determina una región con una frontera de | * El grado o tamaño de la región es el número de ejes que tiene su frontera. Por ejemplo, <math>K_{2}</math> determina una región con una frontera de dos ejes. | ||
* Si G es planar, entonces <math>2m = \sum _{f \in F} |f|</math>, donde <math>|f|</math> es el tamaño de la región f y F es el conjunto de regiones. | * Si G es planar, entonces <math>2m = \sum _{f \in F} |f|</math>, donde <math>|f|</math> es el tamaño de la región f y F es el conjunto de regiones. | ||
Línea 119: | Línea 121: | ||
** M es un matching máximo si y sólo si no existe un camino alternado entre pares de nodos no saturados. | ** M es un matching máximo si y sólo si no existe un camino alternado entre pares de nodos no saturados. | ||
* Un '''conjunto independiente''' I de nodos de G, es un conjunto de nodos tal que para todo eje del grafo, e es incidente a lo sumo a un nodo v de I. Es decir, en el subgrafo inducido por I, todos los nodos son aislados | * Un '''conjunto independiente''' I de nodos de G, es un conjunto de nodos tal que para todo eje del grafo, e es incidente a lo sumo a un nodo v de I. Es decir, en el subgrafo inducido por I, todos los nodos son aislados. | ||
* Un '''recubrimiento de los ejes''' de G, es un conjunto Rn de nodos tal que para todo eje e de G, e es incidente al menos a un nodo v de Rn. Es decir, '''vertex cover''' | * Un '''recubrimiento de los ejes''' de G, es un conjunto Rn de nodos tal que para todo eje e de G, e es incidente al menos a un nodo v de Rn. Es decir, '''vertex cover'''. | ||
* Un '''recubrimiento de los nodos de G''', es un conjunto Re de ejes tal que para todo nodo v de G, v es incidente al menos a un eje e de Re | * Un '''recubrimiento de los nodos de G''', es un conjunto Re de ejes tal que para todo nodo v de G, v es incidente al menos a un eje e de Re. | ||
=== Equivalencias === | === Equivalencias === | ||
Línea 133: | Línea 135: | ||
* Por lo tanto, <math>|M| \leq |R_e|</math>. En particular, si son iguales, se trata de un matching máximo y un recubrimiento mínimo. | * Por lo tanto, <math>|M| \leq |R_e|</math>. En particular, si son iguales, se trata de un matching máximo y un recubrimiento mínimo. | ||
* También se verifica para cualquier recubrimiento de los ejes Rn (vertex cover) que <math>|M| \leq |R_n|</math>. | * También se verifica para cualquier recubrimiento de los ejes Rn (vertex cover) que <math>|M| \leq |R_n|</math>. En particular, si el grafo es bipartito, la cantidad de ejes del matching máximo es igual a la cantidad de nodos de un vertex cover mínimo. | ||
* Dado un grafo G sin vértices aislados, I un conjunto independiente máximo y Re un recubrimiento de nodos mínimo, vale que <math>|I| \leq |R_e|</math> | |||
* Dado un grafo G sin vértices aislados, I un conjunto independiente máximo y Re un recubrimiento de nodos mínimo, vale que <math>|I| \leq |R_e|</math> | |||
* Dado un grafo G, si M es un matching máximo y Re un recubrimiento mínimo de los nodos de V, entonces <math>|M| + |R_e| = n</math>. Es un problema bien resuelto. | * Dado un grafo G, si M es un matching máximo y Re un recubrimiento mínimo de los nodos de V, entonces <math>|M| + |R_e| = n</math>. Es un problema bien resuelto. | ||
Línea 166: | Línea 165: | ||
* Se utiliza el Algoritmo de Ford y Fulkerson con el Algoritmo del Camino de Aumento para resolverlo. Falla si las capacidades son números irracionales, deben ser enteros positivos (si son racionales pueden convertirse a enteros). En la práctica, se usa la variante de Edmonds y Karp que usa BFS para generar los caminos de aumento, asegurando así complejidad polinomial de <math>O(m^2*n)</math>. | * Se utiliza el Algoritmo de Ford y Fulkerson con el Algoritmo del Camino de Aumento para resolverlo. Falla si las capacidades son números irracionales, deben ser enteros positivos (si son racionales pueden convertirse a enteros). En la práctica, se usa la variante de Edmonds y Karp que usa BFS para generar los caminos de aumento, asegurando así complejidad polinomial de <math>O(m^2*n)</math>. | ||