juegos con grafos

GRAFOS JUEGOS CON GRAFOS

MATEMÁTICAS DISCRETAS

JULIO CESAR NUÑEZ TEJERO INGENIERA EN COMPUTACIÓN

DES CIENCIAS DE LA INFORMACIÓN

25 DE MAYO DE 2015 -

UNIVERSIDAD AUTONOMA DEL CARMEN

1 Julio Cesar Nuñez Tejero Juegos Con Grafos

Matemáticas Discretas DES - Ciencias de la Información

Universidad Autónoma del Carmen

Ciudad del Carmen, Campeche

Campus I

Contenido RESUMEN ................................................................................... 2

INTRODUCCIÓN .......................................................................... 3

ANTECEDENTES ........................................................................... 4

GRAFO EULERIANO ..............................................................................4 Puentes de Königsberg ................................................................4 Grafo de Listing ...........................................................................6

GRAFO HAMILTONIANO .......................................................................6 Dodecaedro .................................................................................6

ARBOLES ...........................................................................................7 Laberintos ....................................................................................7

COLOREABILIDAD DE UN GRAFO .............................................................9

JUEGOS ...................................................................................... 10

El problema de los 3 suministros ...............................................10 Pastor, col, oveja y lobo .............................................................11 Dodecaedro ...............................................................................13 Torres de Hanói .........................................................................14 El Domino (Semi) Perfecto ............................................................17 Problema de Collatz ...................................................................19

RESULTADOS .............................................................................. 21

REFERNCIAS ............................................................................................................... 22





Campus I

Resumen

En el presente trabajo se tiene la intención demostrar que “La teoría de

grafos” es una de las herramientas que aparece en el análisis matemático

en los juegos, con una pequeña introducción acerca de los grafos, sus

componentes y sus conceptos, explicaremos como es que son tan útiles en

la resolución de problemas del mundo real.

El propósito de este es modelar a través de la teoría de grafos la matización

de situaciones de forma eficiente, intuitiva y sencilla de algunos juegos,

revisar las estrategias seguidas para ganar y así como los fundamentos para

la realización de estos.

Dibujar un grafo para resolver un problema es bastante común, y no se

precisa de conocimientos matemáticos. Un grafo es un dibujo, y consta de

vértices y de aristas que unen algunos de estos vértices

Describiremos un poco de la historia acerca de cómo surgieron los

planteamientos de los problemas propuestos y denotar como los ahora

llamados grafos fueron de gran ayuda para la resolución de estos.

Analizaremos varios juegos que tienen bases en la Teoría de Grafos y de

acuerdo a su metodología y su nivel de complejidad iremos desglosando los

modelos de resolución en la cual la teoría de grafos es esencial para esta.

Lo que finalmente se propone es analizar el modelo matemático que partir

de grafos para diversos juegos y ver las características de la estrategia

seguida para vencer, tratando de generalizarla para otros juego que puedan

modelar de la misma manera.

Así como denotar algunas pequeñas observaciones que surgieron al estar

desarrollando estos juegos.





Campus I

Introducción

A continuación se presentara un sencillo material introductorio a la teoría de grafos,

que posee diversas aplicaciones en la vida cotidiana, en este caso unos juegos que

a simple vista parecen sencillos, pero al abordarlos descubriremos que nos tomara

un poco más de trabajo la resolución de estos, sabiendo la base en la que se

plantean estos podemos formular una estrategia para vencer a través de la teoría

de grafos, tendremos que aprender un poco sobre como surgieron a través de

diversas situaciones y como fue surgiendo su metodología así como sus conceptos

Consideremos un conjunto de puntos sobre el plano, algunos de ellos unido por un

segmento. A la figura así obtenida se le llama grafo. A cada uno de los puntos lo

llamaremos vértice, y a los segmentos que los unen, aristas.

Cada arista queda definida por los dos vértices de sus

extremos. Se dice que cada uno de estos dos vértices es

adyacente a la arista que los une, o que la arista es adyacente

a los vértices que la definen.

