teoría de grafos –

Nacido de la investigación de Euler en xviii^mi s., la teoría de grafos se convirtió en una rama de las matemáticas al comienzo de la xx^mi s., gracias a las obras de König, Kuratowski, Cayley y, más recientemente, Berge, Erdös y Harary.

La investigación reciente en informática y especialmente en algoritmos le está dando una nueva vida. La teoría de grafos puede resolver eficazmente una amplia variedad de problemas prácticos o recreativos reduciéndolos a configuraciones que simplemente se dibujan con la ayuda de puntos y conexiones entre estos puntos.

La teoría de las gráficas

La teoría de grafos se remonta generalmente al problema de los llamados “puentes de Königsberg” (Kaliningrado). Resuelto por Leonhard Euler en 1736, este problema, que parece un rompecabezas, dice lo siguiente: ¿es posible, partiendo de una zona de la ciudad, volver a la misma zona cruzando cada uno de sus siete puentes una sola vez? ¿una vez?

La teoría de grafos se utiliza sobre todo para representar y organizar tareas de manera óptima: después de haber traducido un problema en forma de gráfico, buscamos métodos sistemáticos que permitan encontrar la sucesión más rápida o menos costosa para realizar todas las tareas. Tareas.

De hecho, sus aplicaciones prácticas son muy diversas: optimización de redes de transporte – transporte por carretera o transporte de información -, diseño de redes eléctricas, redes de comunicación, mecánica estadística, fórmulas químicas, informática teórica, ciencias sociales, geografía, arquitectura …

¿Qué es una gráfica?

Fue en 1822 cuando el inglés JJ Sylvester introdujo la palabra “grafo”, y en 1936 apareció el primer libro sobre teoría de grafos, escrito por D. König. Un gráfico es un dibujo geométrico definido por los datos de un conjunto de puntos (llamado picos Dónde nudos), unidos entre sí por un conjunto de líneas o flechas (llamado bordes Dónde arcos). Cada borde tiene por extremos dos puntos, posiblemente coincidentes. El gráfico se dice orientado si, para cada borde, distinguimos un final inicial y un final terminal.

Las propiedades de los gráficos caracterizan diferentes tipos de problemas:

– se dice un gráfico lleno cuando dos vértices distintos y no especificados están conectados por un solo borde;

– se dice un gráfico relacionado si podemos conectar dos vértices cualesquiera del gráfico mediante una serie continua de aristas.

a árbol es un gráfico conectado que no contiene una ruta cerrada. Ejemplos de uso de árboles, o árboles, se encuentran en la gestión de la base de datos. Conocer el árbol según el cual se organiza la información facilita y optimiza su consulta. La estructura paralela de las computadoras se realiza de acuerdo con un procedimiento de programación de tareas: actualmente es un campo de investigación extremadamente activo en ciencias de la computación matemática.

Gráficos planos

Se dice una gráfica planar si se puede dibujar sobre una superficie topológicamente plana de modo que los bordes no se crucen. Este tipo de gráfico se utiliza particularmente en los problemas de los circuitos impresos (estos circuitos, construidos sobre superficies planas, constituyen actualmente una de las limitaciones de los desarrollos del procesamiento de datos).

El clásico problema recreativo de tres pozos y tres casas permitió al polaco Kazimierz Kuratowski encontrar en 1930 una caracterización de grafos planos: un grafo es plano si y solo si su configuración no contiene tres nodos conectados a otros tres nodos, o cinco nodos todos conectado a los otros cuatro.

Otra aplicación de los gráficos planos es la representación de poliedros en forma de gráficos. Hay dos maneras de hacer esto:

– dibujar los vértices y las aristas del poliedro mirándolo a través de un agujero hecho en un vértice (obtenemos una gráfica abierta que comprende aristas que tienen un solo extremo);

– Dibujar el poliedro mirándolo a través de una cara (luego obtenemos un gráfico cerrado).

Además, las gráficas planas verifican la fórmula de Euler-Poincaré relacionando el número S de vértices, el número F de caras (o regiones) con el número A de aristas: S + F = A + 2. Esta fórmula también es válida para todos poliedros convexos.

Flujos y tensiones en la teoría de grafos

La teoría de grafos también tiene muchas aplicaciones prácticas en el campo de la gestión, que utiliza los llamados grafos valorados. Los bordes o vértices del gráfico se ven afectados por un parámetro económico correspondiente a determinadas limitaciones: costes (transporte, distancias, tiempos de trabajo, existencias, etc.) o rendimientos (tráfico de automóviles, corriente eléctrica, rendimientos de ventas, información binaria, etc.) .

