Processing math: 100%

9 votos

Mathematicly Untangeling Desenredar.

Tengo una nueva adicción, yo juego Desenredar a menudo, y me pregunto ¿qué es la matemática detrás de él.

algunos juegos gratis: (pero se advirtió altamente adictivo)

Javascript: http://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/untangle.html

Android: https://play.google.com/store/apps/details?id=softkos.untanglemeextreme&hl=en

las reglas son simples:

Se le dará un número de puntos, algunos de los cuales tienen líneas dibujadas entre ellos. Puede mover los puntos sobre arbitrariamente; su objetivo es la posición de los puntos, de modo que ninguna línea se cruza con otra.

en algunas versiones, la dificultad es enriquecido por hacer de 1 a 3 puntos inamovibles.

Este rompecabezas simple da lugar a todo tipo topológico de preguntas:

  • hay un algorhitms para resolverlos?

Algunos de los juegos en el android descargar yo era incapaz de resolver, y que hace que me pregunte, probablemente no son irresolubles desentrañar puzzles (de modo que en cualquier situación de algunas líneas de la cruz)

  • cómo se puede reconocer?
  • ¿cuáles son los mínimos casos de rompecabezas irresoluble?
  • existen fundamentalmente diferentes casos de rompecabezas irresoluble?

¿Hay algún matemático informes escritos acerca de estos rompecabezas?

ahora a ver de nuevo tratando de resolver uno.....

5voto

fgp Puntos 15322

Hay rompecabezas irresoluble. Desenredar le da un gráfico, es decir, un conjunto de vértices (puntos) con aristas (líneas) entre algunos de ellos. Se le pedirá que encontrar una incrustación de la gráfica en el plano bidimensional tal que no hay dos bordes se cruzan entre sí. Un gráfico en el que es posible que se llama un plano gráfico.

No todos los gráficos son planas - el más pequeño no planas gráfica es la gráfica que contiene 5 vértices y aristas entre todos los pares de vértices. I. e., se inicia con una estrella de cinco puntas, y luego dibujar líneas entre todos los pares de las esquinas.

Hay varias maneras para decidir si un grafo es planar - check out http://en.wikipedia.org/wiki/Planar_graph y http://en.wikipedia.org/wiki/Planarity_testing

Si usted lee los artículos detenidamente, te darás cuenta de que en realidad no dicen que los bordes deben ser líneas - que permite a los bordes de ser cualquier tipo de curva. Que, sin embargo, no realmente hacer una diferencia. Si usted encuentra alguna incrustación de un gráfico en el plano bidimensional donde los bordes - si representados como arbitraria curvas - no se cortan el uno al otro, siempre se puede mover los puntos tales que estas curvas se convierten en líneas rectas.

0voto

Phicar Puntos 937

La teoría de la fuerza dirigida dibujo de algoritmos(continuación de la teoría de la Tutte del baricentro método ) es la forma de solucionarlo si es plana...si es que no te deje en la respuesta anterior.

Por cierto genial el juego :)

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X