Resumen (Algoritmos III)

Archivo:Back.png Volver a la página de la materia

Segundo Parcial

Grafos Eulerianos

• 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.
• 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 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle d_in (v) = d_out (v)}
• El problema de grafos eulerianos está bien resuelto para todas estas versiones.

Grafos Hamiltonianos

• Un grafo se dice hamiltoniano si tiene un circuito que pasa por cada nodo de G una y sólo una vez.

• No es un problema bien resuelto.

• Sea G un grafo conexo. Si existe Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle W \subset V} tal que G \ W tiene c componentes conexas con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle c > |W|} entonces G no es hamiltoniano.

• Sea G un grafo con n ≥ 3 y tal que para todo Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v \in V} se verifica que d(v) ≥ n/2 entonces G es hamiltoniano (Dirac).

• Sea G un grafo con n ≥ 2 tal que para todo par de vértices Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v, w} no adyacentes se verifica que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle d(v) + d(w) \geq n} entonces G es hamiltoniano (Ore).

Viajante de comercio

• 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.

Planaridad

• Un grafo es planar si puede representarse en el plano sin que sus ejes se crucen.

• Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle K_5} y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle K_{3,3}} son grafos no planares. Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle K_{5}} es el grafo no planar con el menor número de nodos y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle K_{3,3}} es el que tiene el menor número de ejes.

• Es un problema bien resuelto. Se puede usar Demoucron, Malgrange y Pertouset que demora Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle O(n^2)} en hallar una representacion planar o indicar que no existe.

Teorema de Kuratowski

• 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.

• 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle K_{3,3}} o Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle K_{5}} .

Teorema de Whitney

• La operación de contracción de un eje e= (v,w) consiste en eliminar el eje del grafo y considerar sus extremos como un solo nodo u. (quedan como ejes incidentes a u todos los ejes que eran incidentes en v y en w).

• Un grafo G' es una contracción de otro grafo G si se puede obtener a partir de G por sucesivas operaciones de contracción. En este caso se dice que G es contraible a G'.

• Un grafo es planar si y sólo si no contiene ningún subgrafo contraible a Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle K_{3,3}} o Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle K_{5}} .

Teorema de Euler

• Dada una representación planar de un grafo G, las regiones de G son los conjuntos conexos (en el sentido topológico) maximales que quedan en el plano R2 al sacar los puntos correspondientes a los nodos de G.

• 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, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle K_{2}} determina una región con una frontera de dos ejes.

• Si G es planar, entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 2m = \sum _{f \in F} |f|} , donde Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle |f|} es el tamaño de la región f y F es el conjunto de regiones.

• Si G es planar y conexo, entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n - m + r = 2} (ecuación de Euler)

• Si G es planar y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle n \geq 3} , entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle m \leq 3n - 6} (corolario)

• Si G es planar, conexo, bipartito y Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle m \geq 1} , entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle m \leq 2n - 4} (corolario)

Coloreo de Grafos

• Un coloreo válido de los nodos de un grafo G es un asignación de colores a los mismos en la cual 2 nodos adyacentes no tengan el mismo color.

• El número cromático Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \chi (G)} de un grafo G es el menor número de colores con que se puede colorear un grafo.

• El polinomio cromático de un grafo indica cuántos coloreos posibles hay en un grafo usando k colores distintos. Por ejemplo, en Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle K_{3}} , el polinomio cromático es Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle k*(k-1)*(k-2)} .

• El coloreo es un problema computacionalmente aún no resuelto, que da origen a muchos subproblemas.

Propiedades del número cromático

• Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \chi (K_n) = n}

• Si G es un grafo bipartito con m > 0, entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \chi (G) = 2}

• Si G es un circuito simple par, entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \chi (G) = 2}

• Si G es un circuito simple impar, entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \chi (G) = 3}

• Si T es un árbol con n > 1, entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \chi (G) = 2}

• Si H es subgrafo de G, entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \chi (H) \leq \chi (G)}

• Si Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \omega (G)} es el número de nodos de una clique máxima de G, entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \chi (G) \geq \omega (G)}

