Juegos Con Grafos

GRAFOS
JUEGOS CON GRAFOS
MATEMTICAS DISCRETAS
JULIO CESAR NUEZ TEJERO

INGENIERA EN COMPUTACIN
DES CIENCIAS DE LA INFORMACIN
25 DE MAYO DE 2015
UNIVERSIDAD AUTONOMA DEL CARMEN
Universidad Autnoma del Carmen

Ciudad del Carmen, Campeche
Campus I
Matemticas Discretas
DES - Ciencias de la Informacin
Contenido
RESUMEN ................................................................................... 2
INTRODUCCIN .......................................................................... 3
ANTECEDENTES ........................................................................... 4
GRAFO EULERIANO ..............................................................................4
Puentes de Knigsberg ................................................................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 Hani .........................................................................14
El Domino (Semi) Perfecto............................................................17
Problema de Collatz...................................................................19
RESULTADOS..............................................................................21
REFERNCIAS ............................................................................................................... 22
1
Julio Cesar Nuez Tejero
Juegos Con Grafos

Campus I
Resumen
En el presente trabajo se tiene la intencin demostrar que La teora de
grafos es una de las herramientas que aparece en el anlisis matemtico
en los juegos, con una pequea introduccin acerca de los grafos, sus
componentes y sus conceptos, explicaremos como es que son tan tiles en
la resolucin de problemas del mundo real.
El propsito de este es modelar a travs de la teora de grafos la matizacin
de situaciones de forma eficiente, intuitiva y sencilla de algunos juegos,
revisar las estrategias seguidas para ganar y as como los fundamentos para
la realizacin de estos.
Dibujar un grafo para resolver un problema es bastante comn, y no se
precisa de conocimientos matemticos. Un grafo es un dibujo, y consta de
vrtices y de aristas que unen algunos de estos vrtices
Describiremos un poco de la historia acerca de cmo surgieron los
planteamientos de los problemas propuestos y denotar como los ahora
llamados grafos fueron de gran ayuda para la resolucin de estos.
Analizaremos varios juegos que tienen bases en la Teora de Grafos y de
acuerdo a su metodologa y su nivel de complejidad iremos desglosando los
modelos de resolucin en la cual la teora de grafos es esencial para esta.
Lo que finalmente se propone es analizar el modelo matemtico que partir
de grafos para diversos juegos y ver las caractersticas de la estrategia
seguida para vencer, tratando de generalizarla para otros juego que puedan
modelar de la misma manera.
As como denotar algunas pequeas observaciones que surgieron al estar
desarrollando estos juegos.
2
Juegos Con Grafos

Campus I
Introduccin
A continuacin se presentara un sencillo material introductorio a la teora 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 ms de trabajo la resolucin de estos, sabiendo la base en la que se
plantean estos podemos formular una estrategia para vencer a travs de la teora
de grafos, tendremos que aprender un poco sobre como surgieron a travs de
diversas situaciones y como fue surgiendo su metodologa 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 vrtice, y a los segmentos que los unen, aristas.
Cada arista queda definida por los dos vrtices de sus
extremos. Se dice que cada uno de estos dos vrtices es
adyacente a la arista que los une, o que la arista es adyacente
a los vrtices que la definen.
En un grafo las longitudes de los segmentos no determinan que
dos grafos sean diferentes: lo importante es que algunos
vrtices est unidos y otros no.
La teora de grafos, es una parte de las Matemticas que

comenzaron en clave de juego y se han convertido en un
instrumento fundamental de la Matemtica Aplicada. Los
problemas de transporte, la combinatoria polidrica, los
problemas de secuenciacin de actividades usan de la Teora de Grafos, para
resolver muchos de los problemas de estas reas.
A partir de Euler el modelado mediante grafos fue desarrollando metodologas hasta
convertirse en la actualidad, en una herramienta de trabajo para ciencias tan
diferentes como la Fsica, la Qumica, la Sicosociologa, la Economa, la Lingstica,
etc. La teora de grafos est ntimamente relacionada con varias ramas de la
Matemticas como por ejemplo la Teora de Conjuntos, el Anlisis Numrico,
Probabilidad, Topologa, etc. y es la base conceptual en el tratamiento de problemas
combinatorios.
La eficacia de los grafos se basa en su gran podero de abstraccin y la muy clara
representacin de cualquier relacin lo que facilita enormemente tanto la fase de
modelado como de resolucin del problema. Gracias a la Teora de Grafos se han
desarrollado una gran variedad de algoritmos y mtodos de resolucin eficaces que
nos permiten tomar una mejor decisin.
3
Juegos Con Grafos