En un grafo las longitudes de los segmentos no determinan que

dos grafos sean diferentes: lo importante es que algunos

vértices está unidos y otros no.

La teoría de grafos, es una parte de las Matemáticas que

comenzaron en clave de juego y se han convertido en un

instrumento fundamental de la Matemática Aplicada. Los

problemas de transporte, la combinatoria poliédrica, los

problemas de secuenciación de actividades usan de la Teoría de Grafos, para

resolver muchos de los problemas de estas áreas.

A partir de Euler el modelado mediante grafos fue desarrollando metodologías hasta

convertirse en la actualidad, en una herramienta de trabajo para ciencias tan

diferentes como la Física, la Química, la Sicosociología, la Economía, la Lingüística,

etc. La teoría de grafos está íntimamente relacionada con varias ramas de la

Matemáticas como por ejemplo la Teoría de Conjuntos, el Análisis Numérico,

Probabilidad, Topología, etc. y es la base conceptual en el tratamiento de problemas

combinatorios.

La eficacia de los grafos se basa en su gran poderío de abstracción y la muy clara

representación de cualquier relación lo que facilita enormemente tanto la fase de

modelado como de resolución del problema. Gracias a la Teoría de Grafos se han

desarrollado una gran variedad de algoritmos y métodos de resolución eficaces que

nos permiten tomar una mejor decisión.





Campus I

Antecedentes

El nacimiento del concepto GRAFOS se puede situar, por el año 1730, cuando Euler

(matemático) se convirtió en el padre de la Teoría de Grafos al modelar un famoso

problema no resuelto, llamado el "problema de los

puentes de Königsberg".

En 1847, Gustavo Kirchhoff se interesa, en sus trabajos

sobre redes eléctricas, por la cantidad de corriente que

circula por las diferentes ramas de un circuito eléctrico

dando lugar a las leyes que llevan su nombre. Para ello,

desarrolla la noción de árbol, tipo especial de grafo sin

circuitos

Diez años más tarde, en 1857, los grafos se aplican

también a la química. Cayley, nacido en Richmond en el año 1821, estudia las

diferentes estructuras posibles de una molécula con n átomos de carbono y 2n+2

átomos de hidrógeno. Las substancias con igual número de átomos de cada clase

en la molécula y con pro- piedades distintas, se

conocen en química como isomería. Ejemplo de dos

isómeros son el propano normal y el isopropano,

ambos de fórmula química C5H12. Cayley

representaba también esas fórmulas

con la ayuda de grafos tipo árbol.

Grafo euleriano

Puentes de Königsberg

El problema de los siete puentes de Königsberg, enunciado anteriormente, se

formularía ahora, de la manera siguiente: ¿cómo sería posible, partiendo de uno

cualquiera de los cuatro vértices, colorear la totalidad de los lados del grafo, sin

pasar dos veces por el mismo lado, sin levantar el lápiz del grafo, y regresando al

mismo vértice de partida? Lo que parece un juego, si

fuéramos capaces de construir tal paseo, técnicamente

se dice que se trata de un circuito euleriano y, como

consecuencia, cuando un grafo contiene tal circuito, se

dice que se trata de un grafo euleriano. Dicho de otra

manera, y de una forma más general, ¿sería posible

saber, de una manera sencilla, si en un grafo dado, sea

el de los siete puentes o cualquier otro, existe un

circuito euleriano?

http://photos1.blogger.com/blogger/1725/3679/1600/metano1.gif

http://photos1.blogger.com/blogger/1725/3679/1600/3.4.1.gif





Campus I

Problema genérico: dado un grafo (con múltiples líneas entre pares de puntos)

encontrar un camino que recorra el grafo asando por cada arista exactamente una

vez.

Solución: El grafo debe ser conexo, y en cada punto deben incidir un número par

de líneas. Esta condición es suficiente para definir lo que se llama un ciclo

euleriano.

La cuestión fue resuelta por el mismo Euler y, en la teoría de grafos actual, esa

solución está contenida en un teorema que lleva su nombre. Podríamos enunciarlo

