Resumen (Algoritmos III)

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 peso minimo en un grafo con pesos en sus aristas.

• 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 un nodo u 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 isomorfismo entre una subdivisión de G y una de H.

• 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 tamaño dos (la región exterior).

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

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

• 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. Es decir, edge cover. Resoluble en tiempo polinomial.

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)

(Nota de otro lector: El problema es que tomas vertex cover como cubrimiento de vertices, para la bibliografia en ingles vertex cover es recubrimiento de aristas, por lo que en el ejemplo el matching maximo tiene 0 ejes y el vertex cover tiene 0 vertices porque no hay aristas). (Nota de lector 2 : el teorema que se puede consultar en el gross pagina 568 se llama konig,1931 )

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

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

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