Edición de «Práctica 10: Matching - Flujo Máximo (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 73: | Línea 73: | ||
==Ejercicio 10.04:== | ==Ejercicio 10.04:== | ||
Si G tiene un conjunto independiente de n nodos, entonces cada uno esta en un clique distinto, y el cubrimiento minimo tiene por lo menos n cliques -> |I|<=|Rn| | |||
==Ejercicio 10.05:== | ==Ejercicio 10.05:== | ||
Probar que si G es bipartito, m <= <math>\alpha * \beta </math>, donde <math>\alpha</math>=#(conj. indep. maximo) y <math>\beta</math>=#(Recubrimiento minimo de aristas) | Probar que si G es bipartito, m <= <math>\alpha * \beta </math>, donde <math>\alpha</math>=#(conj. indep. maximo) y <math>\beta</math>=#(Recubrimiento minimo de aristas) | ||
<br>Sea: <math>v \in \real</math>, y V1,V2 las particiones de G | |||
<br><math>m \leq 2*m = \sum d(v) \leq max(|V1|,|V2|)* \beta \leq \alpha * \beta </math> | |||
Me parece que eso no esta bien.. que alguien chequee.. porque si tengo un bipartito K_33, tengo que alfa = 3 y beta = 3, entonces 2*9 <= 3*3 no es verdadero.... | |||
Otra solución es: | |||
<br> P1 = conj nodos de 1era particion. | |||
<br> P1 = conj nodos de 2da particion. | |||
<br> Ca = conj de nodos aislados. | |||
<br> m<=|P1||P2| | |||
<br> alfa = max(|P1|,|P2|)+|Ca| | |||
<br> beta = min(|P1|,|P2|) | |||
<br> alfa*beta = |P1|*|P2|+min(|P1|,|P2|)*|Ca| | |||
<br> por lo tanto: | |||
<br> |P1|*|P2| = alfa*beta - min(|P1|,|P2|)*|Ca| | |||
<br> m <= alfa*beta - min(|P1|,|P2|)*|Ca| <= alfa*beta. | |||
Creo que esto tampoco esta del todo bien, no es cierto que <br> beta = min(|P1|,|P2|) | |||
Si tenes el grafo bipartito P1 = (1,2,3,4) , p2 = (5,6,7,8) con los ejes | |||
<br> {(2,6),(3,6),(4,5),(4,7),(4,8)}, | |||
el recrubrimiento minimo se alcanza con los nodos 4 y 6, entonces beta = 2 != min(|P1|,|P2|) = 3 (el nodo 1 esta aislado). Igual no se me ocurre bien como hacerlo... | |||
otra forma | |||
<math>\alpha</math>=#(conj. indep. maximo) y <math>\beta</math>=#(Recubrimiento minimo de aristas) | |||
<br><math>m \leq \sum d(v) \leq \sum I = \alpha * \beta </math> | |||
la <math>\sum d(v) </math>, es de 1 hasta el cardinal del recubrimiento minimo de aristas. | |||
'''Otra forma simple y en criollo:''' | |||
En un bipartito '''sin nodos aislados''' entonces alfa y beta son iguales al maximo entre |P1| y |P2| dado que el maximo conjunto independiente va a ser el tamaño de la partición más grande, y el minimo numero de aristas que se necesitan para cubrir a todos los nodos también, porque sino va a haber nodos en la particion grande que van a quedar sin cubrir. | |||
Ademas, m <= |P1|*|P2| porque a lo sumo se tiene tantas aristas como en el completo que "le corresponde". | |||
En contreto, sea M el maximo entre |P1| y |P2|, por lo anterior | |||
alfa = beta = M | |||
Entonces: | |||
m <= |P1|*|P2| <= M*M = alfa*beta | |||
Y si '''se tiene k nodos aislados''' entonces aglutinamos todos | |||
los nodos aislados en la particion mas grande. | |||
Ahora ellos no contribuyen aristas, con lo cual, si llamamos n' y m' al numero de nodos y aristas del grafo que resulta de eliminar los k nodos aislados, se tiene que: | |||
m' = m y n' = n - k <= n | |||
y ademas | |||
alfa' = alfa - k | |||
donde alfa' es el conjunto independiente maximo del grafo sin los nodos aislados. | |||
Ahora, por lo anterior tenemos que beta' = beta (porque no cambiamos las aristas) y que: | |||
m' <= alfa' * beta' = (alfa - k) beta <= alfa * beta | |||
==Ejercicio 10.06:== | ==Ejercicio 10.06:== | ||
Línea 156: | Línea 204: | ||
==Ejercicio 10.18:== | ==Ejercicio 10.18:== | ||
==Ejercicio 10.19:== | ==Ejercicio 10.19:== | ||
Agregar s conectado a x1, x2, x3, con capacidad 5, 10, 5 respectivamente, y agregar t conectado a y1, y2, y3 con flujo entre [5..inf],[10..inf],[5..inf] respectivamente | Agregar s conectado a x1, x2, x3, con capacidad 5, 10, 5 respectivamente, y agregar t conectado a y1, y2, y3 con flujo entre [5..inf],[10..inf],[5..inf] respectivamente | ||
Línea 182: | Línea 221: | ||
==Ejercicio 10.22:== | ==Ejercicio 10.22:== | ||
<br>a)Cambios los ejes por ejes direccionados en ambas vias con capacidad 1, y | <br>a)Cambios los ejes por ejes direccionados en ambas vias con capacidad 1, y buscao el flujo maximo. | ||
<br>b) | <br>b) | ||