así: para que un grafo contenga un circuito euleriano, es necesario que en

cada uno de sus vértices incida un número par de lados. Solo así es posible

llegar a un vértice cualquiera y poder salir de él sin volver a pasar por el mismo lado

por el que se accedió.

Aplicando el teorema al caso de los siete puentes

descubrimos inmediatamente que, el problema

del paseo no tiene solución: vemos que el total de

lados incidentes en cada vértice, o grado de sus

vértices, es siempre un número impar. Para poder

efectuar el paseo propuesto, sería necesario

agregar algunos puentes a la topografía

existente, por ejemplo, un nuevo puente ac y el bd, Así, todos los vértices serían de

grado par.

Al genio de Euler se debe, pues, el haber descubierto, apoyándose en la teoría de

grafos por él formaliza- da, que el juego del paseo, tal como estaba planteado, y al

que tanto tiempo dedicaron las gentes de aquel entonces, no tenía solución.

El grafo contiene solo dos vértices impares. Aunque parezca complicado, ese grafo

es recorrible comenzando en uno de los vértices de grado impar y finalizando en el

otro, a y z.





Campus I

Grafo de Listing

El grafo anterior procede del tratado titulado Vorstudien zur Topologie, de Johann

Benedict Listing. Esta obra fue comunicada al matemático y astrónomo francés

Édouard Lucas, 1842-1891, por el también matemático Georg Cantor, profesor en

aquel entonces en la Universidad de Heidelberg. Lucas era un apasionado por las

curiosidades matemáticas y a él se debe el tratado Récréations Mathématiques

publicado después de su muerte en cuatro volúmenes, entre los años 1892 y 1894.

Se le considera el inventor del conocido juego de las Torres de Hanoi o torres de

Brama.

Grafo hamiltoniano

Dodecaedro

En 1857, es decir, 122 años después de los trabajos de Euler, el matemático William

Rowan Hamilton, nacido en Dublín en 1805, inventa y presenta su Juego Ico- siano,

The Icosian Game, y posteriormente una variante del anterior con los nombres de

Dodecaedro del viajero, Un viaje alrededor del mundo, en los que de nuevo

aparecen los grafos.

Este juego estaba compuesto esencialmente por un dodecaedro regular, de

madera, provisto de un mango o asidero fijado en el centro de una de las caras del

dodecaedro. En los vértices del poliedro se habían colocado clavos de cabeza

ancha, bien de marfil o de metal, mientras que las treinta aristas del dodecaedro

estaban marcadas por trazos negros representando las rutas por las que el viajero

podía pasar para ir de una población a otra. Para realizar el paseo y recordar las

diversas poblaciones atravesadas, se tomaba un bramante que se fijaba en el punto

de partida y se iba enlazando en cada población, clavo, del recorrido.

El objetivo del juego es que un viajero visite los veinte vértices de ese poliedro

regular, uno tras otro, una vez y solo una, y de tal forma que el vértice origen sea

también el vértice destino.





Campus I

Arboles En los orígenes de la teoría de grafos, parte de las matemáticas que se ocupa de

objetos finitos o, como decimos hoy día, de objetos discretos, aparece una figura

significativa denominada árbol.

Laberintos

Un árbol es un grafo conexo y sin ciclos. Conexo significa que es posible conectar

cualquier pareja de vértices por medio de un camino y los laberintos constituyen un

ejemplo de grafo

En muchos casos, los laberintos se han concebido como lugares de diversión o

esparcimiento como es el caso de uno de los

más populares laberintos jardín: el de

Hampton Court, en Inglaterra, ideado y

realizado por el rey Guillermo III de Orange

en 1690. Otros laberintos del mismo uso son:

Villa Alteri en Roma y Alfarrás en Cataluña.

Asimilando los pasillos de un laberinto a los lados de un grafo y sus cruces o

encrucijadas a los vértices, la teoría de grafos permite salir de cualquier laberinto.

El interés por un laberinto puede ser diverso: acceder a un punto determinado del

