Teoría de grafos | un campo de las matemáticas sobre grafos

Diferentes tipos de gráficos

• La teoría de los grafos tiene muchos aspectos. Los grafos pueden ser dirigidos o no dirigidos. Un ejemplo de grafo dirigido sería el sistema de carreteras de una ciudad. Algunas calles de la ciudad son de un solo sentido. Esto significa que en esas partes sólo se puede seguir una dirección.
• Los gráficos pueden ser ponderados. Un ejemplo sería una red de carreteras, con distancias, o con peajes (para carreteras).
• Los nodos (los círculos en el esquema) de un gráfico se llaman vértices. Las líneas que conectan los nodos se llaman aristas. Puede no haber ninguna línea entre dos nodos, puede haber una línea o puede haber múltiples líneas.
• En la teoría de grafos se utilizan mucho las estructuras de Árboles, que representan estructuras jerárquicas. Un Árbol es un grafo dirigido o no dirigido en el que no hay ningún ciclo, es decir: no hay forma de ir de un vértice (por ejemplo, una ciudad) al mismo utilizando cada arista que se usa una sola vez (caminar una sola vez por cada camino que se toma).

 
Un gráfico dirigido.  

Historia

→ →

Una visualización de los siete puentes de Königberg. Leonhard Euler resolvió este problema en 1736, lo que condujo al desarrollo de la topología, y a la teoría moderna de los grafos.

Un grafo es una estructura de datos abstracta. Contiene nodos que suelen estar relacionados entre sí. Un nodo es un conjunto de datos, normalmente en forma de pares ordenados. Los nodos están conectados o no conectados a otro nodo. La relación entre los nodos suele definirse como una arista. Los grafos son útiles por su capacidad de asociar nodos con otros nodos. En la práctica, existen algunas representaciones de los grafos.

Leonhard Euler vivía en una ciudad llamada Königsberg. (Su nombre cambió a Kaliningrado en 1946). La ciudad está en el río Pregel. Hay una isla en el río. Hay algunos puentes que cruzan el río. Euler quería pasear y utilizar cada uno de los puentes una vez. Preguntó si podía hacerlo. En 1736, publicó un artículo científico en el que demostraba que esto no era posible. Hoy en día, este problema se conoce como los Siete Puentes de Königsberg. El artículo se considera el primer documento de la historia de la teoría de los grafos.

Este artículo, al igual que el escrito por Vandermonde sobre el problema del caballero, continuó con el situs de análisis iniciado por Leibniz. La fórmula de Euler sobre el número de aristas, vértices y caras de un poliedro convexo fue estudiada y generalizada por Cauchy y L'Huillier, y está en el origen de la topología.

La fusión de las ideas procedentes de las matemáticas con las de la química está en el origen de una parte de la terminología estándar de la teoría de grafos. En concreto, el término "grafo" fue introducido por Sylvester en un artículo publicado en 1878 en Nature.

Uno de los problemas más famosos y productivos de la teoría de grafos es el problema de los cuatro colores: "¿Es cierto que cualquier mapa dibujado en el plano puede tener sus regiones coloreadas con cuatro colores, de forma que dos regiones cualesquiera que tengan un borde común tengan colores diferentes?"

 
El mismo problema, pero utilizando un gráfico  


El problema del puente de Königsberg, en un mapa de la ciudad  

La teoría de los grafos en perspectiva

La teoría de grafos es una parte importante de las matemáticas y la informática. Para muchos de estos problemas existen soluciones exactas. Sin embargo, muchas veces son muy difíciles de calcular. Por ello, muy a menudo se utilizan aproximaciones. Hay dos tipos de tales aproximaciones, los algoritmos de Monte-Carlo y los algoritmos de Las-Vegas.

 

Páginas relacionadas

• Estructura de datos