Dos tipos de problemas caracterizan este campo: el de la programación de tareas y el del viajante de comercio.

Problema de programación de tareas y gráficos

La programación de tareas consiste en planificar las diversas tareas que conducen a la realización de un producto en una línea de producción o un gran proyecto de construcción. Cada vértice del gráfico está asociado con un número que caracteriza a un evento (fecha o fecha límite de finalización, por ejemplo). Los bordes también pueden llevar valores correspondientes a otras restricciones (tiempo mínimo entre dos eventos, por ejemplo). Tenemos un problema de tensión típico: encontrar un camino óptimo o un camino crítico entre el principio y el final del proceso.

Un problema de gráfico: el viajante de comercio

El viajante de comercio debe encontrar la ruta más corta que, partiendo de una ciudad, regrese a ella pasando por todas las demás. Los bordes llevan valores correspondientes a distancias, que se pueden medir en tiempo, en costos de viaje, en caudales de electricidad o agua, etc. Este tipo de problemas tiene soluciones que tardan más en encontrar que el número de ciudades es grande. Si con 10 ciudades se necesitan, por ejemplo, 64 pasos de cálculo (realizados en un microsegundo por una computadora), con 100 ciudades, se necesitarían 2⁶⁴ etapas de cálculos, que movilizarían una computadora durante cientos de años.

Algoritmos eficientes

Los algoritmos permiten encontrar una solución óptima a estos problemas, con una eficiencia acorde al número de parámetros. Citemos los más famosos:

– el método de la ruta crítica, que determina el margen de maniobra en cada nodo;

– el método PERT (tarea de evaluación e investigación del programa), que permite encontrar soluciones en los problemas de tensión introduciendo, para medir los tiempos de trabajo en cada puesto, un valor medio calculado a partir de probabilidades optimistas y pesimistas. Sin obtener aún soluciones exactas, se obtienen soluciones aproximadas muy satisfactorias.

Computabilidad y complejidad según la teoría de grafos

La teoría de grafos ilustra un enfoque matemático para la resolución de problemas que ahora está experimentando numerosos desarrollos gracias a la informática. Hay tres etapas en este proceso:

– mostrar que hay una o más soluciones posible al problema planteado;

– demuestre que esta solución es calculable utilizando un algoritmo que se puede programar;

– asegúrese de que este algoritmo sea eficaz, que conduce a la solución en un tiempo de cálculo razonable, que no aumenta exponencialmente en función del número de parámetros.

Esta última etapa es un campo de investigación matemática que se ha desarrollado desde 1935, a partir del trabajo de K. Gödel, A. Church y A. Turing.

Problemas aparentemente tan similares como los caminos eulerianos o los caminos hamiltonianos son problemas de complejidad muy diferente. La búsqueda de soluciones en cada tipo de problema conduce a algoritmos de muy diferente eficiencia. Los caminos eulerianos se encuentran gracias a algoritmos que tienen tiempos de cálculo razonables: corresponden a problemas de baja complejidad. Los caminos hamiltonianos se encuentran gracias a algoritmos cuyos tiempos de cálculo aumentan exponencialmente con el número de vértices a conectar: ​​responden a problemas algorítmicos difíciles, llamados problemas complejos. Tenga en cuenta que los problemas eulerianos tienen una caracterización simple, mientras que no ocurre lo mismo con los problemas hamiltonianos.

Los últimos avances en teoría de grafos

Desde la década de 1930, y cada vez más durante los últimos veinte años, la teoría de grafos ha experimentado desarrollos muy importantes, tanto teóricamente como en términos de aplicaciones. Se abordan una amplia variedad de problemas mediante el estudio de gráficos asociados:

– estudio de rutas eulerianas o hamiltonianas;

– estudio de gráficos planos y representación en diferentes superficies;

– propiedades algebraicas de gráficos (flujos y tensiones);

– problema de coloración de gráficos (del cual el teorema de los cuatro colores, demostrado por Appel y Haken en 1976, es el ejemplo más famoso);

– finalmente, ciertos conceptos de grafos pueden extenderse con éxito a familias de conjuntos, estos son los hipergrafos.

La teoría de grafos tiene muchos vínculos con la mayoría de las otras áreas de las matemáticas discretas: combinatoria, teoría de conjuntos, teoría de grupos, álgebra lineal, teoría de poliedros, programación lineal, teoría de juegos, algorítmica …