Extraña pregunta para comenzar la semana, ¿verdad? Vamos a intentar responderla a lo largo de este artículo.
Introducción
La Topología (no confundir con Topografía) es una rama de las matemáticas que podríamos decir que se ocupa de las deformaciones continuas de cuerpos. La cuestión es más o menos como sigue:
En Topología, si podemos convertir un cuerpo en otro mediante una deformación que no implique rotura entonces los dos cuerpos son topológicamente iguales.
Por ejemplo, en Topología una circunferencia y una elipse son iguales (se dice que son homeomorfos). Y, como todo el mundo sabe, un dónut y una taza de café también son iguales. Valga esta imagen (que encontré en este post del blog Topología I de un antiguo profesor mío) como ejemplo de ello:
Así que ya sabéis, si alguna vez coincidís desayunando con profesor de Topología y veis que está mordiendo la taza e intentando beber de un dónut no os extrañéis y echadle una mano porque no sabe distinguirlos.
Y hasta un conejito es igual a una esfera (gracias Acho):
Introducido ya el tema de la deformación de cuerpos vamos a plantearnos cómo podemos sumarlos. En principio sabemos sumar números, pero también conocemos cómo se suman matrices del mismo orden (sumando las entradas de cada una de ellas que están en la misma posición), polinomios (sumando los coeficientes de los monomios de mismo grado) o funciones en general. Pero ¿podemos sumar superficies? En Topoplogía sí. (Leer el resto del post)
Autor: ^DiAmOnD^ | Publicado el 21 de Diciembre de 2009 | 16 Comentarios Categorías: Topología
Dos horas buceando entre mis apuntes de la carrera (ese es el tiempo que he tardado en encontrar este teorema) bien valen un artículo. Sí, sé que en internet hay información, pero para mí mis apuntes son enormemente valiosos y no quería dejar escapar la oportunidad de consultarlo en ellos.
Introducción
Suena el despertador. Son las 6:30 de la mañana. Víctor se revuelve entre las sábanas, no quiere levantarse, el sueño le supera…pero no puede permitirlo. A las 8:30 tiene una entrevista de trabajo muy importante, puede que determinante para su futuro profesional.
- ¡¡Arriba chaval!!
Víctor se levanta de la cama de un salto y va directo al baño. Una ducha rápida complementada con un afeitado apurado le dejan nuevo. Desodorante, colonia y a arreglar esa cabeza. Ayer fue día (bueno, más bien noche) de salida informal con los amigos y el peinado fue más bien alocado, pero hoy toca seriedad y hay que bajarlo como sea. Secador por aquí, peine por allá. Y listo, su peinado hacia un lado presenta una completa armonía…¿completa?
- ¡¡Aghh!! Este maldito remolino…¿va a poder conmigo?…¡¡No!!
¿Podrá conseguir nuestro amigo Víctor que su pelo esté complemente perfecto? (Leer el resto del post)
¿Dónde está el punto , en el interior o en el exterior de la curva?
Posiblemente no os sea demasiado difícil acertar con un simple vistazo al dibujo. Pero imaginad ahora que la curva cubre la extensión de un campo de fútbol. ¿Sería la cosa tan sencilla? Creo que no. Entonces:
¿Qué procedimiento general utilizarías para determinar la situación del punto?
Seguro que muchos ya sabéis la respuesta. Para quien no la sepa responderemos a lo largo de este texto. (Leer el resto del post)
La presentación del juego es la que aparece en la imagen. El objetivo del mismo es conectar cada una de las casas de la fila superior con los tres círculos de la fila inferior si que ninguna de las líneas de conexión corte a otra. En este punto os dejo intentarlo para ver quién es el primero en conseguirlo.
Si representamos cada uno de los iconos (tanto las casas como los círculos) mediante puntos (vértices) y tomamos también las líneas de conexión (aristas) lo que obtenemos es un grafo.
Llamando a los vértices superiores y a los inferiores y representando como a la arista que une el vértice con el vértice obtenemos el grafo conocido como :
Seguís intentando conectar las tres casas con los tres círculos, ¿no? Por intentarlo que no quede, continuad con ello.
Partiendo de que dos aristas de un grafo sólo pueden contarse en un vértice (es decir, que si tenemos dibujados los vértices de antemano dos aristas no pueden cortarse en ningún punto nada más que en ellos) vamos a definir ahora lo que es un grafo plano:
Se dice que un grafo es plano si puede embeberse (algo así como “meterse”) en .
Es decir, un grafo es plano si podemos dibujarlo en un papel sin que ninguna de las aristas corte a otra en un punto que no sea un vértice.
Ahora, antes de dar la solución del juego, vamos a definir otro grafo, :
Es decir, es un grafo que tiene 5 vértices y que tiene como aristas todas las líneas que conectan cada vértice con todos los demás, como podéis ver en la imagen. A este grafo también se le denomina grafo completo de 5 vértices.
Y ahora vamos con la solución del asunto. El matemático polaco Kazimierz Kuratowski demostró lo siguiente (os dejo una versión débil del teorema):
Teorema de Kuratowski:
Un grafo es plano si no contiene como subgrafo a ni a .
Es decir, ni ni son grafos planos (ya que cada uno de ellos se contiene a sí mismo como subgrafo). O lo que es lo mismo, no pueden dibujarse en un papel con la condición de que ninguna arista corte a otra en un punto que no sea desde el principio un vértice.
La demostración de este teorema necesita de ciertos conocimientos previos sobre teoría de grafos relativamente avanzados y es algo complicada, por eso no la adjunto. Yo la conocí en 4º de carrera y la verdad es que me pareció bastante curioso el asunto ya que responde la típica pregunta que mucha gente se hace con las matemáticas: ¿pueden las matemáticas resolver problemas, digamos, tangibles? La respuesta es sí: en este caso las matemáticas nos dicen por qué no podemos realizar ese dibujo con esas condiciones.
En Gaussianos ya hemos visto, que yo recuerde, dos demostraciones de la infinitud de los números primos: la de Euclides y la que utiliza los números de Fermat. En esta entrada vamos a otra demostración de este hecho.
La prueba que vamos a ver es topológica y se debe al matemático israelí Hillel Furstenberg. A mí me parece muy interesante ya que en principio a uno no se le ocurre qué relación puede haber entre la infinitud de los números primos y la topología. Esta demostración, por tanto, servirá como otro ejemplo más de la conexión que existe entre ramas tan distintas de las matemáticas. (Leer el resto del post)
Comenzamos esta semana con una entrada dedicada a un problema clásico pero no por ello falto de interés: los puentes de Königsberg. Clásico porque es un problema muy conocido y estudiado; interesante porque está considerado como el comienzo de la topología, y, en particular, de la teoría de grafos.
El artículo consta de cuatro partes: descripción del problema y encuadre histórico del mismo, iniciación a la teoría de grafos, resolución del problema y aplicación a la resolución del problema del sobre y similares.
Los puentes de Königsberg
Königsberg (actualmente Kaliningrado, Rusia) era una ciudad de Prusia del siglo XVIII. El problema que nos ocupa tiene como protagonista a un río, el río Pregel, que cruzaba la ciudad, a dos islas que se encontraban en el mismo y a siete puentes que comunicaban las dos partes de la ciudad con las mismas. Concretamente la situación era como se describe en la imagen ( y son las dos partes de la ciudad y y las dos islas):
El problema consistía en comenzar en un punto, pasar por los siete puentes sin repetir ninguno y volver al punto de partida. Antes de seguir leyendo podéis intentarlo vosotros mismos, aunque os recomiendo que no le dediquéis demasiado tiempo.
Iniciación a la teoría de grafos
Un grafo es básicamente un conjunto no vacío (al menos contiene un elemento) de puntos llamados vértices y un conjunto de líneas llamadas aristas cada una de las cuales une dos vértices. Se llama lazo a una arista que une un vértice consigo mismo. Se dice que dos vértices son adyacentes si existe una arista que los une.
Se dice que un grafo es simple si para cualesquiera dos vértices existe a lo sumo una arista que los une. En otro caso se denomina multigrafo.
Si es un vértice de un grafo, se denomina grado de al número de aristas que inciden en el mismo (por convenio de considera que un lazo cuenta dos veces al determinar el grado de su vértice).
Se dice que un grafo es conexo si no puede expresarse como la unión de dos grafos de vértices disjuntos. Os dejo un ejemplo:
Un camino de longitud n es una sucesión de vértices, , y aristas, , de la siguiente forma: . Se dice que un camino es cerrado si , es decir, el vértice inicial y el final son el mismo. Se dice que es simple si todas sus aristas son distintas. Se llama trayectoria a un camino simple en el que todos sus vértices (salvo probablemente el inicial y el final) son distintos y se denomina circuito a una trayectoria cerrada con al menos una arista.
Se llama camino euleriano a un camino simple que contiene todas las aristas del grafo y se denomina circuito euleriano a un camino euleriano cerrado. Se dice que un grafo es euleriano si contiene un circuito euleriano.
Resolución del problema
Para empezar, ¿quién resolvió el problema? Pues como ya sabéis los que conocíais el problema y como habréis intuido los que no lo conocíais fue Leonhard Euler quien dio solución a este asunto. La idea genial de Euler fue representar la ciudad de Königsberg como un grafo en el que las cuatro partes de la misma eran los vértices y los siete puentes eran las aristas:
Por tanto el problema de los puentes de Königsberg pasa a ser un problema de teoría de grafos cuya solución publicó Euler en su artículo Solución de un problema relativo a la geometría de posición.
Según las definiciones que hemos visto en el punto anterior lo que queremos saber es si este grafo en euleriano, es decir, si contiene un circuito euleriano (es decir, un camino que contiene a todas las aristas del grafo sin que ninguna se repita y que comienza y termina en el mismo vértice). Vamos a demostrar el siguiente resultado:
Teorema:
Un grafo es euleriano y sin vértices aislados es conexo y el grado de todos sus vértices es par.
Demostración:
Si es euleriano entonces contiene un circuito euleriano y como no tiene vértices aislados entonces cualquier par de vértice y están conectados por la parte del circuito que va de a . Por tanto es conexo.
Por otra parte, como es euleriano contiene un circuito euleriano, es decir, un camino simple y cerrado que contiene a todas las aristas. Por tanto por cada arista que llegue a un vértice debe haber otra que salga del mismo y en consecuencia el grado de cada vértice es un número par.
Partimos de que es conexo y todos sus vértices tienen grado par.
Si el número de aristas de es 1 ó 2 el resultado es inmediato. Procedemos por inducción: supongamos que tiene aristas y que el resultado es cierto para los grafos que cumplan las condiciones y tengan menos de aristas.
Usando que todo grafo en el que todos sus vértices tienen grado mayor o igual que dos posee un circuito (¿por qué?) tenemos que el nuestro contiene un circuito, dikgamos . Si contiene todas las aristas de , entonces es un circuito euleriano y hemos terminado. En caso contrario sea el grafo obtenido al suprimir de las aristas de y suprimir después los vértices que han quedado aislados. Puede que el grafo haya quedado dividido en subgrafos no conectados entre sí; cada uno de ellos es una componente conexa de .
Por haber eliminado las aristas de un circuito todos los vértices de tiene grado par. Por la hipótesis de inducción, cada componente conexa de contiene un circuito euleriano.
Como en cada componente conexa debe haber al menos un vértice de podemos obtener un circuito euleriano en (que es lo que queríamos conseguir) del siguiente modo:
Partimos de un vértice cualquiera de (que recordemos que no era un circuito euleriano). Recorremos hasta llegar a un vértice de una componente conexa de . Recorremos esta componente conexa a través del circuito euleriano que hemos visto que debe contener y continuamos recorriendo hasta que nos encontremos con un vértice de otra de las componentes conexas, realizando entonces la misma operación. Repetimos el procedimiento hasta llegar al vértice de partida, obteniendo así un circuito euleriano.
c.q.d.
Observemos ahora el grafo que habíamos obtenido de la ciudad de Königsberg y calculemos el grado de todos sus vértices. Hay tres vértices con grado y un vértice con grado . Es decir, no hay ninguno con grado par. Por tanto, según el teorema anterior, este grafo no contiene un circuito euleriano, esto es, no podemos comenzar en un punto de la ciudad y recorrer cada uno de los puentes sólo una vez y terminar en el punto de partida.
El problema del sobre y similares
Supongo que muchos de vosotros os habréis encontrado con el típico problema de recorrer todos los segmentos de un dibujo sólo una vez sin levantar el lápiz del papel. En esos problemas los vértices inicial y final no tiene que ser el mismo, es decir, puedo comenzar en el vértice que quiera y terminar en ese mismo o en cualquier otro, pero debo pasar por todas las líneas una y sólo una vez sin levantarme del papel. El más típico es el sobre:
El siguiente resultado es un corolario del teorema anterior y nos ayudará a analizar todos estos problemas:
Corolario:
Un grafo contiene un camino euleriano es conexo y tiene como máximo dos vértices de grado impar.
La demostración os la dejo a vosotros para que la penséis.
Un camino euleriano es precisamente lo que buscamos cuando queremos resolver estos problemas. Por tanto lo único que tenemos que hacer es calcular el grado de cada vértice. Si tenemos más de dos vértices de grado impar el recorrido no será posible; por el contrario, si tiene sólo dos vértices o ningún vértice con grado impar entonces sí se podrá recorrer de esa forma (no puede haber sólo un vértice con grado impar ya que el número de vértices de grado impar es par, ¿por qué?). En el caso de nuestro sobre tenemos cuatro vértices con grado impar y por tanto no podremos recorrer todas las aristas sólo una vez sin levantar el lápiz del papel.
Por contra, si tenemos el sobre abierto:
sí podremos recorrerlo así ya que ahora sólo hay dos vértices con grado impar, los dos de abajo. De hecho se sabe que para recorrer todas las aristas sólo una vez sin levantar el lápiz del papel debemos comenzar en uno de los vértices de grado impar y terminar en el otro.
Con estos resultados ya no habrá problema de este tipo que se os resista.
Introducción
Como comentamos en la historia de la resolución de la cúbica, Tartaglia reveló, después de mucha insistencia, su método de resolución de los distintos tipos de ecuaciones cúbicas reducidas a Cardano. Pero no lo hizo de una manera convencional, sino que lo hizo en verso. Concretamente así:
Quando che’l cubo con le cose appresso
se agguaglia a [...]
