Una bastante interesante es la existencia de separadores, un conjunto de vértices que desconecta el gráfico en partes más o menos equilibradas; eso también en tiempo lineal solamente (en número de vértices). Esto ayuda a diseñar algoritmos eficientes de divide y vencerás específicamente para gráficos planos.
Para decirlo más formalmente, el teorema del separador plano establece que: dado cualquier gráfico plano G, podemos encontrar una partición del conjunto de vértices V en tres conjuntos A, B, C; tal que no exista borde entre los vértices en A y los vértices en B, C tiene un tamaño como máximo [math] \ sqrt {8n} [/ math], y A y B tienen un tamaño no mayor que [math] 2n / 3 [/ math ] (donde n es el tamaño de V)
Esto fue demostrado por Lipton y Tarjan en su artículo titulado “Un teorema del separador para gráficos planos”. En realidad, demostraron un resultado más fuerte: si los vértices tienen pesos que suman no más de 1, los conjuntos A y B habrían costado al menos [matemáticas] 2/3 [/ matemáticas].
- ¿Qué es mejor, #define PI o const double PI?
- Matemáticamente hablando, ¿una probabilidad negativa significa algo?
- ¿Cuáles son todos los términos del "Teorema de la gran ortogonalidad"?
- ¿Cuál es la forma más efectiva de aprender matemáticas abstractas?
- A menudo se dice que las matemáticas son un juego de hombres (y mujeres) y, de hecho, parece que los grandes matemáticos suelen hacer sus primeros descubrimientos importantes a una edad temprana. ¿Es esto realmente cierto, y si es así, a qué edad es el caso de que, si uno aún no ha hecho un gran trabajo, debería aceptar que no están hechos para ser uno de los grandes?
El límite superior del tamaño del conjunto C fue mejorado más tarde por Djidjev a [math] \ sqrt {6n} [/ math]. Para los gráficos con propiedades adicionales (como ser máximo plano, o 2-conectado), Miller y otros demostraron que el separador puede ser un ciclo simple.