mismo; visitar el laberinto completamente para encontrar un tesoro, un secreto y

luego salir regresando al origen. La cuestión es cómo explorar el laberinto de forma

sistemática o, lo que es lo mismo, cómo recorrer todas sus galerías sin dejar de

visitar un solo rincón.

Gaston Tarry, 1843-1913, fue un matemático francés nacido en Villefranche de

Panat e interesado por distintos temas de las matemáticas recreativas y, entre ellos,

por los laberintos. En 1895 enuncia un método sistemático de exploración de

laberintos de cualquier tipo. El método descansa en las dos reglas que siguen.





Campus I

Tendremos en cuenta que un pasillo comienza y acaba en los cruces; un cruce o

encrucijada es el punto del laberinto donde se encuentran dos o más pasillos.

1. Se recorre cada pasillo exactamente dos veces, una vez en cada sentido, colocando una marca en la entrada del pasillo y otra en la salida del mismo, de forma que al finalizar la exploración total del laberinto, cada pasillo habrá sido marca- do dos veces en cada extremidad.

2. En cada cruce o encrucijada se impone la condición de no volver a tomar el

pasillo por el que se ha descubierto o llegado a tal cruce (el pasillo por el cual

nos encontramos con ese cruce por vez primera) más que como último recurso.

En la misma época que Tarry, el ingeniero francés de telégrafos, Trémeaux, había

comunicado al matemático E. Lucas, ya citado más arriba, un método muy similar,

pero más preciso

Tres reglas por las que se rige este procedimiento.

1) Desde el punto de comienzo, se toma un camino cualquiera. Si se encuentra un punto sin salida, se retrocede por el pasillo ya recorrido. Si se llega a una encrucijada de pasillos, se toma uno cualquiera aún no explorado.

2) Si se llega a un cruce ya explorado, pero por una vía nueva, se retrocede por el pasillo al que se ha llegado al cruce hasta recorrerlo de nuevo completamente en sentido inverso.

3) Si se llega a una encrucijada ya explorada y por un pasillo ya recorrido en los dos sentidos, se elige, en primer lugar, un pasillo nuevo, y si esto no fuera posible, un pasillo explorado en un solo sentido.





Campus I

Coloreabilidad de un grafo

Junto con la caracterización de la existencia o no de ciclos y caminos eulerianos,

éste es uno de los problemas más conocidos en teoría de grafos.

Se dice que un grafo es n-coloreable si pueden pintarse sus vértices con n colores

diferentes de manera que dados 2 vértices del grafo unidos por una arista puedan

ser pintados de colores diferentes, y n sea el número más pequeño posible que

cumpla esa condición.

Uno de los resultados más celebrados (y controvertidos) de finales del siglo pasa-

do es el llamado Teorema de los cuatro colores. Appel y Hakel demuestran en 1976

que todo grafo plano4 es a lo sumo 4-coloreable.

Muchos de los grafos que surgen en nuestra actividad de coloreado no son planos,

por lo que éste último resultado no es parte del núcleo central de contenidos de la

actividad, aunque sí la definición de coloreabilidad de un grafo y cómo se puede

comprobar si un grafo es coloreable o no.

Numerosos investigadores han intentado crear diversos juegos de coloración.

Xuding Zhu creó en 1998 un par de juegos que consistían en obtener el número

cromático de un grafo y el número cromático acíclico.

Otro de los juegos consiste en intentar una coloración de los grafos,

teniendo cada vértice una lista de colores para realizar la coloración.

Siguiendo una estrategia de selección de vértices se procede a la

coloración de los mismos seleccionando un color de la lista de

colores que tie-ne asignada. La coloración será posible si se pueden

asignar colores a todos los vértices del grafo.

Entre los juegos de coloración también se incluyen algunos en los

que es necesaria la participación de dos personas para realizar el

juego. Es decir, que no consiste en un juego individual sino colectivo.

El juego consiste en realizar una coloración de un grafo con una serie de colores

disponibles entre dos jugadores. Cada jugador colorea un solo vértice en su turno,

