Aproximación para colorear al azar un grafo con 2 colores.

Answer

1. 

   davy.ai

   July 15, 2023 at 10:22 pm

   Para demostrar que este algoritmo de asignación de colores aleatoria es una “aproximación de 4”, necesitamos demostrar que el peso de las aristas coloreadas entre “rojo” y “azul” es al menos 1/4 del peso total de las aristas en el grafo.

   Sea “OPT” la solución óptima, es decir, el peso máximo de las aristas coloreadas entre “rojo” y “azul”.

   Ahora, consideremos el peso esperado de las aristas coloreadas entre “rojo” y “azul” en la coloración aleatoria.

   Sea “W” el peso de las aristas coloreadas entre “rojo” y “azul” en la coloración aleatoria.

   Dado que marcamos cada vértice de forma aleatoria con “rojo” o “azul” con probabilidad de 1/2 y la coloración se realiza de forma independiente para cada vértice, podemos modelar cada vértice como una moneda lanzada, donde “caras” representan un color y “cruces” representan el otro color.

   Entonces, el peso esperado de las aristas entre “rojo” y “azul” se puede calcular de la siguiente manera:

   E[W] = suma del peso esperado de las aristas en cada vértice
   

   E[W] = suma de {probabilidad de que el vértice sea rojo * peso de las aristas desde ese vértice hasta azul} +
          suma de {probabilidad de que el vértice sea azul * peso de las aristas desde ese vértice hasta rojo}
   

   E[W] = (1/2) * suma de {peso de las aristas desde ese vértice hasta azul} +
          (1/2) * suma de {peso de las aristas desde ese vértice hasta rojo}
   

   E[W] = (1/2) * suma de {peso de las aristas desde ese vértice}
   

   E[W] = (1/2) * peso total de las aristas en el grafo
   

   Por lo tanto, tenemos que “E[W] = (1/2) * peso total de las aristas en el grafo”.

   Ahora, necesitamos demostrar que “W >= (1/4) * OPT”.

   Consideremos cualquier coloración óptima del grafo. En esta coloración óptima, sea “B” el conjunto de vértices que son “azules”.

   Sea “W(B)” el peso de las aristas desde los vértices “rojos” a los vértices “azules” en esta coloración óptima.

   Sea “R” el conjunto de vértices que son “rojos”.

   Sea “W(R)” el peso de las aristas desde los vértices “azules” a los vértices “rojos” en esta coloración óptima.

   OPT = W(B) + W(R)
   

   Ahora, consideremos el valor esperado de “W” en la coloración aleatoria.

   E[W] = (1/2) * suma de {peso de las aristas desde ese vértice hasta el color opuesto}
   

   E[W] = (1/2) * (W(B) + W(R))
   

   Dado que tanto “W(B)” como “W(R)” son no negativos, tenemos

   W(B) + W(R) >= 2 * W(sqrt(W(B)*W(R)))
   

   Usando esta desigualdad, podemos escribir:

   W(B) + W(R) >= 2 * W(sqrt(OPT/4))
   

   W(B) + W(R) >= 2 * (OPT/2)
   

   W(B) + W(R) >= OPT
   

   Por lo tanto, hemos demostrado que “W >= (1/4) * OPT” y, por lo tanto, el algoritmo de asignación de colores aleatoria es una “aproximación de 4”.

Comments are closed.