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 $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 $W\subset V$ tal que G \ W tiene c componentes conexas con $c>|W|$ entonces G no es hamiltoniano.

• Sea G un grafo con n ≥ 3 y tal que para todo $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 $v,w$ no adyacentes se verifica que $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.

• $K_{5}$ y $K_{3,3}$ son grafos no planares. $K_{5}$ es el grafo no planar con el menor número de nodos y $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 $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 $K_{3,3}$ o $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 $K_{3,3}$ o $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, $K_{2}$ determina una región con una frontera de tamaño dos (la región exterior).

• Si G es planar, entonces $2m=\sum _{f\in F}|f|$, donde $|f|$ es el tamaño de la región f y F es el conjunto de regiones.

• Si G es planar y conexo, entonces $n-m+r=2$ (ecuación de Euler)

• Si G es planar y $n\geq 3$, entonces $m\leq 3n-6$ (corolario)

• Si G es planar, conexo, bipartito y $m\geq 1$, entonces $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 $\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 $K_{3}$, el polinomio cromático es $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

• $\chi (K_{n})=n$

• Si G es un grafo bipartito con m > 0, entonces $\chi (G)=2$

• Si G es un circuito simple par, entonces $\chi (G)=2$

• Si G es un circuito simple impar, entonces $\chi (G)=3$

• Si T es un árbol con n > 1, entonces $\chi (G)=2$

• Si H es subgrafo de G, entonces $\chi (H)\leq \chi (G)$

• Si $\omega (G)$ es el número de nodos de una clique máxima de G, entonces $\chi (G)\geq \omega (G)$

• Si d es el grado del nodo de mayor grado, entonces $\chi (G)\leq d(G)+1$

• Si G es un grafo conexo que no es un circuito impar ni un grafo completo con $d(G)\geq 3$, entonces $\chi (G)\leq d(G)$ (Teorema de Brooks)

• Si G es un grafo planar, entonces $\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 $|M|\leq n/2$ (redondeado hacia abajo).

• Cualquier recubrimiento de nodos Re (conjunto de ejes) verifica que $|R_{e}|\geq n/2$ (redondeado hacia arriba), pues deben cubrir todos los nodos.

• Por lo tanto, $|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 $|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 $|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 $|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 $|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 $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, $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, $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 $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 $O(m^{2}*n)$.