Sobre puentes, palomas y colores

Publicado por Miguel Rubio

Hay una leyenda urbana que dice que las teorías matemáticas son complicadas y están llenas de fórmulas inentendibles para la mayoría de los mortales. Nada más lejos de la realidad. Una prueba de esto es la llamada teoría de grafos: Los grafos se utilizan para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, se emplean en problemas de control de producción, para proyectar redes de ordenadores, para diseñar módulos electrónicos modernos, se usan para la solución de problemas de genética y problemas de automatización.

Entre las aplicaciones de la teoría de grafos que se han vuelto importantes en la actualidad podemos encontrar el estudio de las redes sociales, cuya importancia radica en el adecuado almacenamiento de datos.

La lista de aplicaciones no terminaría nunca: biología, genética, ecología, ingeniería, economía, sociología……es muy difícil encontrar un área de la actividad humana donde no se aplique la teoría de grafos.

Sin embargo es una estructura simple y muy intuitiva: consiste en un conjunto de puntos llamados vértices que están unidos por unos arcos llamados aristas. Eso es todo.

La historia comenzó cuando el matemático Leonhard Euler en 1736 visitó la ciudad de Königsberg, en Prusia Oriental, que actualmente es la ciudad rusa de Kaliningrado, atravesada por el río Pregel, que la divide en cuatro regiones.

Estas cuatro regiones estaban entonces unidas por siete puentes que las conectaban entre sí y los habitantes de la ciudad se entretenían por las tardes tratando de encontrar un recorrido para pasar por todos los puentes pero una sola vez por cada uno, regresando al punto de inicio. Euler demostró que esto era imposible, y para hacerlo creo la estructura que hoy se conoce como grafo.

El trabajo de Leonhard Euler sobre el problema titulado La solución de un problema relativo a la geometría de la posición , es considerado el primer resultado de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría.

El razonamiento de Euler fue sencillo y elegante: si llegamos a un vértice desde alguna arista, entonces el único modo de salir de ese vértice es por una arista diferente. Esto significa que tanto el vértice inicial como el final serían los únicos que podrían estar conectados con un número impar de aristas. Sin embargo, el requisito adicional del problema dice que el vértice inicial debe ser igual al final, por lo que no podría existir ningún vértice conectado con un número impar de aristas.

En particular, como en este diagrama los cuatro vértices poseen un número impar de aristas incidentes (tres de ellos inciden en tres aristas, y el restante incide en cinco), entonces se concluye que es imposible definir un camino con las características buscadas que son los 7 puentes de Königsberg.

Un caso particular de grafo muy importante es el llamado diagrama de Hasse, creado por el matemático alemán Helmut Hasse.

Un diagrama de Hasse es un grafo al que se le ha quitado todas las aristas que pueden deducirse con las propiedades reflexiva y transitiva y todos sus bucles.

Cuando dos vértices están unidos por una arista se dice que son adyacentes. Imaginemos que coloreamos los vértices con dos colores, digamos rojo y azul. Nos interesa saber bajo que condiciones los vértices adyacentes tienen el mismo color o no. Esta es la esencia de la llamada Teoría de Ramsey, una teoría que combina los grafos con un área de la Matemática conocida como Combinatoria.

La combinatoria se basa en unos principios matemáticos muy sencillos, como el llamado principio del palomar: si n palomas se distribuyen en m palomares, y si n es mayor que m, entonces al menos habrá un palomar con más de una paloma.

Basándose en ideas tan sencillas como estas, los matemáticos Franck Ramsey y Paul Erdös establecieron que el desorden completo no existe. Es decir que en cualquier estructura suficientemente grande siempre se puede encontrar una subestructura ordenada.

Paul Erdös nació en Budapest en 1913. Su vida fue documentada en la película N es un número: El retrato de Paul Erdös, hecha mientras él todavía estaba vivo, y el libroEl hombre que solo amaba a los números. Murió de un ataque al corazón el 20 de septiembre de 1996, a la edad de 83 años, en plena actividad.

Publicó más de 1.500 artículos, y tuvo en total 509 colaboradores directos.

Actualmente las conjeturas que formuló a lo largo de su vida son todavía son motivo de investigación matemática.

De sus primeras 64 publicaciones 61 eran sobre la Teoría de los Números.

Debido a sus numerosos aportes, colaboradores y amigos inventaron el número de Erdös: Él tiene asignado el número 0, todos aquellos que colaboraron en algún artículo con él tienen el 1, alguien que haya colaborado con alguno de sus colaboradores tiene el 2, y así sucesivamente…. Sencillas estimaciones comprueban que el 90% de los matemáticos activos tienen un número de Erdös menor que 8.