Campus I
Antecedentes
El nacimiento del concepto GRAFOS se puede situar, por el ao 1730, cuando Euler
(matemtico) se convirti en el padre de la Teora de Grafos al modelar un famoso
problema no resuelto, llamado el "problema de los
puentes de Knigsberg".
En 1847, Gustavo Kirchhoff se interesa, en sus trabajos
sobre redes elctricas, por la cantidad de corriente que
circula por las diferentes ramas de un circuito elctrico
dando lugar a las leyes que llevan su nombre. Para ello,
desarrolla la nocin de rbol, tipo especial de grafo sin
circuitos
Diez aos ms tarde, en 1857, los grafos se aplican
tambin a la qumica. Cayley, nacido en Richmond en el ao 1821, estudia las
diferentes estructuras posibles de una molcula con n tomos de carbono y 2n+2
tomos de hidrgeno. Las substancias con igual nmero de tomos de cada clase
en la molcula y con pro- piedades distintas, se
conocen en qumica como isomera. Ejemplo de dos
ismeros son el propano normal y el isopropano,
ambos de frmula qumica C5H12. Cayley
representaba tambin esas frmulas
con la ayuda de grafos tipo rbol.
Grafo euleriano
Puentes de Knigsberg
El problema de los siete puentes de Knigsberg, enunciado anteriormente, se
formulara ahora, de la manera siguiente: cmo sera posible, partiendo de uno
cualquiera de los cuatro vrtices, colorear la totalidad de los lados del grafo, sin
pasar dos veces por el mismo lado, sin levantar el lpiz del grafo, y regresando al
mismo vrtice de partida? Lo que parece un juego, si
furamos capaces de construir tal paseo, tcnicamente
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 ms general, sera posible
saber, de una manera sencilla, si en un grafo dado, sea
el de los siete puentes o cualquier otro, existe un
circuito euleriano?
4
Juegos Con Grafos

Campus I
Problema genrico: dado un grafo (con mltiples lneas entre pares de puntos)
encontrar un camino que recorra el grafo asando por cada arista exactamente una
vez.
Solucin: El grafo debe ser conexo, y en cada punto deben incidir un nmero par
de lneas. Esta condicin es suficiente para definir lo que se llama un ciclo
euleriano.
La cuestin fue resuelta por el mismo Euler y, en la teora de grafos actual, esa
solucin est contenida en un teorema que lleva su nombre. Podramos enunciarlo
as: para que un grafo contenga un circuito euleriano, es necesario que en
cada uno de sus vrtices incida un nmero par de lados. Solo as es posible
llegar a un vrtice 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 solucin: vemos que el total de
lados incidentes en cada vrtice, o grado de sus
vrtices, es siempre un nmero impar. Para poder
efectuar el paseo propuesto, sera necesario
agregar algunos puentes a la topografa
existente, por ejemplo, un nuevo puente ac y el bd, As, todos los vrtices seran de
grado par.
Al genio de Euler se debe, pues, el haber descubierto, apoyndose en la teora 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 tena solucin.
El grafo contiene solo dos vrtices impares. Aunque parezca complicado, ese grafo
es recorrible comenzando en uno de los vrtices de grado impar y finalizando en el
otro, a y z.
5
Juegos Con Grafos

Campus I
Grafo de Listing
El grafo anterior procede del tratado titulado Vorstudien zur Topologie, de Johann
Benedict Listing. Esta obra fue comunicada al matemtico y astrnomo francs
douard Lucas, 1842-1891, por el tambin matemtico Georg Cantor, profesor en
aquel entonces en la Universidad de Heidelberg. Lucas era un apasionado por las
curiosidades matemticas y a l se debe el tratado Rcrations Mathmatiques
publicado despus de su muerte en cuatro volmenes, entre los aos 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 aos despus de los trabajos de Euler, el matemtico William
Rowan Hamilton, nacido en Dubln 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 vrtices del poliedro se haban 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
poda pasar para ir de una poblacin 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 poblacin, clavo, del recorrido.
El objetivo del juego es que un viajero visite los veinte vrtices de ese poliedro
regular, uno tras otro, una vez y solo una, y de tal forma que el vrtice origen sea
tambin el vrtice destino.
6
Juegos Con Grafos

