Teoria D Grafos

Los grafos en nuestra vida diaria

Estamos rodeados de cosas que nos parecen de lo más cotidianas y sin embargo, no pensamos frecuentemente que éstas formen parte de las Matemáticas. Un ejemplo, son las carreteras, líneas telefónicas, circuitos eléctricos de nuestras casas, los organigramas de una empresa, los árboles genealógicos,... que suponen un claro ejemplo de la aplicación de algo que en Matemáticas llamamos Grafos.

Los grafos nos permiten expresar las relaciones existentes entre elementos de muy diversa índole. Por ejemplo, los planos de las líneas de metro de una ciudad son grafos que muestran la conexión entre sus paradas. La imagen de la derecha corresponde a la red de metro de Madrid.

De una manera muy elemental, podemos decir que un grafo es un conjunto no vacío de elementos llamados vértices o nodos, y un conjunto de pares de vértices llamados aristas que pueden ser orientados o no. Así, un grafo está representado por una serie de puntos (vértices) conectados por líneas (aristas). Un ejemplo, es el grafo del dodecaedro representado en la siguiente imagen.

Ejemplo de grafo. Fuente

El estudio de las propiedades de los grafos ha dado lugar a una completa teoría matemática denominada Teoría de Grafos. El primer resultado de esta teoría fue el trabajo de Leonhard Euler sobre el problema de los PUENTES DE KÖNIGSBER, una ciudad prusiana atravesada por el río Pregolya y cuyos siete puentes permitían a sus habitantes recorrer las distintas zonas en que éste dividía a la ciudad. Sus habitantes plantearon el reto de encontrar una ruta que recorriera los siete puentes cruzando cada uno de ellos una sola vez y regresando al punto de partida. La siguiente imagen representa dichos puentes.

Puentes de Königsberg. Fuente

Por más que lo intentaron, los habitantes de Königsber nunca encontraron dicha ruta. Y fue Leonhard Euler quien demostró matemáticamente que tal recorrido era imposible, indicando las condiciones para que una ruta de tales características fuese factible. De este modo, nació la Teoría de Grafos cuyas aplicaciones están extendidas a los distintos campos del saber(economía, sociología, psicología, lingüística, ingeniería, etc.).

Así, los grafos nos ayudan a resolver gran variedad de problemas. Un ejemplo típico consiste en el problema de colorear un mapa plano asignando colores distintos a regiones vecinas, pero utilizando el mínimo número de colores posible.

¿Cuál es el mínimo número de colores necesarios para colorear el siguiente mapa?

...