Óptimo y teoría de grafos
La noción de óptimo evoca a menudo la de máximo o mínimo de una función que, como un fluido, evolucionaría de manera continua, e incluso derivable. El arsenal del análisis y del cálculo diferencial se impone entonces al espíritu. Pero la optimización concierne también, a menudo, a cantidades que no pueden tomar más que un número finito o contable de valores. Si el repertorio de técnicas derivadas del análisis ya no es entonces de ninguna utilidad, las matemáticas discretas y la teoría de grafos toman el relevo. Es el ordenador, máquina secuencial mejor adaptada a los entornos combinatorios, el que será entonces, la mayoría de las veces, puesto a contribución para resolver los problemas de óptimo.
Todos los artículos de este dossier
Problemas de coloración para todas las edades
Al asignar colores —con sus correspondientes conjuntos de restricciones— a los vértices de un grafo, entramos en el apasionante mundo de los problemas de coloreado de grafos.
Camino más corto: algoritmos de grafos | Tangente
¿Es siempre la línea recta el camino más corto de A a B? Por lo general, sí, pero cuando hay que seguir las vías delimitadas por las calles y los cruces de una ciudad, se impone otro punto de vista. ¡El algoritmo de Dijkstra nos resulta entonces de gran ayuda!
El azar al rescate de la satisfacibilidad
El universo booleano es un pequeño mundo matemático en el que solo existen dos valores: Verdadero y Falso. ¡Y, sin embargo, ya resulta complicado obtener satisfacción! Por suerte, el azar viene en nuestro auxilio: a veces, al elegir a cara o cruz, nos acercamos sorprendentemente a un máximo buscado.
Restricciones sobre los grados de los vértices de un grafo | Tangente
¿Cuál es el grafo más pequeño que tiene un conjunto dado de grados? Hace cuarenta años, un artículo respondió de manera elegante y constructiva a esta pregunta.
El arte de no cruzarse
Artistas que utilizan las matemáticas: nada nuevo. Artistas que plantean problemas de optimización que los matemáticos todavía no saben resolver: ¡eso sí que sorprende! Una conjetura, anodina en apariencia, sobre la representación de grafos lleva cincuenta años resistiéndose.