pero ambos tienen metas diferentes. El jugador A intenta colorear el grafo con el

menor número de colores posibles, mientras que el jugador B tratará que no pueda

completarse la coloración llegando a un

vértice que no pueda ser coloreado con

los colores que hay disponibles.





Campus I

Juegos El problema de los 3 suministros

Este es uno de los problemas clásicos y más divertidos de teoría de grafos:

El objetivo es conectar cada una de las casas con los tres círculos –agua,

electricidad y gas — sin que ninguna de las líneas de conexión corte a otra.

Si representamos cada una de las casas y los posos mediante puntos (vértices) y

tomamos también las líneas de conexión (aristas) lo que obtenemos es el grafo

bipartito

Un grafo se dice que 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.

Solución

Kuratowski demuestra que este grafo K(3,3) no es plano. De hecho demuestra más,

que un grafo es plano si y sólo si no contiene a K(3,3) ni al grafo completo K(5). Esto

resuelve el problema, en el sentido de que no tiene solución sobre el plano,

En cambio, sí tiene solución si nos encontramos en un toro o en una cinta de Möbius.





Campus I

Pastor, col, oveja y lobo

Un pastor, con una col, una oveja y un lobo se encuentra a la orilla de un río que

quiere atravesar. Hay en su orilla una barca en la que cabe él y una sola de sus

pertenencias al tiempo. ¿Cómo se las ingeniará para pasarlas todas? Si deja solas

a un lado oveja y col, ésta será liquidada rápidamente por la oveja. Si deja oveja y

lobo solos a un lado, el lobo se zampará a la oveja. En cambio al lobo no le atrae

nada la col y bien se puede quedar solo con ella.

Apuntamos las posibles situaciones de las pertenencias del pastor en la orilla inicial

I sin que le desaparezca nada. Así

Solución

Señalamos con una flecha los posibles pasos de una situación a otra según la regla

del juego, es decir que en el barco sólo pueden cruzar el pastor y una sola de sus

pertenencias.

El primer paso el llevar la cabra a través del río, ya que de otro modo la cabra o la

col serían devoradas. Cuando el granjero vuelve a la orilla original, puede elegir

entre llevar el lobo o la col al otro lado. Si lleva el lobo, deben volver luego para

llevar la col, entones el lobo se comería a la cabra. Si lleva la col al otro lado,

necesitará volver para coger al lobo, entonces la col sería comida. Aquí se

encuentra el dilema, se resuelve llevando el lobo (o la col) en la barca y trayendo de

vuelta a la cabra. Ahora podemos llevar la col (o el lobo), dejando la cabra y,

finalmente, volver a buscar la cabra.





Campus I

La solución se resume de la siguiente manera:

1) Deja a la cabra al otro lado 2) Vuelve 3) Deja al lobo en el otro lado 4) Regresa con la cabra 5) Deja la col en el otro lado 6) Vuelve 7) Deja la cabra al otro lado

De modo, que hay siete pasos: cuatro hacia la derecha y tres hacia la izquierda.

Nuestro problema ahora consiste en hallar un camino de flechas desde POCL hasta

Nada. En el cuadro es evidente que hay solamente dos posibilidades

(1) POCL - LC - L - PLO - O - Nada (2) POCL - LC - C - PCO - O - Nada

Otra representación del mismo problema sería esta.





Campus I

Dodecaedro

El dodecaedro representado en (a), poliedro formado por doce caras de pentágonos

regulares, veinte vértices y treinta aristas, equivale topológicamente al grafo plano

(b) que posee los mismos vértices y lados que vértices y aristas tenía el dodecaedro

original.

Entonces, el juego se puede plantear técnicamente así: se trata de encontrar en el

dodecaedro un camino que, partiendo de un vértice cualquiera, vuelva a ese mismo

vértice después de pasar, a través de sus aristas, por todos los demás vértices una

sola vez. Tal recorrido se denominó más tarde en la teoría de grafos, ciclo y, en

honor de su descubridor, ciclo hamiltoniano.