Campus I
Arboles
En los orgenes de la teora de grafos, parte de las matemticas que se ocupa de
objetos finitos o, como decimos hoy da, 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 vrtices por medio de un camino y los laberintos constituyen un
ejemplo de grafo
En muchos casos, los laberintos se han concebido como lugares de diversin o
esparcimiento como es el caso de uno de los
ms populares laberintos jardn: 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 Alfarrs en Catalua.
Asimilando los pasillos de un laberinto a los lados de un grafo y sus cruces o

encrucijadas a los vrtices, la teora de grafos permite salir de cualquier laberinto.
El inters 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 cuestin es cmo explorar el laberinto de forma
sistemtica o, lo que es lo mismo, cmo recorrer todas sus galeras sin dejar de
visitar un solo rincn.
Gaston Tarry, 1843-1913, fue un matemtico francs nacido en Villefranche de

Panat e interesado por distintos temas de las matemticas recreativas y, entre ellos,
por los laberintos. En 1895 enuncia un mtodo sistemtico de exploracin de
laberintos de cualquier tipo. El mtodo descansa en las dos reglas que siguen.
7
Juegos Con Grafos

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 ms 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 exploracin total del laberinto, cada pasillo habr
sido marca- do dos veces en cada extremidad.
2. En cada cruce o encrucijada se impone la condicin 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) ms que como ltimo recurso.
En la misma poca que Tarry, el ingeniero francs de telgrafos, Trmeaux, haba

comunicado al matemtico E. Lucas, ya citado ms arriba, un mtodo muy similar,
pero ms 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 an no explorado.
2) Si se llega a un cruce ya explorado, pero por una va 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.
8
Juegos Con Grafos

Campus I
Coloreabilidad de un grafo
Junto con la caracterizacin de la existencia o no de ciclos y caminos eulerianos,
ste es uno de los problemas ms conocidos en teora de grafos.
Se dice que un grafo es n-coloreable si pueden pintarse sus vrtices con n colores
diferentes de manera que dados 2 vrtices del grafo unidos por una arista puedan
ser pintados de colores diferentes, y n sea el nmero ms pequeo posible que
cumpla esa condicin.
Uno de los resultados ms celebrados (y controvertidos) de finales del siglo pasado 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 ncleo central de contenidos de la
actividad, aunque s la definicin de coloreabilidad de un grafo y cmo se puede
comprobar si un grafo es coloreable o no.
Numerosos investigadores han intentado crear diversos juegos de coloracin.
Xuding Zhu cre en 1998 un par de juegos que consistan en obtener el nmero
cromtico de un grafo y el nmero cromtico acclico.
Otro de los juegos consiste en intentar una coloracin de los grafos,
teniendo cada vrtice una lista de colores para realizar la coloracin.
Siguiendo una estrategia de seleccin de vrtices se procede a la
coloracin de los mismos seleccionando un color de la lista de
colores que tie-ne asignada. La coloracin ser posible si se pueden
asignar colores a todos los vrtices del grafo.
Entre los juegos de coloracin tambin se incluyen algunos en los
que es necesaria la participacin de dos personas para realizar el
juego. Es decir, que no consiste en un juego individual sino colectivo.
El juego consiste en realizar una coloracin de un grafo con una serie de colores
disponibles entre dos jugadores. Cada jugador colorea un solo vrtice en su turno,
pero ambos tienen metas diferentes. El jugador A intenta colorear el grafo con el
menor nmero de colores posibles, mientras que el jugador B tratar que no pueda
completarse la coloracin llegando a un
vrtice que no pueda ser coloreado con
los colores que hay disponibles.
9
Juegos Con Grafos