Una lista de importantes matemáticos y científicos con un número de Erdös bajo puede verse aquí.

Franck Ramsey nació en Cambridge en 1903. Desarrolló una cantidad de trabajos sobre lógica, matemáticas, economía y la filosofía de dichas disciplinas. Desafortunadamente, tras una operación murió a la edad de 26 años.

Entre los primeros resultados de su teoría están el teorema de la amistad y el problema del final feliz.

El teorema de la amistad asegura que en cualquier reunión donde haya al menos seis personas, habrá tres de ellas que ya se conocen o tres que nunca se habían visto. En términos de la teoría de grafos: Si un grafo tiene al menos seis vértices de forma que entre dos vértices cualesquiera hay una arista y si las coloreamos digamos de rojo y azul, entonces habrá un triángulo formado por aristas del mismo color.

La demostración es sencilla:

Elíjase uno de los vértices P. Hay cinco aristas incidentes a P, cada una coloreada con el color rojo o azul.

Según el principio del palomar, al menos tres aristas deben ser del mismo color, porque si hay menos de tres de un solo color, por ejemplo roja, entonces hay al menos tres que son de color azul.

Sean A, B, C, los otros vértices extremos de estas tres aristas, todas del mismo color, por ejemplo azul. Si alguna de las aristas AB, BC, CA es azul, entonces esta arista junto con las dos aristas incidentes a P forman los lados de un triángulo azul. Si ninguna de las aristas AB, BC, CA es azul, entonces las tres aristas son de color rojo y se tiene un triángulo rojo de vértices ABC.

El problema del final feliz es uno de los resultados que dieron origen a la teoría de Ramsey. El planteo del problema es el siguiente: Cual es el menor número de puntos en el plano tal que no haya tres alineados, para que siempre exista un subconjunto de 4 puntos que sean los vértices de un cuadrilátero convexo (es decir, que todos sus ángulos interiores midan menos de 180º).

Paul Erdós, Esther Klein y George Szekeres demostraron de una forma breve y sencilla que basta con 5 puntos.

Lo probaron analizando cada caso:

Caso 1: Si los cinco puntos forman los vértices de un pentágono convexo, pueden ser elegidos 4 puntos cualquiera.

Caso 2: Si una configuración de puntos forma un triángulo con dos puntos interiores; los dos puntos interiores y dos vértices del triángulo pueden ser elegidos.

Caso 3: Si una configuración de puntos forma un cuadrilátero con un punto interior,este cuadrílatero es convexo.

Esther Klein y George Szekeres se hicieron novios mientras trabajaban en este problema, y luego se casaron. Por eso Paul Erdös lo llamó el problema con final feliz.

El teorema de Ramsey establece que en cualquier esquema de color aplicado a un grafo completo suficientemente grande, se hallarán subgrafos completos monocromáticos.

Según la teoría de Ramsey, del total de estrellas del cielo nocturno, siempre podemos seleccionar un subconjunto de ellas para dibujar diferentes objetos como: un triángulo, un cuadrilátero, un paraguas o un pulpo.

En general, la teoría de Ramsey busca regularidad en medio del desorden: condiciones generales para la existencia de subestructuras con propiedades regulares.

4 marzo, 2019 Combinatoria Grafos Teoremas 5

 

5 comentarios

  1. […] Hilbert nació en 1862 en Königsberg (la ciudad de los famosos puentes). Fue uno de los matemáticos que más influyó en el desarrollo actual de la matemática, y uno de […]

  2. […] Los problemas planteados por Erdős, son fáciles de entender, pero habitualmente son muy difíciles de resolver, suelen tener una gran profundidad matemática e incluso han dado origen en algunos casos a importantes teorías matemáticas, como es el caso de la teoría de Ramsey ( una teoría matemática que busca encontrar conjuntos ordenados en medio del desorden, sobre la que ya he escrito aquí). […]

  3. […] he mencionado en un artículo anterior cómo Leonhard Paul Euler creó la teoría de grafos: “El trabajo de Leonhard Euler sobre el […]

  4. […] matemático prusiano Christian Goldbach nació en Königsberg, Prusia (la misma del famoso problema de los puentes),hoy Kaliningrado, Rusia. En sus viajes por Europa conoció a matemáticos como  Gottfried […]

  5. […] conjeturó que todos estos números eran primos, pero en 1732 Leonhard Euler (el mismo de los puentes de Königsberg ) encontró que F5 es divisible por […]

Deja un comentario

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.