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 79: | Línea 79: | ||
==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:== |