Campus I
Juegos
El problema de los 3 suministros
Este es uno de los problemas clsicos y ms divertidos de teora de grafos:
El objetivo es conectar cada una de las casas con los tres crculos agua,
electricidad y gas sin que ninguna de las lneas de conexin corte a otra.
Si representamos cada una de las casas y los posos mediante puntos (vrtices) y
tomamos tambin las lneas de conexin (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 vrtice.
Solucin
Kuratowski demuestra que este grafo K(3,3) no es plano. De hecho demuestra ms,
que un grafo es plano si y slo si no contiene a K(3,3) ni al grafo completo K(5). Esto
resuelve el problema, en el sentido de que no tiene solucin sobre el plano,
En cambio, s tiene solucin si nos encontramos en un toro o en una cinta de Mbius.
10
Juegos Con Grafos

Campus I
Pastor, col, oveja y lobo

Un pastor, con una col, una oveja y un lobo se encuentra a la orilla de un ro que
quiere atravesar. Hay en su orilla una barca en la que cabe l y una sola de sus
pertenencias al tiempo. Cmo se las ingeniar para pasarlas todas? Si deja solas
a un lado oveja y col, sta ser liquidada rpidamente 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
Solucin
Sealamos con una flecha los posibles pasos de una situacin a otra segn la regla
del juego, es decir que en el barco slo pueden cruzar el pastor y una sola de sus
pertenencias.
El primer paso el llevar la cabra a travs del ro, ya que de otro modo la cabra o la
col seran 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 comera a la cabra. Si lleva la col al otro lado,
necesitar volver para coger al lobo, entonces la col sera 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.
11
Juegos Con Grafos

Campus I
La solucin se resume de la siguiente manera:

1)
2)
3)
4)
5)
6)
7)
Deja a la cabra al otro lado

Vuelve
Deja al lobo en el otro lado
Regresa con la cabra
Deja la col en el otro lado
Vuelve
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 representacin del mismo problema sera esta.
12
Juegos Con Grafos

Campus I
Dodecaedro
El dodecaedro representado en (a), poliedro formado por doce caras de pentgonos
regulares, veinte vrtices y treinta aristas, equivale topolgicamente al grafo plano
(b) que posee los mismos vrtices y lados que vrtices y aristas tena el dodecaedro
original.
Entonces, el juego se puede plantear tcnicamente as: se trata de encontrar en el
dodecaedro un camino que, partiendo de un vrtice cualquiera, vuelva a ese mismo
vrtice despus de pasar, a travs de sus aristas, por todos los dems vrtices una
sola vez. Tal recorrido se denomin ms tarde en la teora 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 haba
dibujado el dodecaedro plano. Los vrtices estaban perforados con agujeros en los
que se colocaban peones numerados o testigos del recorrido. Por lo dems, el juego
no difiere del anterior.
Solucin
Hoy en da, no se conocen mtodos generales para hallar un ciclo hamiltoniano en

tiempo polinmico, siendo la bsqueda por fuerza bruta de todos los posibles
caminos u otros mtodos excesivamente costosos. Existen, sin embargo, mtodos
para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeos.
13
Juegos Con Grafos

Campus I
Torres de Hani
LAS REGLAS
Slo se puede mover un disco cada vez.

Un disco de mayor tamao no puede descansar sobre uno ms pequeo que
l mismo.
Slo 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 propsitos del grafo, asumamos la siguiente nomenclatura. Los discos
aumentan de tamao de izquierda a derecha, es decir, el disco menor est a la
izquierda. Adems, la localizacin de disco se identificar con el nombre de la
columna. De esta forma, la notacin 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
ABC
ACA
ABA
ABB
BCC
BCA
CBB
BCB
BBB
CBC
BCB
BAB
BBC
BAC
CBA
CAC
BAA
CAA
CCA
CAB
CCB
CCC
14
Juegos Con Grafos

Campus I
Solucin
Mover el disco menor a la columna intermediaria si hay un nmero par de discos. Si