Si el recorrido se hace sin cumplir el requisito de que inicio y final coincidan, es decir,

de que no haya ciclo cerrado, recibe el nombre de camino hamiltoniano. Y por

último, cuando un grafo posee un ciclo hamiltoniano, ese grafo se denomina grafo

hamiltoniano o de Hamilton.

El Juego Icosiano estaba formado por una tablilla de madera sobre la que se había

dibujado el dodecaedro plano. Los vértices estaban perforados con agujeros en los

que se colocaban peones numerados o testigos del recorrido. Por lo demás, el juego

no difiere del anterior.

Solución

Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano en

tiempo polinómico, siendo la búsqueda por fuerza bruta de todos los posibles

caminos u otros métodos excesivamente costosos. Existen, sin embargo, métodos

para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeños.





Campus I

Torres de Hanói

LAS REGLAS

Sólo se puede mover un disco cada vez.

Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.

Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.

Asumamos que tenemos una Torre de Hanoi con tres columnas (A, B, C) y tres

discos. Para propósitos del grafo, asumamos la siguiente nomenclatura. Los discos

aumentan de tamaño de izquierda a derecha, es decir, el disco menor está a la

izquierda. Además, la localización de disco se identificará con el nombre de la

columna. De esta forma, la notación ABC indica que el disco mayor está en la

columna A, el segundo disco en la columna B y el disco menor en la columna C.

AAA

AAB AAC

ACB

ACC ACA

ABC

ABA ABB

CBB

CBC CBA

CAC

CAA CAB

CCA

CCB CCC

BCC

BCA BCB

BCB

BBB BBC

BAB

BAC BAA





Campus I

Solución

Mover el disco menor a la columna intermediaria si hay un número par de discos. Si

hay un número impar de discos, mover el disco menor a la columna destino.

1) Hacer un movimiento legal que no sea reversar el paso anterior (sólo debe haber una posibilidad).

2) Mover el disco menor a la columna de la cual no provino en su movimiento anterior.

3) Repetir los pasos dos y tres hasta mover todos los discos.

De forma recursiva, este algoritmo se pude expresar como sigue.

1) Mover los n-1 discos superiores de la columna origen a la columna intermediaria usando la columna destino como intermediaria.

2) Mover el disco n a la columna destino 3) Mover los n-1 discos superiores de la columna intermediaria a la columna

destino usando la columna origen como intermediaria. De este modelo, es posible establecer que el paso más corto (óptimo) para pasar

los discos de A hasta C es AAA-AAC-ABC-ABB-CBB-CBA-CCA-CCC y que consta

de siete pasos solamente. Esto concuerda con el número mínimo de 2n - 1 (23 - 1

= 8 – 1 = 7) mencionado anteriormente.

Paso óptimo entre A y C

AAA

AAB AAC

ACB

ACC ACA

ABC

ABA ABB

CBB

CBC CBA

CAC

CAA CAB

CCA

CCB CCC

BCC

BCA BCB

BCB

BBB BBC

BAB

BAC BAA





Campus I

De este grafo es posible obtener otros pasos de interés, por ejemplo, el paso

Hamiltiniano, es decir, el paso que lleve el conjunto de discos a todas las columnas

y los regrese al principio. Hinz y Parisse (2002) probaron que todo grafo de Hanoi

es Hamiltoniano isomórfico y realizaron un análisis exhaustivo de su planaridad.

Hay un solo camino óptimo que conduce del estado inicial al final, así como un solo

camino de longitud máxima entre ambos estados. Este camino pasa por todos los

estados sin repetir ninguno.

AAA

AAB AAC

ACB

ACC ACA

AB C

ABA ABB

CBB

CBC CBA

CAC

CAA CAB

CCA

CCB CCC

BCC

BCA BCB

BCB

BBB BBC

BAB

BAC BAA





Campus I

El Domino (Semi) Perfecto

Se dispone del conjunto de todas las fichas de dominó, 28 fichas en total.

Reglas: Las fichas se colocan una tras otra siguiendo las reglas del dominó