• Si d es el grado del nodo de mayor grado, entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \chi (G) \leq d(G) + 1}

• Si G es un grafo conexo que no es un circuito impar ni un grafo completo con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle d(G) \geq 3} , entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \chi (G) \leq d(G)} (Teorema de Brooks)

• Si G es un grafo planar, entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \chi (G) \leq 4} (Teorema de los 4 colores)

Matching, Covering, Independent Set

Sea un grafo G =(V,X).

• Una correspondencia o matching entre los nodos de G, es un conjunto M de ejes tal que para todo nodo v del grafo, v es incidente a lo sumo a un eje e de M.

• • Un nodo v se dice saturado por un matching M si hay un eje de M incidente a v.

• • Dado un matching M en G, un camino alternado en G es un camino simple donde se alternan ejes que están en M con ejes que no están en M.

• • Dados dos matchings M0 y M1 para G, si se toma el grafo G' que resulta de realizar la diferencia simétrica entre los matchings, es decir, X' = (M0 - M1) U (M1 - M0), todas las componentes conexas de G' son nodos aislados o circuitos o caminos simples con ejes alternados en M0 y M1.

• • 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 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.

Equivalencias

• Cualquier matching M verifica que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle |M| \leq n/2} (redondeado hacia abajo).

• Cualquier recubrimiento de nodos Re (conjunto de ejes) verifica que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle |R_e| \geq n/2} (redondeado hacia arriba), pues deben cubrir todos los nodos.

• Por lo tanto, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle |M| \leq |R_e|} . 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle |M| \leq |R_n|} .

• 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. (Nota de un lector: Esto no me lo creo. Para un grafo con puntos aislados, es bipartito, el matching maximo tiene 0 ejes y no existe vertex cover, quizas tengo alguna definicion mal, pero aviso por las dudas)

• Dado un grafo G sin vértices aislados, I un conjunto independiente máximo y Re un recubrimiento de nodos mínimo, vale que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle |I| \leq |R_e|} (Dem: Como un eje solo puede tocar un solo nodo de I (pq es indep), necesitas al menos tantos ejes como nodos en I para cubrir todo)

• Dado un grafo G, si M es un matching máximo y Re un recubrimiento mínimo de los nodos de V, entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle |M| + |R_e| = n} . Es un problema bien resuelto. (NDL: no entendi)

• Dado un grafo G, si I es un conjunto independiente máximo y Rn un recubrimiento mínimo de los ejes de V, entonces Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle |I| + |R_n| = n} . No es un problema bien resuelto. (No entendi)

• Dado un grafo G bipartito de m aristas, con I conjunto independiente máximo y Rn recubrimiento mínimo de aristas, vale que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle m \leq |I|*|R_n|} .

Flujo

• El problema consiste en hallar el flujo máximo en una red. En su versión tradicional, se encuentra bien resuelto.

• Un flujo factible en una red es una función f que verifica que:

• • El flujo no supera la capacidad, es decir, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle 0 \leq f(e) \leq c(e)} para todo eje e.
  • Se cumple la ley de conservación de flujo, es decir, para todo nodo distinto de s (la fuente) y t (el sumidero), la suma de los f(e) de entrada es igual a la suma de los f(e) de salida.

• El valor del flujo es la diferencia entre la suma de los f(e) de entrada del sumidero y los de salida, es decir, Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle F = \sum _{e \in In(t)} f(e) - \sum _{e \in Out(t)} f(e)}

• Un corte en la red N es un subconjunto S de V , tal que la fuente pertenece a S y el sumidero no. El conjunto de ejes que sale de S es SS, y el que llega es SS. S es el complemento de S.

• Para cualquier corte S, el valor de un flujo F es igual a la diferencia entre la suma de los f(e) que salen de S y la suma de los f(e) que entran.

• La capacidad de un corte S se define como c(S) igual a la suma de las capacidades de los ejes que salen de S.

• Vale que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle F \leq c(S)} , y siempre existe un corte tal que se verifique la igualdad. Entonces si se halla un par F, S tal que la igualdad se verifique, se tiene un flujo máximo y un corte de capacidad mínima.

• 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle O(m^2*n)} .