hay un nmero impar de discos, mover el disco menor a la columna destino.
1) Hacer un movimiento legal que no sea reversar el paso anterior (slo 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 ms 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 nmero mnimo de 2n - 1 (23 - 1
= 8 1 = 7) mencionado anteriormente.
AAA
AAB
AAC
ACB
ACC
ABC
ACA
ABA
ABB
BCC
BCA
CBB
BCB
BBB
CBC
BCB
CAC
BAB
BBC
BAC
CBA
BAA
CAA
CCA
CAB
CCB
CCC
Paso ptimo entre A y C
15
Juegos Con Grafos

Campus I
De este grafo es posible obtener otros pasos de inters, 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 isomrfico y realizaron un anlisis exhaustivo de su planaridad.
Hay un solo camino ptimo que conduce del estado inicial al final, as como un solo
camino de longitud mxima entre ambos estados. Este camino pasa por todos los
estados sin repetir ninguno.
AAA
AAB
AAC
ACB
ACC
AB C
ACA
ABA
ABB
BCC
BCA
CBB
BCB
BCB
BBB
CBC
BAB
BBC
BAC
CBA
CAC
BAA
CAA
CCA
CAB
CCB
CCC
16
Juegos Con Grafos

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.
Solucin
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 vrtice del grafo y se numera con esa misma cifra.
Por cada ficha de domin, se dibuja una arista que une los vrtices
correspondientes a las cifras de la ficha elegida6.
Si tenemos un grafo, se obtiene un conjunto de fichas de domin sin ms
que numerar los vrtices del grafo y tomar por cada arista del mismo la ficha
cuyas cifras son los nmeros correspondientes a los vrtices que une dicha
arista. Se muestra as que, esencialmente, es lo mismo tener grafos que
conjuntos de fichas de domin.
17
Juegos Con Grafos

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

mbito de los grafos es tambin una traduccin muy sencilla y natural
18
Juegos Con Grafos

Campus I
Problema de Collatz
Hace ms de sesenta aos, Collatz inventa y da solucin
a un problema que ha circulado desde siempre en los
medios matemticos. Lo vamos a mostrar mediante un
grafo especial que llamamos organigrama, herramienta
empleada en informtica, entre otras cosas, para
representar la lgica de los programas de ordenador y,
en general, para representar un algoritmo.
Tambin conocida como 3n+1, conjetura de Ulam, el
problema de Siracusa, la secuencia hailstone, los
nmeros hailstone y muchos ms nombres. Este es el
problema.
Qu jugador puede llegar ms rpido al nmero 1usando el problema 3n+1?
1. Tomar un entero natural cualquiera. Si es par, dividirlo por dos; si es impar,

triplicarlo y aadirle uno y nuevamente dividirlo entre dos.
2. Tomar el nmero obtenido y repetir con l el proceso 1. Y as sucesivamente.
A este algoritmo le agregu una condicin 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 nmero de
orbitas.
Solucin
Tomamos como referencia 4 jugadores que seleccionaron nmeros al azar: 336,

340, 256, y 36.
Se realizan los clculos correspondientes con la
metodologa mencionada anteriormente y se
obtiene la siguiente grfica.
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 nmero n al P(n) y
cuyas orbitas son el nivel del rbol.
Se aprecia que:
Jugador1
Jugador2
Jugador3
Jugador4
11 Orbitas
10 Orbitas
8 Orbitas
15 Orbitas
No/Pasadas
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Jugador1 Jugador2
Jugador3
Jugador4
336
340
256
168
170
128
84
85
64
42
128
32
21
64
16
64
32
8
32
16
4
16
8
2
8
4
1
4
2
2
2
1
1
1
2
2
4
1
1
2
4
4
1
2
2
4
1
1
2
4
4
19
Juegos Con Grafos
36
18
9
14
7
11
17
26
13
20
10
5
8
4
2
1
2

Campus I
Siendo el vencedor el jugador nmero 3 al tener menor nmeros de ciclos en

completar todo el trayecto hasta el numero raz.
Dentro de este rbol se observa los resultado de varios nmeros y aparece un dato
curioso: cualquiera que sea el entero de partida, se finaliza siempre con... 4, 2, 1.
20
Juegos Con Grafos

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 poda representarse en un plano sin que haya cortes entre las aristas en
puntos que no sean vrtices Sin embargo, es posible hacerlo en una
superficie terica (naturalmente un toro y un plano no son topolgicamente
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 nmero, aunque es cierto q siempre llegaras la raz
que es 1 te podra tomar m orbitas en alcanzar ese nmero, por ejemplo si
tomamos al nmero vencedor del jugador 256 y le aadimos 1 quedando
257, el nmero de orbitas que tendra dar seria de 117 haciendo q perdiera
por mucho el juego.
Tambin se muestra el denominado modelo fractal de Sierpinski que
representa la solucin grfica al problema de la Torre de Hanoi.
En esa figura, los vrtices de la estructura externa son las condiciones en
que los tres discos estn en la misma columna. Adems, que el tringulo
externo est formado por tres tringulos internos siguiendo el arreglo de
Sierpinski, y que estos, a su vez, estn formados por tringulos ms
pequeos.
Adems, parte de estas actividades no son exclusivas del rea de
Matemticas, por lo que la teora de grafos posee mltiples aplicaciones en
muy diferentes contextos fuera delos contenidos propios de las
Matemticas.
21
Juegos Con Grafos

Campus I
Referncias
Morales, J.M., Muoz & J.M.,Oller A.M.. (2009). EMPLEO DIDCTICO 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
Garca F.. (2004). La magia de los grafos. Junio 27,2015, de ACTA - Autores Cientfico-Tcnicos y
Acadmicos Sitio web: http://www.acta.es/medios/articulos/matematicas/034029.pdf
MARTN NOVO, E., MNDEZ ALONSO, A.. (2004). La magia de los grafos. Junio 27,2015, de ACTA Autores Cientfico-Tcnicos y Acadmicos Sitio web: http://revistasuma.es/IMG/pdf/46/031035.pdf
Guzmn de, M. (1984). JUEGOS MATEMTICOS EN LA ENSEANZA. Junio 27,2015, de Sociedad

Canaria
de
Profesores
de
Matemticas
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 Mbius. Junio
27,2015, de Gaussianos Sitio web: http://gaussianos.com/el-problema-de-las-tres-casas-y-los-tressuministros-y-la-banda-de-mobius/
http://www.dmae.upm.es/cursofractales/capitulo4/series/1_5.html
22
Juegos Con Grafos

Juegos Con Grafos

Cargado por

Copyright:

Formatos disponibles

Juegos Con Grafos

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Juegos Con Grafos

Cargado por

Copyright:

Formatos disponibles

GRAFOS

JUEGOS CON GRAFOS

JULIO CESAR NUEZ TEJERO

Universidad Autnoma del Carmen

Universidad Autnoma del Carmen

Universidad Autnoma del Carmen

La teora de grafos, es una parte de las Matemticas que

Universidad Autnoma del Carmen

Universidad Autnoma del Carmen

Universidad Autnoma del Carmen

Universidad Autnoma del Carmen

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

Gaston Tarry, 1843-1913, fue un matemtico francs nacido en Villefranche de

Universidad Autnoma del Carmen

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

En la misma poca que Tarry, el ingeniero francs de telgrafos, Trmeaux, haba

Universidad Autnoma del Carmen

Universidad Autnoma del Carmen

Universidad Autnoma del Carmen

Pastor, col, oveja y lobo

Universidad Autnoma del Carmen

La solucin se resume de la siguiente manera:

Deja a la cabra al otro lado

Universidad Autnoma del Carmen

Hoy en da, no se conocen mtodos generales para hallar un ciclo hamiltoniano en

Universidad Autnoma del Carmen

Slo se puede mover un disco cada vez.

Universidad Autnoma del Carmen

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

Paso ptimo entre A y C

Universidad Autnoma del Carmen

Universidad Autnoma del Carmen

El Domino (Semi) Perfecto

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

Universidad Autnoma del Carmen

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

Universidad Autnoma del Carmen

1. Tomar un entero natural cualquiera. Si es par, dividirlo por dos; si es impar,

Tomamos como referencia 4 jugadores que seleccionaron nmeros al azar: 336,

Universidad Autnoma del Carmen

Siendo el vencedor el jugador nmero 3 al tener menor nmeros de ciclos en

Universidad Autnoma del Carmen

Universidad Autnoma del Carmen

Guzmn de, M. (1984). JUEGOS MATEMTICOS EN LA ENSEANZA. Junio 27,2015, de Sociedad

También podría gustarte