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. | |||
==Ejercicio 10.06:== | ==Ejercicio 10.06:== | ||
Línea 156: | Línea 180: | ||
==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 197: | ||
==Ejercicio 10.22:== | ==Ejercicio 10.22:== | ||
<br>a) | <br>a)Con DFS sacando ejes usados | ||
<br>b) | <br>b)Con DFS sacando vertices usados | ||
==Ejercicio 10.23:== | ==Ejercicio 10.23:== |