El problema del viajante

De

Travelling Salesman Problem, TSP

Un vendedor necesita repartir sus productos en cinco ciudades, Debe pasar una sola vez por cada ciudad empezando y terminando en el mismo punto. Debe buscar el circuito de peso mínimo, es decir, el más corto. 

¿Puedes calcular el recorrido más corto empezando desde la ciudad A y terminando en la ciudad A pasando una sola vez por cada ciudad? 







Este problema es representado mediante un grafo hamiltoniano, en el que las ciudades son los vértices y los caminos son las aristas. En los grafos de tipo hamiltoniano hay que pasar una sola vez por cada vértice, y no es obligatorio pasar por todas las aristas. Es un grafo ponderado, ya que cada arista tiene un valor que en este caso corresponde con el número de kilómetros que separan a las ciudades. También es un grafo no dirigido, puesto que los caminos pueden recorrerse en una dirección o en otra. Y es un grafo completo, porque cada par de vértices está unido por una arista (todos los vértices están unidos con todos).

Este problema fue formulado por primera vez por sir William Rowan Hamilton (1805-1865), que estaba muy interesado en dar solución a este tipo de grafos. Las aplicaciones de este problema son muchas. Hamilton desarrolló el juego Icosian. 

En el ejemplo anterior con cinco ciudades, la solución puede resultar sencilla, pero el problema se complica mucho si se aumenta el número de ciudades. 

¿Puedes decir cuántos recorridos distintos se pueden realizar en el grafo anterior, empezando por la ciudad A y terminando en la ciudad A? 
¿Y si aumentas a 6 ciudades? 
¿Puedes dar una fórmula general?


Comentarios

Publicar un comentario

Entradas populares de este blog

¿Qué significan las palabras cateto e hipotenusa? ¿De dónde provienen?

De
Imagen
Un triángulo rectángulo es aquel que tiene un ángulo recto, es decir un ángulo de 90º. Se llama Cateto a cada uno de los lados menores, los que conforman el ángulo recto. Hipotenusa es el lado mayor del triángulo, el que está en el lado opuesto al ángulo recto. En los triángulos rectángulos se cumple el Teorema de Pitágoras: el cuadrado de la hipotenusa es igual a la suma del cuadrado de los catetos. cateto1 2 + cateto2 2 = hipotenusa 2 Pero ¿por qué los lados de los triángulos rectángulos tienen esos nombres tan raros ? La palabra cateto viene del griego (κάθετος) y significa perpendicular .  Se define como: " C ada uno de los dos lados que forman el ángulo recto en un triángulo rectángulo. "  Efectivamente los dos catetos están colocados en posición perpendicular. La palabra hipotenusa también viene del griego, (ὑποτείνουσα), y significa tensar fuertemente una cuerda.  Es como si colocáramos una cuerda en los extremos de los catetos y l
Sigue leyendo

¿Por qué en un A4 no se cumple la Regla de Oro?

De
Imagen
Número de Oro: c/a=1,618 El número Phi (Φ, φ), también llamado Número de Oro, Proporción Áurea, Divina Proporción, es utilizado en arquitectura, escultura, pintura y diseño gráfico por ser la más bella proporción que puede aplicarse a una obra de arte. Ya los griegos y renacentistas lo utilizaban en sus creaciones, pero... ...¿por qué los formatos de papel estándar más utilizados (DIN A1, DIN A2...), no guardan esa misma proporción? Por ejemplo, un DIN A4 mide 210x297 mm. Si dividimos 297/210 nos da 1,414, nada que ver con el Número de Oro: 1,618.  Nuestros diseños sobre papel estándar no cumplen la Regla de Oro. ¿y por qué un A4 mide 210x297mm? Primero se buscó una medida para el A0, y se acordó que su superficie debía ser 1 m 2 .  También se decidió que la superficie del A1 debía ser la mitad de un A0, y mantener sus mismas proporciones. Esto se aprecia muy bien en la imagen. _____________________________ Para calcular los lados de cada uno de los tamaños hay
Sigue leyendo

Pitágoras, la mosca y la araña

De
Imagen
Resuelve este acertijo aplicando el Teorema de Pitágoras. En una habitación hay una mosca y una araña. La mosca está posada en una de las paredes, a un metro del suelo, y la araña está en la pared opuesta a un metro del techo. Las dos se hallan en el medio horizontal de la pared. En este dibujo encontrarás la posición exacta de la araña y de la mosca. La habitación mide 20m de largo, 10m de ancho y 10m de alto ¡qué alta!. ¿Cuál es el camino más corto que debe recorrer la araña para atrapar a la mosca? En principio parece que el camino más corto es:  bajar 9m, recorrer otros 20m por el suelo y subir 1m,  total 30m.  Hay otro camino más corto Vamos a dibujar la habitación, pero de otra forma, En dos dimensiones.  Ahora vamos a colocar a la mosca y a la araña. Y dibujamos una línea uniéndolas. Ese es el camino más corto. Si has plegado la habitación, verás que la araña debería avanzar en diagonal por las paredes y el suelo. Vamos a comprobar si
Sigue leyendo

Euler, el carrito de limpieza y la fórmula secreta

De
Imagen
E uler, el carrito de limpieza y la fórmula secreta  Cuento matemático Alicia Yaiza Toda la verdad sobre Euler y la Teoría de Grafos.  El problema de los Puentes de Konigsberg es conocido en el mundo entero. Pero la verdadera historia es esta: la Teoría de Grafos nació gracias a Úrsula, la señora de limpieza de la Academia de las Ciencias de San Petesburgo. Todo esto quedó olvidado durante muchos años, pero hoy se conoce toda la verdad. Leonhard Euler nació en Suiza en el año 1707. A los 20 años se fue a San Petesburgo para trabajar como profesor e investigador en la Academia de las Ciencias de Rusia. Leonhard pasaba mucho tiempo en la Academia. Le gustaba estar allí cuando todo el mundo ya se había ido. Se quedaba solo escribiendo interminables fórmulas de física o matemáticas en esas gigantescas pizarras de madera que suben y bajan.   A las seis de la tarde llegaba Úrsula, la persona encargada de la limpieza de la Academia. Úrsula tenía un carrito para transpo
Sigue leyendo

El garabato de Euler

De
Imagen
El garabato de Euler Cuento matemático Alicia Yaiza Un garabato con mucha "característica" Leonardo era un niño inteligente y soñador. Le gustaban mucho las matemáticas,  el cine  y los inventos. Le encantaba su nombre, pues era también el nombre de Leonardo Da Vinci, Leonardo de Pisa y de Leonhard Euler, sabios entre sabios. Aunque algunas personas le decían, - "¡Ah, Leonardo, como Leonardo Di Caprio!". Leonardo a veces se aburría en clase, cuando el profesor hablaba y hablaba repitiendo cien veces lo mismo. En esas ocasiones su mente conectaba con otra dimensión, su mirada parecía traspasar los cristales de la ventana y la electricidad viajaba a velocidad supersónica por sus neuronas. Imaginaba trucos, inventos, películas y hasta conversaciones con los Leonardos. En una ocasión, mientras el profesor explicaba por enésima vez la fórmula para calcular el área del triángulo,  Leonardo, sin darse cuenta, comenzó a dibujar un garabato en un papel,
Sigue leyendo