Estoy pensando en destruir todos los ciclos de longitud impar mediante la eliminación de los bordes, para que obtener un grafo bipartito, con un % de partición $V_1$y $V_2$ para que ningún borde en el gráfico de nuevo correr dentro de las dos partes. Entonces el peor de los casos en la adición de nuevo los bordes quita, es que estos bordes todos ejecutan dentro de cada parte. Así que me gustaría mostrar que puedo destruir a todos los ciclos impares eliminando a más de la mitad de todos los bordes. ¿Alguien me puede decir si estoy pensando en la dirección correcta?
Respuestas
¿Demasiados anuncios?
Considere la posibilidad de comenzar con un gráfico de $G$ y particiones de sus vértices en $V_1$ $V_2$ observando cada vértice de uno en uno y de asignar a $V_1$ o $V_2$ (a partir de la con $V_1$ $V_2$ tanto vacío): si el vértice $v$ tiene más aristas de ir a $V_1$$V_2$, se debe asignar a $V_2$, de lo contrario asignar a $V_1$. Si usted asigne $v$$V_i$, el color de cada borde de $v$ $V_i$rojo, y en cada extremo de $v$ $V_{3-i}$azul. Luego siempre habrá, al menos, como muchos azul en los bordes de los bordes rojos. Cuando el proceso haya terminado, todos los bordes serán de color, aquellos dentro de $V_1$ o $V_2$ será de color rojo y los de entre $V_1$ $V_2$ azul.
John Smith
Puntos
53
Este es un problema clásico donde el Método de probabilidades da una muy buena solución.
Considerar el efecto de los asignados al azar a cada vértice, de forma independiente y de forma idéntica, a $V_1$ o $V_2$ con una probabilidad de $1/2$. En este caso, se espera que el número de aristas que se cruzan las dos mitades es $m/2$. Esto implica que hay una probabilidad positiva de la partición de los vértices de manera que el real (en contraposición a la espera) número de aristas de cruce de las dos mitades es, al menos,$m/2$. En particular, la partición existe.