tradicional. Se juega de forma lineal, sin bifurcaciones.

Un (doble) objetivo final:

Realizar una partida perfecta; esto es, colocar todas las fichas de las condiciones iniciales siguiendo las reglas del dominó de forma que la cifra con la que se comienza y la cifra con la que se termina coincidan.

Realizar una partida semiperfecta; esto es, colocar todas las fichas de las condiciones iniciales siguiendo las reglas del dominó de forma que la cifra con la que se comienza y la cifra con la que se termina no coincidan.

Solución

A partir de un conjunto de fichas de dominó se obtiene un grafo:

Por cada cifra distinta que aparezca en nuestro conjunto de fichas de

dominó, se dibuja un vértice del grafo y se numera con esa misma cifra.

Por cada ficha de dominó, se dibuja una arista que une los vértices

correspondientes a las cifras de la ficha elegida6.

Si tenemos un grafo, se obtiene un conjunto de fichas de dominó sin más

que numerar los vértices del grafo y tomar por cada arista del mismo la ficha

cuyas cifras son los números correspondientes a los vértices que une dicha

arista. Se muestra así que, esencialmente, es lo mismo tener grafos que

conjuntos de fichas de dominó.





Campus I

El reflejo de los conceptos de partida perfecta, y semiperfecta dentro del

ámbito de los grafos es también una traducción muy sencilla y natural





Campus I

Problema de Collatz

Hace más de sesenta años, Collatz inventa y da solución

a un problema que ha circulado desde siempre en los

medios matemáticos. Lo vamos a mostrar mediante un

grafo especial que llamamos organigrama, herramienta

empleada en informática, entre otras cosas, para

representar la lógica de los programas de ordenador y,

en general, para representar un algoritmo.

También conocida como 3n+1, conjetura de Ulam, el

problema de Siracusa, la secuencia hailstone, los

números hailstone y muchos más nombres. Este es el

problema.

¿Qué jugador puede llegar más rápido al número 1usando el problema 3n+1?

1. Tomar un entero natural cualquiera. Si es par, dividirlo por dos; si es impar, triplicarlo y añadirle uno y nuevamente dividirlo entre dos.

2. Tomar el número obtenido y repetir con él el proceso 1. Y así sucesivamente. A este algoritmo le agregué una condición extra para poder usarla como juego

competitivo entre varios jugadores.

3. Gana el jugador con el valor que llegue primero a 1 en el menor número de orbitas.

Solución

Tomamos como referencia 4 jugadores que seleccionaron números al azar: 336,

340, 256, y 36.

Se realizan los cálculos correspondientes con la

metodología mencionada anteriormente y se

obtiene la siguiente gráfica.

Una forma de visualizar las órbitas del problema

de 3n+1 es mediante un grafo denominado árbol

dirigido, cuyos nodos son enteros positivos,

cuyas aristas apuntan del número n al P(n) y

cuyas orbitas son el nivel del árbol.

Se aprecia que:

Jugador1 11 Orbitas

Jugador2 10 Orbitas

Jugador3 8 Orbitas

Jugador4 15 Orbitas

Jugador1 Jugador2 Jugador3 Jugador4

No/Pasadas 336 340 256 36

1 168 170 128 18

2 84 85 64 9

3 42 128 32 14

4 21 64 16 7

5 64 32 8 11

6 32 16 4 17

7 16 8 2 26

8 8 4 1 13

9 4 2 2 20

10 2 1 1 10

11 1 2 2 5

12 4 1 1 8

13 2 4 4 4

14 1 2 2 2

15 4 1 1 1

16 2 4 4 2





Campus I

Siendo el vencedor el jugador número 3 al tener menor números de ciclos en

completar todo el trayecto hasta el numero raíz.

Dentro de este Árbol se observa los resultado de varios números y aparece un dato

curioso: cualquiera que sea el entero de partida, se finaliza siempre con... 4, 2, 1.





Campus I

Resultados

Al analizar algunos juegos que relativamente parecen sencillos, podemos

