Teoría de gráficas

Mi nombre es Alberto Rosales, actualmente estudio la Lic. en física en la Facultad de Ciencias de la UNAM, decidí hacerlo porque la forma en la cual las ciencias nos permiten descubrir el mundo que nos rodea es fascinante. Creo que las ideas son la esencia de estas disciplinas, la validez de una demostración matemática es perenne y los conocimientos acumulados son capas que crecen con cada teoría, es por ello que esta ocasión quiero hablar un poco sobre Teoría de Gráficas, algo que surgió como una idea sencilla y que hoy en día es un motor de las matemáticas.


EL NACIMIENTO

La Teoría de Gráficas es una rama joven de las matemáticas, todo comenzó con un problema que solían plantear los habitantes de Königsberg (actualmente Kaliningrado, Rusia) a propios y extraños. La ciudad estaba dividida en 4 porciones de tierra y era conectada por 7 puentes que cruzaban el río Pregel.

Los puentes de Könisberg.

Imagen 1. La ciudad de Konigsberg, los puentes en color verde y su gráfica representativa.

La pregunta es: ¿Se pueden recorrer los 7 puentes sin repetir alguno y regresar al mismo punto?

La respuesta (demostrada formalmente) fue dada por Leohnard Euler en 1736, para hallarla Euler planteó el problema con puntos y aristas, es decir, un grafo. Cada porción de tierra fue representada por un vértice y los puentes por aristas.

El resultado al problema es sencillo, la idea consiste en que al pasar por un vértice tendremos que utilizar una arista para entrar y una para salir (es decir, un numero par de aristas), de otra forma al llegar al vértice no podremos salir de él sin repetir alguna. Entonces no es posible cruzar los puentes de Königsberg como se desea, esto porque en varias porciones de tierra firme los puentes inciden un número impar de veces.

DEFINICIONES Y APLICACIONES

Entonces una gráfica (o grafo) es un diagrama que consiste en un conjunto de puntos relacionados entre sí con aristas. Puede ser que existan multiraristas (varias aristas entre 2 vértices), que sean dirigidas (que se especifique una sola dirección), que las gráficas sean árboles (cada vértice tenga a lo más 2 aristas incidentes) o ciclos (como polígonos regulares). Las formas de las gráficas pueden ser muy variadas.

Los vértices conectados directamente por una arista se llaman adyacentes. Sí existe al menos un camino para conectar cualquier par de puntos, entonces la gráfica es conexa. Los caminos que recorren todas las aristas sin repetir alguna de ellas se denominan eulerianos, mientras que los caminos que recorren todos los vértices sólo en una ocasión (sin importar recorrer todas las aristas) se denominan Hamiltonianos.

El potencial de la teoría de gráficas reside en poder modelar alguna situación de la vida real de forma simple, se abstraen las características del sistema y se estudia. En un principio se pensaba en la teoría de gráficas como una diversión matemática, sin embargo pronto se descubrió su verdadero potencial, incluso fue parte clave para el nacimiento de otra rama matemática, la topología.

Actualmente la teoría de gráficas se aplica en electrónica al estudio de circuitos y mallas, también ayuda al transporte en el diseño de rutas, a los analistas a vincular información y todas las redes sociales son grafos, donde cada persona es un vértice y la relación de “amistad” es una arista.

EL PROBLEMA DE LOS 4 COLORES
Un concepto importante en gráficas es la coloración, se dice que una gráfica está bien coloreada sí a cada vértice le puedes asignar un color distinto del de sus vecinos (vértices adyacentes), el problema es deducir ¿Cuál es el mínimo de colores que se necesitan?

Resulta que este problema es análogo a preguntarse ¿Con cuantos colores puedo pintar un mapa?, ya que los territorios vecinos no pueden tener colores iguales. El problema históricamente tiene su origen en Inglaterra en 1852, pero su resolución tardó mas de 100 años y la prueba no es completamente satisfactoria para algunos matemáticos. Esto porque se debe dar una solución general y las gráficas o mapas pueden tener distintas configuraciones, de hecho para 1879 Alfred Bray Kempe (un matemático inglés) pensó tener la demostración definitiva, pero años después se encontró un error que dejaba la demostración en 5 colores y no 4.

Fue hasta 1976 que se redujeron las posibles configuraciones a 1,482 y con base en los cálculos realizados por una supercomputadora (50 días de cálculo) se determinó que todas ellas cumplen el teorema de los 4 colores. Este tipo de demostración fue la primera en su tipo y trajo controversia, ya que fue a base de “trabajo bruto” y comprobando todos los casos posibles haciendo cuentas. Hoy en día todavía se hacen avances intentando dar mayor validez a la demostración y buscando una forma de hacerlo sin la necesidad de ordenadores.

LOS 6 GRADOS DE SEPARACIÓN
¿Alguna vez has escuchado que el mundo es muy pequeño?, ¿Que tan “alejado” estas de cualquier persona en el mundo?, estas preguntas desde hace algunas décadas han intrigado a sociólogos y psicólogos.

Six degrees of separation

Imagen 2. Seis grados de separación.

En los años 60’s el psicólogo Stanley Milgram se dedicó a probar la teoría de los seis grados de separación, la cual establece que en el mundo dos personas están conectadas por una cadena de conocidos con sólo seis enlaces, sus resultados con habitantes en Estados Unidos indicaban que entre cualquier par de personas había menos de cinco eslabones intermedios en la cadena.

La realidad es que se ha especulado mucho sobre el tema y no existe un resultado concluyente al respecto, pero recientemente se analizó la estructura de la red social más grande hasta la fecha, Facebook, y resulta que más del 99% de los usuarios cumplen la regla de los seis grados (algo verdaderamente extraño).

Imágenes.
[1] Los puentes de Konigsberg.jpg en (http://gaussianos.com/los-puentes-de-konigsberg-el-comienzo-de-la-teoria-de-grafos), fecha de consulta 13/06/12.

Fuentes de Información.
No, no es posible atravesar los siete puentes de Königsberg pasando exactamente una vez por cada uno de ellos, Santos Francisco, Fecha de consulta:13/06/12.

El teorema de los 4 colores, fecha de consulta: 13/06/12.

La caprichosa forma de globión, Illanes Mejía Alejandro, Fondo de Cultura Económica, Colección la ciencia para todos, Primera Edición, México D.F., 1999.

Seis grados de separación, fecha de consulta: 13/06/12

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s