observar que es posible seguir una estrategia que nos permite ganar si

jugamos bien.

Dentro del problema de los 3 suministros se observó que ese mismo grafo

no podía representarse en un plano sin que haya cortes entre las aristas en

puntos que no sean vértices Sin embargo, es posible hacerlo en una

superficie teórica (naturalmente un toro y un plano no son topológicamente

semejantes, ya que el toro tiene un agujero).

Dentó del problema de collatz o el denominado 3n+1 hay que tener cierto

cuidado al escoger el número, aunque es cierto q siempre llegaras la raíz

que es 1 te podría tomar m orbitas en alcanzar ese número, por ejemplo si

tomamos al número vencedor del jugador 256 y le añadimos 1 quedando

257, el número de orbitas que tendría dar seria de 117 haciendo q perdiera

por mucho el juego.

También se muestra el denominado modelo fractal de Sierpinski que representa la solución gráfica al problema de la Torre de Hanoi. En esa figura, los vértices de la estructura externa son las condiciones en

que los tres discos están en la misma columna. Además, que el triángulo

externo está formado por tres triángulos internos siguiendo el arreglo de

Sierpinski, y que estos, a su vez, están formados por triángulos más

pequeños.

Además, parte de estas actividades no son exclusivas del Área de

Matemáticas, por lo que la teoría de grafos posee múltiples aplicaciones en

muy diferentes contextos fuera delos contenidos propios de las

Matemáticas.





Campus I

Referncias

Morales, J.M., Muñoz & J.M.,Oller A.M.. (2009). EMPLEO DIDÁCTICO DE JUEGOS QUE SE

MATEMATIZAN MEDIANTE GRAFOS. UNA EXPERIENCIA. Junio 27,2015, de Contextos Educ. Sitio

web:

http://redined.mecd.gob.es/xmlui/bitstream/handle/11162/48158/01120123000052.pdf?sequen

ce=1

GarcÌa F.. (2004). La magia de los grafos. Junio 27,2015, de ACTA - Autores Científico-Técnicos y

Académicos Sitio web: http://www.acta.es/medios/articulos/matematicas/034029.pdf

MARTÍN NOVO, E., MÉNDEZ ALONSO, A.. (2004). La magia de los grafos. Junio 27,2015, de ACTA -

Autores Científico-Técnicos y Académicos Sitio web: http://revistasuma.es/IMG/pdf/46/031-

035.pdf

Guzmán de, M. (1984). JUEGOS MATEMÁTICOS EN LA ENSEÑANZA. Junio 27,2015, de Sociedad

Canaria de Profesores de Matemáticas Isaac Newton Sitio web:

http://www.mat.ucm.es/catedramdeguzman/old/06juegomat/juegosmatensenanza/juemat.htm

Morales M.. (2013). El problema de las tres casas y los tres suministros y la banda de Möbius. Junio

27,2015, de Gaussianos Sitio web: http://gaussianos.com/el-problema-de-las-tres-casas-y-los-tres-

suministros-y-la-banda-de-mobius/

http://www.dmae.upm.es/cursofractales/capitulo4/series/1_5.html

http://redined.mecd.gob.es/xmlui/bitstream/handle/11162/48158/01120123000052.pdf?sequence=1

http://redined.mecd.gob.es/xmlui/bitstream/handle/11162/48158/01120123000052.pdf?sequence=1

http://www.acta.es/medios/articulos/matematicas/034029.pdf

http://revistasuma.es/IMG/pdf/46/031-035.pdf

http://revistasuma.es/IMG/pdf/46/031-035.pdf

http://www.mat.ucm.es/catedramdeguzman/old/06juegomat/juegosmatensenanza/juemat.htm

http://gaussianos.com/el-problema-de-las-tres-casas-y-los-tres-suministros-y-la-banda-de-mobius/

http://gaussianos.com/el-problema-de-las-tres-casas-y-los-tres-suministros-y-la-banda-de-mobius/

http://www.dmae.upm.es/cursofractales/capitulo4/series/1_5.html

juegos con grafos

Documents