malabares v2

1557 days ago by pang

Malabares y teoría de grafos

Grafo de estados de k bolas y altura h

Hipótesis:

  • El tiempo está compartimentado en instantes de igual longitud
  • En cada instante el malabarista puede hacer a lo sumo una acción (recoger una bola y volverla a lanzar)
  • En los instantes impares usa la mano izquierda y en los pares la derecha (se puede relajar)
  • El malabarista nunca tiene más de una bola en una sóla mano (se puede relajar)

Nota: en un principio no hablamos de cómo empiezan los trucos, asumimos que los trucos ya están en marcha, con todas las pelotas en el aire de modo que en ningún instante futuro esté prevista la caída de dos bolas. Sin embargo, en todos los grafos que dibujaremos hay una forma sencilla de empezar.

Estado

Un instante está caracterizado por los tiempos esperados de caída de cada bola. Un estado sólo es válido si cada bola en el aire caerá en un instante futuro distinto. Representamos un estado mediante una secuencia de bola '*' y no bola '_'. En la posición i-ésima ponemos una bola si se espera que una bola caiga dentro de i instantes y no-bola si ninguna bola caerá dentro de i instantes. Por ejemplo '**__*' quiere decir que hay tres bolas en el aire y que caerán dentro de 1, 2 y 5 instantes.

Nota: Al estado en el que las bolas caerán en los instantes sucesivos inmediatos, lo denominamos estado fundamental ('***_', ó '***__', ó lo que toque).

Altura

La fuerza y la precisión del malabarista limitan el número máximo de instantes en el que futuro al que puede enviar una bola. A este número lo llamamos altura.

Hay una cantidad finita de estados posibles con k bolas y una altura h. Concretamente, cada una de las k bolas caerá en un instante entre 1 y h que es distinto para cada bola, luego se trata de elegir k números entre 1 y h, y la cantidad de formas de hacer esta elección es ${h \choose k}$

bolas = 3 altura = 4 estados = [ ''.join(('*' if j in ss else '_') for j in range(altura)) for ss in Subsets(range(altura), bolas) ] estados 
       
['***_', '**_*', '*_**', '_***']
['***_', '**_*', '*_**', '_***']

Transiciones

¿A qué estados podemos cambiar partiendo de un estado dado? En el instante siguiente todas las bolas están un instante más próximas a caer en la mano del malabarista, luego pasamos por ejemplo de '_*_**' a '*_**_', pero si teníamos una bola a punto de caer, el malabarista la recibe y la lanza de forma que caiga dentro de un cierto número de instantes de tiempo, y puede elegir cualquier momento futuro en el que no esté prevista la caída de ninguna otra bola. Por ejemplo, del estado '*_**_' podemos pasar a '***__', '_***_' o '_**_*'.

Junto a cada posible transición, guardamos la altura a la que lanzamos la bola (usando un 0 cuando no hacemos nada).

'*
def opciones(estado): pasa = estado[1:] + '_' if estado[0]=='_': return {pasa:0} opciones = {} for j,s in enumerate(pasa): if s=='_': opciones[pasa[:j] + '*'+ pasa[j+1:]] = j + 1 return opciones transiciones = dict((estado,opciones(estado)) for estado in estados) transiciones 
       
{'***_': {'***_': 3, '**_*': 4}, '_***': {'***_': 0}, '*_**': {'***_':
1, '_***': 4}, '**_*': {'***_': 2, '*_**': 4}}
{'***_': {'***_': 3, '**_*': 4}, '_***': {'***_': 0}, '*_**': {'***_': 1, '_***': 4}, '**_*': {'***_': 2, '*_**': 4}}
def grafo_malabar(bolas, altura): '''Crea el grafo de malabares con numero de bolas y altura dadas''' estados = [ ''.join(('*' if j in ss else '_') for j in range(altura)) for ss in Subsets(range(altura), bolas) ] transiciones = dict((estado,opciones(estado)) for estado in estados) return DiGraph(transiciones) 
       

Dibujamos el grafo

g = grafo_malabar(3,4) g.show(edge_labels=True, layout='circular', vertex_size=300, figsize=8) 
       

También dibujaremos los diagramas con graphviz, porque las etiquetas se ven más claras (graphviz debe estar instalado).

attach(DATA + 'graphviz.sage') graphviz(grafo_malabar(3,4)) 
       
Traceback (click to the left of this block for traceback)
...
OSError: [Errno 2] No such file or directory
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_7.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("YXR0YWNoKERBVEEgKyAnZ3JhcGh2aXouc2FnZScpCmdyYXBodml6KGdyYWZvX21hbGFiYXIoMyw0KSk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmp_RHyLQ/___code___.py", line 4, in <module>
    exec compile(u'graphviz(grafo_malabar(_sage_const_3 ,_sage_const_4 ))
  File "", line 1, in <module>
    
  File "/home/sage/.sage/sage_notebook.sagenb/home/pang/5/data/graphviz.sagevRrEIO.py", line 22, in graphviz
    retcode = call(['circo','-Tpng', path1, '-o',path2])
  File "/usr/local/sage-5.9/local/lib/python/subprocess.py", line 493, in call
    return Popen(*popenargs, **kwargs).wait()
  File "/usr/local/sage-5.9/local/lib/python/subprocess.py", line 679, in __init__
    errread, errwrite)
  File "/usr/local/sage-5.9/local/lib/python/subprocess.py", line 1249, in _execute_child
    raise child_exception
OSError: [Errno 2] No such file or directory

Aviso: dile a David o a JoseLuis que instalen graphviz:

apt-get install graphviz

graphviz(grafo_malabar(2,4)) 
       
graphviz(grafo_malabar(3,5)) 
       

¿Qué ventajas ofrece la teoría de grafos sobre el site swap?

En pocas palabras, los grafos permiten representar situaciones muy diversas de forma muy uniforme.

Requerimientos del espectáculo de lo más variopinto se pueden traducir en restricciones sobre el grafo de posibles malabares.

Ejemplo práctico

Queremos estar a distancia menor o igual que 4 del estado '___***', por ejemplo porque ese estado nos da tiempo para hacer un truco que hemos preparado, o para saludar a un viandante que ha echado una moneda en el plato.

g = grafo_malabar(3,5) ds = g.distance_all_pairs() v0 = '__***' new_labels = {} for v in g: new_labels[v] = (v, ds[v][v0]) g.relabel(new_labels) graphviz(g)#,layout='circular', figsize=8) 
       
g = grafo_malabar(3,5) ds = g.distance_all_pairs() v0 = '__***' vs0 = [v for v in g if ds[v][v0]<=4] sg = g.subgraph(vs0) graphviz(sg) 
       

Otro ejemplo: poner una pelota en la cabeza

Ahora podemos dejar una pelota en la cabeza por tiempo indefinido. Representamos por un '8' una cabeza con una pelota encima, y por una 'o' una cabeza sin pelota encima.

Por ejemplo, para tres pelotas y altura 4, los posibles estados tienen dos pelotas en el aire y una en la cabeza, o tres pelotas en el aire y ninguna en la cabeza.

bolas = 3 altura = 4 estados_con_cabeza = ([('o' + ''.join(('*' if j in ss else '_') for j in range(altura))) for ss in Subsets(range(altura), bolas) ] + [('8' + ''.join(('*' if j in ss else '_') for j in range(altura))) for ss in Subsets(range(altura), bolas-1) ]) estados_con_cabeza 
       
['o***_', 'o**_*', 'o*_**', 'o_***', '8**__', '8*_*_', '8*__*', '8_**_',
'8_*_*', '8__**']
['o***_', 'o**_*', 'o*_**', 'o_***', '8**__', '8*_*_', '8*__*', '8_**_', '8_*_*', '8__**']

Transiciones con cabeza

Ahora tenemos opciones nuevas para pasar de un estado a otro:

  • Si tenemos la mano vacía y una pelota en la cabeza, podemos cogerla y lanzarla.
  • Si tenemos una pelota en la mano y ninguna en la cabeza, podemos dejar la pelota en la cabeza.
  • Si tenemos una pelota en la mano y otra en la cabeza, tenemos que lanzar la pelota como de costumbre.
def opciones_con_cabeza(estado): cabeza = estado[0] mano = estado[1] bolas1 = estado[2:] + '_' opciones = {} if mano=='_' and cabeza=='o': opciones = {('o' + bolas1):'0'} elif mano=='_': #and cabeza=='8' opciones['8' + bolas1] = '0' for j,s in enumerate(bolas1): if s=='_': opciones[('o' + bolas1[:j] + '*'+ bolas1[j+1:])] = 'o%d'%(j + 1) elif cabeza=='8': #and mano=='*' for j,s in enumerate(bolas1): if s=='_': opciones[('8' + bolas1[:j] + '*'+ bolas1[j+1:])] = '%d'%(j + 1) else: #cabeza=='o': #and mano=='*' opciones['8' + bolas1] = 'o0' for j,s in enumerate(bolas1): if s=='_': opciones[('o' + bolas1[:j] + '*'+ bolas1[j+1:])] = '%d'%(j + 1) return opciones def grafo_malabar_con_cabeza(bolas, altura): estados_con_cabeza = ([('o' + ''.join(('*' if j in ss else '_') for j in range(altura))) for ss in Subsets(range(altura), bolas) ] + [('8' + ''.join(('*' if j in ss else '_') for j in range(altura))) for ss in Subsets(range(altura), bolas-1) ]) transiciones = dict((estado,opciones_con_cabeza(estado)) for estado in estados_con_cabeza) g = DiGraph(transiciones) return g 
       
g = grafo_malabar_con_cabeza(3, 4) graphviz(g) 
       

Y mucho más

  • Bolas distintas (por su color o por su naturaleza).
  • Varios malabaristas.
  • ...

Más ejemplos en los ejercicios del final.

 
       
 
       

Propiedades de los grafos malabares

Y bien, ¿qué hacemos una vez tenemos un grafo? Para empezar, nos podemos preguntar si el grafo tiene algunas propiedades típicas de la teoría de grafos que pueden ser interesantes:

  • ¿El grafo es fuertemente conexo? Es decir, ¿se puede pasar de un estado a cualquier otro?
  • ¿El grafo de malabares es euleriano? Es decir, ¿existe un circuito que pasa por cada arista exactamente una vez?
  • ¿El grafo de malabares es hamiltoniano? Es decir, ¿existe un circuito que pasa por cada vértice exactamente una vez?
for j in range(2,5): for k in range(j+1,j+4): print 'el grafo malabar con %d bolas y altura %d\ %ses fuertemente conexo'%(j,k,s malabaristas. '' if grafo_malabar(j,k).is_strongly_connected() else 'no ') 
       
el grafo malabar con 2 bolas y altura 3 es fuertemente conexo
el grafo malabar con 2 bolas y altura 4 es fuertemente conexo
el grafo malabar con 2 bolas y altura 5 es fuertemente conexo
el grafo malabar con 3 bolas y altura 4 es fuertemente conexo
el grafo malabar con 3 bolas y altura 5 es fuertemente conexo
el grafo malabar con 3 bolas y altura 6 es fuertemente conexo
el grafo malabar con 4 bolas y altura 5 es fuertemente conexo
el grafo malabar con 4 bolas y altura 6 es fuertemente conexo
el grafo malabar con 4 bolas y altura 7 es fuertemente conexo
el grafo malabar con 2 bolas y altura 3 es fuertemente conexo
el grafo malabar con 2 bolas y altura 4 es fuertemente conexo
el grafo malabar con 2 bolas y altura 5 es fuertemente conexo
el grafo malabar con 3 bolas y altura 4 es fuertemente conexo
el grafo malabar con 3 bolas y altura 5 es fuertemente conexo
el grafo malabar con 3 bolas y altura 6 es fuertemente conexo
el grafo malabar con 4 bolas y altura 5 es fuertemente conexo
el grafo malabar con 4 bolas y altura 6 es fuertemente conexo
el grafo malabar con 4 bolas y altura 7 es fuertemente conexo
for j in range(2,5): for k in range(j+1,j+4): print 'el grafo malabar con %d bolas y altura %d\ %ses euleriano'%(j,k, '' if grafo_malabar(j,k).is_eulerian() else 'no ') 
       
el grafo malabar con 2 bolas y altura 3 no es euleriano
el grafo malabar con 2 bolas y altura 4 no es euleriano
el grafo malabar con 2 bolas y altura 5 no es euleriano
el grafo malabar con 3 bolas y altura 4 no es euleriano
el grafo malabar con 3 bolas y altura 5 no es euleriano
el grafo malabar con 3 bolas y altura 6 no es euleriano
el grafo malabar con 4 bolas y altura 5 no es euleriano
el grafo malabar con 4 bolas y altura 6 no es euleriano
el grafo malabar con 4 bolas y altura 7 no es euleriano
el grafo malabar con 2 bolas y altura 3 no es euleriano
el grafo malabar con 2 bolas y altura 4 no es euleriano
el grafo malabar con 2 bolas y altura 5 no es euleriano
el grafo malabar con 3 bolas y altura 4 no es euleriano
el grafo malabar con 3 bolas y altura 5 no es euleriano
el grafo malabar con 3 bolas y altura 6 no es euleriano
el grafo malabar con 4 bolas y altura 5 no es euleriano
el grafo malabar con 4 bolas y altura 6 no es euleriano
el grafo malabar con 4 bolas y altura 7 no es euleriano
for j in range(2,5): for k in range(j+1,j+4): print 'el grafo malabar con %d bolas y altura %d\ %ses hamiltoniano'%(j,k, '' if grafo_malabar(j,k).is_hamiltonian() else 'no ') 
       
el grafo malabar con 2 bolas y altura 3 es hamiltoniano
el grafo malabar con 2 bolas y altura 4 no es hamiltoniano
el grafo malabar con 2 bolas y altura 5 no es hamiltoniano
el grafo malabar con 3 bolas y altura 4 es hamiltoniano
el grafo malabar con 3 bolas y altura 5 no es hamiltoniano
el grafo malabar con 3 bolas y altura 6 no es hamiltoniano
el grafo malabar con 4 bolas y altura 5 es hamiltoniano
el grafo malabar con 4 bolas y altura 6 no es hamiltoniano
el grafo malabar con 4 bolas y altura 7 no es hamiltoniano
el grafo malabar con 2 bolas y altura 3 es hamiltoniano
el grafo malabar con 2 bolas y altura 4 no es hamiltoniano
el grafo malabar con 2 bolas y altura 5 no es hamiltoniano
el grafo malabar con 3 bolas y altura 4 es hamiltoniano
el grafo malabar con 3 bolas y altura 5 no es hamiltoniano
el grafo malabar con 3 bolas y altura 6 no es hamiltoniano
el grafo malabar con 4 bolas y altura 5 es hamiltoniano
el grafo malabar con 4 bolas y altura 6 no es hamiltoniano
el grafo malabar con 4 bolas y altura 7 no es hamiltoniano
for j in range(2,5): for k in range(j+1,j+4): print 'el grafo malabar con %d bolas, altura %d y con cabeza\ %ses hamiltoniano'%(j,k, '' if grafo_malabar_con_cabeza(j,k).is_hamiltonian() else 'no ') 
       
el grafo malabar con 2 bolas, altura 3 y con cabeza es hamiltoniano
el grafo malabar con 2 bolas, altura 4 y con cabeza es hamiltoniano
el grafo malabar con 2 bolas, altura 5 y con cabeza es hamiltoniano
el grafo malabar con 3 bolas, altura 4 y con cabeza es hamiltoniano
el grafo malabar con 3 bolas, altura 5 y con cabeza es hamiltoniano
el grafo malabar con 3 bolas, altura 6 y con cabeza es hamiltoniano
el grafo malabar con 4 bolas, altura 5 y con cabeza es hamiltoniano
el grafo malabar con 4 bolas, altura 6 y con cabeza es hamiltoniano
el grafo malabar con 4 bolas, altura 7 y con cabeza es hamiltoniano
el grafo malabar con 2 bolas, altura 3 y con cabeza es hamiltoniano
el grafo malabar con 2 bolas, altura 4 y con cabeza es hamiltoniano
el grafo malabar con 2 bolas, altura 5 y con cabeza es hamiltoniano
el grafo malabar con 3 bolas, altura 4 y con cabeza es hamiltoniano
el grafo malabar con 3 bolas, altura 5 y con cabeza es hamiltoniano
el grafo malabar con 3 bolas, altura 6 y con cabeza es hamiltoniano
el grafo malabar con 4 bolas, altura 5 y con cabeza es hamiltoniano
el grafo malabar con 4 bolas, altura 6 y con cabeza es hamiltoniano
el grafo malabar con 4 bolas, altura 7 y con cabeza es hamiltoniano
 
       

Circuitos cerrados

Aunque podemos movernos indefinidamente por el grafo sin repetirnos, antes o después pasaremos dos veces por el mismo nodo y en ese momento habremos completado un circuito.

path2

Circuitos primos

Si un circuito pasa dos veces por el mismo sitio, es composición de circuitos elementales o primos, en los que no se pasa dos veces por el mismo vértice.

Los caminos en el grafo son composición de estos caminos elementales. En cierto modo, es equivalente a cómo el desarrollo decimal de un número puede no ser periódico (por ejemplo, el desarollo de $\pi$), pero todos los números se pueden desarrollar con los mismo dígitos.

Listar todos los circuitos primos

La teoría de circuitos cerrados en un grafo no dirigido es preciosa y tiene una descripción matemática muy elegante, que en última instancia se debe a que se puede definir una suma de caminos. Sin embargo, para grafos dirigidos no se puede definir la suma de caminos y las matemáticas no dan una visión tan clara del conjunto de circuitos. Afortunadamente, existen algoritmos eficientes para encontrar todos los circuitos elementales en un grafo dirigido. Aunque la complejidad del algoritmo es exponencial en el tamaño del grafo, es lineal en el número de circutos.

Nota: si al recorrer un circuito, listamos la altura a la que debemos lanzar cada pelota (la arista de cada nodo), recuperamos la notación siteswap.

Todos los posibles trucos con 3 bolas y altura a lo sumo 4: listamos los circuitos del grafo malabar con 3 bolas y altura máxima 4, en notación siteswap.

g = grafo_malabar(3,4) for ls in g.all_simple_cycles(): aristas = [(ls[j],ls[j+1]) for j in range(len(ls)-1)] sg = g.subgraph(edges = aristas) print [g.edge_label(v1,v2) for v1,v2 in aristas] graphviz(sg) 
       
[3]

[4, 2]

[4, 4, 1]

[4, 4, 4, 0]
[3]

[4, 2]

[4, 4, 1]

[4, 4, 4, 0]
g = grafo_malabar(3,4) g.show(edge_labels=True, layout='circular', vertex_size=300, figsize=8) graphs_list.show_graphs([g.subgraph(edges = [(ls[j],ls[j+1]) for j in range(len(ls)-1)]) for ls in g.all_simple_cycles()]) 
       

Todos los posibles trucos con 3 bolas y altura a lo sumo 5.

g = grafo_malabar(3,5) for ls in g.all_simple_cycles(): aristas = [(ls[j],ls[j+1]) for j in range(len(ls)-1)] print ''.join([str(g.edge_label(v1,v2)) for v1,v2 in aristas]) 
       
3
42
51
441
531
522
450
4440
4530
5340
5241
5511
5520
45501
53502
52440
52530
55140
55500
55050
455040
525501
551502
5350530
5255040
55150530
3
42
51
441
531
522
450
4440
4530
5340
5241
5511
5520
45501
53502
52440
52530
55140
55500
55050
455040
525501
551502
5350530
5255040
55150530

La misma información, de forma gráfica.

g = grafo_malabar(3,5) show(g, edge_labels=True, layout='circular', figsize = 8, vertex_size=400) graphs_list.show_graphs([g.subgraph(edges = [(ls[j],ls[j+1]) for j in range(len(ls)-1)]) for ls in g.all_simple_cycles()]) 
       

Finalmente, la misma información para el grafo de malabares con cabeza

g = grafo_malabar_con_cabeza(3,4) for ls in g.all_simple_cycles(): aristas = [(ls[j],ls[j+1]) for j in range(len(ls)-1)] print ','.join([str(g.edge_label(v1,v2)) for v1,v2 in aristas]) show(g, edge_labels=True, layout='circular', figsize = 8, vertex_size=400) subgrafos = [g.subgraph(edges = [(ls[j],ls[j+1]) for j in range(len(ls)-1)]) for ls in g.all_simple_cycles()] graphs_list.show_graphs(subgrafos) 
       
2
3
3,1
4,0
4,2
3,3,0
4,1,1
4,2,0
3,o4,o0
o4,4,o0
4,4,1
3,4,o2,o0
3,3,o3,o0
4,1,3,0
4,4,o1,o0
4,4,0,0
4,2,o3,o0
4,o2,4,o0
3,o3,4,o0
o3,4,4,o0
4,4,4,0
3,4,o4,1,o0
3,4,o4,o0,0
3,3,o4,2,o0
4,1,4,o2,o0
4,1,3,o3,o0
4,4,o4,0,o0
4,4,0,o3,o0
4,2,o4,o0,1
4,2,o4,2,o0
4,o4,1,4,o0
4,o4,o0,o4,o0
3,4,o4,4,0,o0
3,4,o4,o0,o3,o0
3,3,o4,4,1,o0
4,1,4,o4,1,o0
4,1,4,o4,o0,0
4,1,3,o4,2,o0
4,4,o1,4,o0,1
4,4,0,o4,o0,1
4,4,0,o4,2,o0
4,2,o4,4,1,o0
4,2,o3,4,o0,1
4,o4,4,0,4,o0
4,o4,o0,o3,4,o0
3,4,o4,o0,o4,2,o0
3,4,o2,4,4,o0,0
3,3,o4,4,4,0,o0
4,1,4,o4,4,0,o0
4,1,4,o4,o0,o3,o0
4,1,3,o4,4,1,o0
4,4,o1,4,o0,3,0
4,4,o1,4,4,o0,0
4,4,o4,0,4,o0,1
4,4,0,o4,4,1,o0
4,4,0,o3,4,o0,1
4,2,o4,o0,4,o2,o0
4,2,o4,4,4,0,o0
4,1,4,o4,o0,o4,2,o0
4,1,4,o2,4,4,o0,0
4,1,3,o4,4,4,0,o0
4,4,o4,0,4,o0,3,0
4,4,o4,0,4,4,o0,0
4,4,0,o4,o0,4,o2,o0
4,4,0,o4,4,4,0,o0
4,2,o4,o0,4,o4,1,o0
4,4,o1,4,o0,4,o4,o0,0
4,4,0,o4,o0,4,o4,1,o0
4,2,o4,o0,4,o4,4,0,o0
4,4,o4,0,4,o0,4,o4,o0,0
4,4,0,o4,o0,4,o4,4,0,o0
2
3
3,1
4,0
4,2
3,3,0
4,1,1
4,2,0
3,o4,o0
o4,4,o0
4,4,1
3,4,o2,o0
3,3,o3,o0
4,1,3,0
4,4,o1,o0
4,4,0,0
4,2,o3,o0
4,o2,4,o0
3,o3,4,o0
o3,4,4,o0
4,4,4,0
3,4,o4,1,o0
3,4,o4,o0,0
3,3,o4,2,o0
4,1,4,o2,o0
4,1,3,o3,o0
4,4,o4,0,o0
4,4,0,o3,o0
4,2,o4,o0,1
4,2,o4,2,o0
4,o4,1,4,o0
4,o4,o0,o4,o0
3,4,o4,4,0,o0
3,4,o4,o0,o3,o0
3,3,o4,4,1,o0
4,1,4,o4,1,o0
4,1,4,o4,o0,0
4,1,3,o4,2,o0
4,4,o1,4,o0,1
4,4,0,o4,o0,1
4,4,0,o4,2,o0
4,2,o4,4,1,o0
4,2,o3,4,o0,1
4,o4,4,0,4,o0
4,o4,o0,o3,4,o0
3,4,o4,o0,o4,2,o0
3,4,o2,4,4,o0,0
3,3,o4,4,4,0,o0
4,1,4,o4,4,0,o0
4,1,4,o4,o0,o3,o0
4,1,3,o4,4,1,o0
4,4,o1,4,o0,3,0
4,4,o1,4,4,o0,0
4,4,o4,0,4,o0,1
4,4,0,o4,4,1,o0
4,4,0,o3,4,o0,1
4,2,o4,o0,4,o2,o0
4,2,o4,4,4,0,o0
4,1,4,o4,o0,o4,2,o0
4,1,4,o2,4,4,o0,0
4,1,3,o4,4,4,0,o0
4,4,o4,0,4,o0,3,0
4,4,o4,0,4,4,o0,0
4,4,0,o4,o0,4,o2,o0
4,4,0,o4,4,4,0,o0
4,2,o4,o0,4,o4,1,o0
4,4,o1,4,o0,4,o4,o0,0
4,4,0,o4,o0,4,o4,1,o0
4,2,o4,o0,4,o4,4,0,o0
4,4,o4,0,4,o0,4,o4,o0,0
4,4,0,o4,o0,4,o4,4,0,o0



 
       

Ejercicios

  • Escribe el grafo de malabares con dos pelotas de un color y una tercera de otro color y altura máxima 4. Si la tercera pelota es una manzana, identifica los estados en los que puedes pegarle un mordisco.
  • Escribe el grafo de estados para dos malabaristas, con 5 pelotas y altura máxima 3. Los malabaristas pueden pasarle cada pelota al otro o lanzarla para recogerla ellos mismos.
  • Pepito está aprendiendo a hacer malabares con cuchillos. Se ve capaz de lanzar y recibir los cuchillos a altura 5 pero no quiere lanzar dos cuchillos seguidos tan alto por si se hace un lío al recogerlos. Modifica el grafo de tres objetos y altura 5 para evitar lanzar dos objetos a altura 5 seguidos.
  • Genera el grafo de dos malabaristas con altura máxima 3 y un total de 5 bolas trabajando en modo canon (los tiempos de uno y otro malabarista no están sincronzados, sino que tienen un retraso de medio tiempo). A modo de pista, tienes más abajo la construcción del grafo de n malabaristas, pero en modo síncrono.

Cuestiones

  • ¿Cuántos circuitos hamiltonianos tiene el grafo_malabar_con_cabeza(3,4)?
  • Identifica en cada grafo el estado o estado "fundamentales", que debe verificar dos propiedades: que sea fácil alcanzar ese estado empezando con todas las bolas en la mano, y que se pueda mantener de forma indefinida.
 
       
 
       

Camino aleatorio en el grafo

Podemos movernos libremente sobre el grafo, sin necesidad de seguir uno de los patrones de siteswap como 441 o 531. Creamos a continuación una animación que cada segundo muestra el estado en que nos encontramos dentro del grafo y el número asociado a la arista que seguimos para llegar al siguiente estado (que es la altura a la que tenemos que lanzar la bola). Cada vez que podemos elegir una arista entre varias posibilidades, escogemos una de las opciones con igual probabilidad.

def camino_aleatorio(g, estado_inicial, longitud=10): vs = g.vertices() vs.remove(estado_inicial) ps = [g.plot(edge_labels=True, layout='circular', vertex_size = 400, vertex_colors={'blue':[estado_inicial], 'white':vs})+ text('...', (0,0), fontsize=200)] v0 = estado_inicial for j in xrange(longitud): v0,v1,altura = choice(g.outgoing_edges(v0)) if v1 != v0: vs.remove(v1) vs.append(v0) ps.append(g.plot(edge_labels=True, layout='circular', vertex_size = 400, vertex_colors={'blue':[v1], 'white':vs}) + text(altura, (0,0), fontsize=200)) v0 = v1 return animate(ps, axes = False, figsize = 8) 
       
g = grafo_malabar(3,5) #Partimos del estado fundamental a = camino_aleatorio(g, '***__', longitud = 10) a.show(delay = 200) 
       
g = grafo_malabar(3,4) #Partimos del estado fundamental a = camino_aleatorio(g, '***_', longitud = 10) a.show(delay = 200) 
       
 
       

Cadena de Markov

Si cada vez que lanzamos una bola escogemos la altura entre las posibilidades viables con igual probabilidad, ¿cuánto tiempo pasaremos en cada estado?

Para empezar a entender el problema, trabajamos con 3 bolas y altura 4, y nos planteamos qué pasaría si repetimos el experimento 1000 veces, partiendo por ejemplo del estado fundamental '***_'. En el primer lanzamiento, podemos elegir entre hacer un lanzamiento a altura 3 ó 4, de modo que 500 veces estaremos en el estado '***_' y otras 500 en el estado '**_*'. Si hacemos dos lanzamientos, tenemos dos decisiones, lo que da lugar a 4 caminos, y seguiremos cada uno de los cuatro en 250 ocasiones. Sin embargo, dos de esos caminos llevan al estado fundamental, luego en 500 ocasiones nos encontramos en '***_', en 250 en '**_*' y en otras 250 en '*_**'.

Por supuesto, lo importante no es el número absoluto de lanzamientos, sino la proporción sobre el número de lanzamientos (es decir, 1/2 de las veces nos encontramos en '***_', 1/4 de las veces en '**_*' y el otro 1/4 de las veces en '*_**'.). La manera habitual de registrar el experimento anterior en matemáticas es guardar estas proporciones, o probabilidades, en un vector donde guardamos las probabilidades en el orden correspodiente a ['***_', '**_*', '*_**', '_***']. En el ejemplo anterior, decimos que estamos en el estado [1/2, 1/4, 1/4, 0]. El estado inicial era el estado determinista [1,0,0,0], y el estado en el primer instante después de empezar era [1/2, 1/2, 0, 0].

Para calcular las probabilidades en un estado a partir de las probabilidades en el anterior, construimos una matriz con las probabilidades de transición a partir de cada estado. Para obtener las probabilidades en un estado a partir de las probabilidades en el anterior, multiplicamos el vector de probabilidades por la matriz de probabilidades de transición.

Esta forma de calcular las transiciones se basa en el teorema de la probabilidad total. La probabilidad de estar en el estado I en tiempo k+1 es igual a la suma para cada estado J del producto de la probabilidad del estado J en tiempo k por la probabilidad de transición de J a I:

$$P_{k+1}(I) = \sum_{J} P_k(J) P_{k\rightarrow k+1}(I|J)$$

escrito en forma vectorial:

$$P_{k+1} = P_{k}\cdot M$$

La matriz de probabilidades de transición se obtiene de forma sencilla a partir de la matriz de adyacencia del grafo, que tiene un 1 en la posición (i,j) si hay una flecha del vértice i-ésimo al j-ésimo, y 0 en otro caso.

g = grafo_malabar(3,4) print g.vertices() show(g.adjacency_matrix()) M = matrix([row/sum(row) for row in g.adjacency_matrix().rows()]) show(M) 
       
['***_', '**_*', '*_**', '_***']
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ 1 & 0 & 0 & 0 \end{array}\right)
['***_', '**_*', '*_**', '_***']
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ 1 & 0 & 0 & 0 \end{array}\right)

Calculamos el vector de probabilidades hasta después de 10 instantes.

print g.vertices() M = matrix([row/sum(rowestado*M) for row in g.adjacency_matrix().rows()]) # Partiendo de un estado inicial [1,0,...0]) estado = vector( [1]+[0]*(len(g.vertices())-1) ) n3 = lambda x: x.n(digits = 3) for k in range(10): print k, ':', map(n3, estado) estado = estado*M 
       
['***_', '**_*', '*_**', '_***']
0 : [1.00, 0.000, 0.000, 0.000]
1 : [0.500, 0.500, 0.000, 0.000]
2 : [0.500, 0.250, 0.250, 0.000]
3 : [0.500, 0.250, 0.125, 0.125]
4 : [0.562, 0.250, 0.125, 0.0625]
5 : [0.531, 0.281, 0.125, 0.0625]
6 : [0.531, 0.266, 0.141, 0.0625]
7 : [0.531, 0.266, 0.133, 0.0703]
8 : [0.535, 0.266, 0.133, 0.0664]
9 : [0.533, 0.268, 0.133, 0.0664]
['***_', '**_*', '*_**', '_***']
0 : [1.00, 0.000, 0.000, 0.000]
1 : [0.500, 0.500, 0.000, 0.000]
2 : [0.500, 0.250, 0.250, 0.000]
3 : [0.500, 0.250, 0.125, 0.125]
4 : [0.562, 0.250, 0.125, 0.0625]
5 : [0.531, 0.281, 0.125, 0.0625]
6 : [0.531, 0.266, 0.141, 0.0625]
7 : [0.531, 0.266, 0.133, 0.0703]
8 : [0.535, 0.266, 0.133, 0.0664]
9 : [0.533, 0.268, 0.133, 0.0664]

Mostramos la información de modo gráfico: en la siguiente animación mostramos la probabilidad como tonalidad de azul: mayor tonalidad de azul corresponde a mayor probabilidad. Comenzamos con el estado fundamental completamente azul y todos los demás blancos, lo que corresponde a que estamos en el estado fundamental con total seguridad (con probabilidad 1), pero en cada instante de tiempo cada nodo bifurca la mitad de su probabilidad (su "cantidad de azul") a todos los estados a los que se puede acceder desde este en un solo paso.

def cadena_de_Markov(g, prob_inicial, longitud=10): vs = g.vertices() probs = vector(prob_inicial[v] for v in vs) ps = [g.plot(edge_labels=True, layout='circular', vertex_size = 400, vertex_colors=dict(((1-p,1-p,1-0.001*random()),[v]) for v,p in zip(vs,probs)))+ text(map(n3,probs), (0,-1.2), fontsize=20)]*2 M = matrix([row/sum(row) for row in g.adjacency_matrix().rows()]) for j in xrange(longitud): probs = probs*M ps.append(g.plot(edge_labels=True, layout='circular', vertex_size = 400, vertex_colors=dict(((1-p,1-p,1-0.001*random()),[v]) for v,p in zip(vs,probs)))+ text(map(n3,probs), (0,-1.2), fontsize=20)) return animate(ps, axes = False, figsize = 8) 
       
g = grafo_malabar(3,4) probs = {'***_':1, '**_*':0, '_***':0, '*_**':0, } a = cadena_de_Markov(g, probs) a.show(delay = 200) 
       

Repetimos el experimento pero partiendo de un estado inicial distinto.

g = grafo_malabar(3,4) probs = {'***_':0, '**_*':0, '_***':0, '*_**':1, } a = cadena_de_Markov(g, probs) a.show(delay = 200) 
       

Observamos que las probabilidades de transición parecen acercarse al vector [0.533, 0.267, 0.133, 0.0667], y que una vez se llega a ese vector las probabilidades ya no cambian. Para más inri, comprobamos que se llega al mismo vector independientemente del estado inicial.

print g.vertices() M = matrix([row/sum(row) for row in g.adjacency_matrix().rows()]) # Partiendo de un estado inicial [1,0,...0]) estado = vector( [0,0,1,0]) n3 = lambda x: x.n(digits = 3) for k in range(10): print k, ':', map(n3, estado) estado = estado*M 
       
['***_', '**_*', '*_**', '_***']
0 : [0.000, 0.000, 1.00, 0.000]
1 : [0.500, 0.000, 0.000, 0.500]
2 : [0.750, 0.250, 0.000, 0.000]
3 : [0.500, 0.375, 0.125, 0.000]
4 : [0.500, 0.250, 0.188, 0.0625]
5 : [0.531, 0.250, 0.125, 0.0938]
6 : [0.547, 0.266, 0.125, 0.0625]
7 : [0.531, 0.273, 0.133, 0.0625]
8 : [0.531, 0.266, 0.137, 0.0664]
9 : [0.533, 0.266, 0.133, 0.0684]
['***_', '**_*', '*_**', '_***']
0 : [0.000, 0.000, 1.00, 0.000]
1 : [0.500, 0.000, 0.000, 0.500]
2 : [0.750, 0.250, 0.000, 0.000]
3 : [0.500, 0.375, 0.125, 0.000]
4 : [0.500, 0.250, 0.188, 0.0625]
5 : [0.531, 0.250, 0.125, 0.0938]
6 : [0.547, 0.266, 0.125, 0.0625]
7 : [0.531, 0.273, 0.133, 0.0625]
8 : [0.531, 0.266, 0.137, 0.0664]
9 : [0.533, 0.266, 0.133, 0.0684]

Pero también podemos observar que para hacer evolucionar un estado k pasos, multiplicamos la distribución de probabilidad por la matriz de transición k veces, y esto es equivalente a multiplicar por la matriz $M^k$.

Observamos que las potencias de la matriz M convergen a una matriz de rango 1, que envía cualquier vector cuyas entradas sumen 1 al mismo vector.

n3 = lambda x: x.n(digits = 3) show((M).apply_map(n3)) show((M^2).apply_map(n3)) show((M^5).apply_map(n3)) show((M^10).apply_map(n3)) show((M^30).apply_map(n3)) 
       
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 0.500 & 0.500 & 0.000 & 0.000 \\ 0.500 & 0.000 & 0.500 & 0.000 \\ 0.500 & 0.000 & 0.000 & 0.500 \\ 1.00 & 0.000 & 0.000 & 0.000 \end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 0.500 & 0.250 & 0.250 & 0.000 \\ 0.500 & 0.250 & 0.000 & 0.250 \\ 0.750 & 0.250 & 0.000 & 0.000 \\ 0.500 & 0.500 & 0.000 & 0.000 \end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 0.531 & 0.281 & 0.125 & 0.0625 \\ 0.531 & 0.250 & 0.156 & 0.0625 \\ 0.531 & 0.250 & 0.125 & 0.0938 \\ 0.562 & 0.250 & 0.125 & 0.0625 \end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 0.533 & 0.267 & 0.134 & 0.0664 \\ 0.533 & 0.267 & 0.133 & 0.0674 \\ 0.534 & 0.267 & 0.133 & 0.0664 \\ 0.533 & 0.268 & 0.133 & 0.0664 \end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 0.533 & 0.267 & 0.133 & 0.0667 \\ 0.533 & 0.267 & 0.133 & 0.0667 \\ 0.533 & 0.267 & 0.133 & 0.0667 \\ 0.533 & 0.267 & 0.133 & 0.0667 \end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 0.500 & 0.500 & 0.000 & 0.000 \\ 0.500 & 0.000 & 0.500 & 0.000 \\ 0.500 & 0.000 & 0.000 & 0.500 \\ 1.00 & 0.000 & 0.000 & 0.000 \end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 0.500 & 0.250 & 0.250 & 0.000 \\ 0.500 & 0.250 & 0.000 & 0.250 \\ 0.750 & 0.250 & 0.000 & 0.000 \\ 0.500 & 0.500 & 0.000 & 0.000 \end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 0.531 & 0.281 & 0.125 & 0.0625 \\ 0.531 & 0.250 & 0.156 & 0.0625 \\ 0.531 & 0.250 & 0.125 & 0.0938 \\ 0.562 & 0.250 & 0.125 & 0.0625 \end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 0.533 & 0.267 & 0.134 & 0.0664 \\ 0.533 & 0.267 & 0.133 & 0.0674 \\ 0.534 & 0.267 & 0.133 & 0.0664 \\ 0.533 & 0.268 & 0.133 & 0.0664 \end{array}\right)
\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 0.533 & 0.267 & 0.133 & 0.0667 \\ 0.533 & 0.267 & 0.133 & 0.0667 \\ 0.533 & 0.267 & 0.133 & 0.0667 \\ 0.533 & 0.267 & 0.133 & 0.0667 \end{array}\right)

La teoría de cadenas de Markov nos dice que se alcanza una distribución de probabilidad estable, independiente del punto de partida. Este es un hecho general que se verifica bajo hipótesis muy generales que verifican todos los grafos que hemos visto. El vector con las probabilidades es un autovector por la izquierda de autovalor 1 de la matriz M. Como el grafo es fuertemente conexo y tiene una arista que une un vértice consigo mismo, la cadena de Markov es irreducible y este autovector es único salvo escala. Escogemos el vector tal que la suma de sus componentes es uno.

#print M.eigenvectors_left()[0][1] distribucion_estable = (M - 1).left_kernel().basis()[0] distribucion_estable /= sum(distribucion_estable) print g.vertices() print distribucion_estable print [n3(p) for p in distribucion_estable] 
       
['***_', '**_*', '*_**', '_***']
(8/15, 4/15, 2/15, 1/15)
[0.533, 0.267, 0.133, 0.0667]
['***_', '**_*', '*_**', '_***']
(8/15, 4/15, 2/15, 1/15)
[0.533, 0.267, 0.133, 0.0667]

Aplicamos lo anterior al grafo de malabares usando la cabeza. Mostramos sólo la distribución de probabilidad estable.

g = grafo_malabar_con_cabeza(3,4) vs = g.vertices() probs = vector([1/len(g)]*len(g)) M = matrix([row/sum(row) for row in g.adjacency_matrix().rows()]) probs = (M - 1).left_kernel().basis()[0] probs /= sum(probs) p = g.plot(edge_labels=True, layout='circular', vertex_size = 400, vertex_colors=dict(((1-p,1-p,1-0.001*random()),[v]) for v,p in zip(vs,probs))) print dict(zip(g.vertices(), map(n3,probs))) p.show(axes = False, figsize = 8) 
       
{'8__**': 0.0250, 'o**_*': 0.100, '8**__': 0.225, '8_**_': 0.100,
'8*__*': 0.0750, 'o_***': 0.0250, '8_*_*': 0.0500, 'o*_**': 0.0500,
'8*_*_': 0.150, 'o***_': 0.200}
{'8__**': 0.0250, 'o**_*': 0.100, '8**__': 0.225, '8_**_': 0.100, '8*__*': 0.0750, 'o_***': 0.0250, '8_*_*': 0.0500, 'o*_**': 0.0500, '8*_*_': 0.150, 'o***_': 0.200}
 
       

Palabras finales sobre las cadenas de Markov

Como vemos, la probabilidad de estar en cada nodo al cabo de un número grande de iteraciones no depende del estado inicial. Esta probabilidad se puede usar por tanto para medir la importancia de cada nodo (es decir, cómo de bien está conectado). No hay nada en esta idea que sea específico de las malabares, y de hecho esta idea se aplica a grafos de todo tipo. Por ejemplo, Google afirma que su algoritmo original para asignar una importancia a cada página web estaba basado en esta idea.

Referencia: El secreto de Google de Pablo Fernández Gallardo.

 
       

Apéndice: varios malabaristas

Grafo de varios malabaristas que tienen todos la misma altura como cota y con una cantidad dada de bolas en total. Observa que si en un instante varios malabaristas deben lanzar una bola, sólo anotamos los destinos de esas bolas, sin distinguir quién hace qué lanzamiento. Es decir, que no distinguimos si cada malabarista se lanza a sí mismo o si cada uno le lanza al otro. Representamos cada estado mediante la unión de las listas de espera de todos los malabaristas, y cada arista mediante pares que dicen el malabarista que debe recibir y la altura del lanzamiento.

def opcionesm(estado): estado1 = tuple(malabarista[1:] + '_' for malabarista in estado) bolas = sum(1 if malabarista[0]=='*' else 0 for malabarista in estado) if not bolas: return {estado1:'0'} huecos = [(i, j) for i,malabarista in enumerate(estado1) for j,s in enumerate(malabarista) if s=='_'] opciones = {} for objetivos in Combinations(huecos, bolas): nuevo_estado = list(estado1) for i, j in objetivos: cadena = nuevo_estado[i] nuevo_estado[i] = cadena[:j] + '*'+ cadena[j+1:] opciones[tuple(nuevo_estado)] = ','.join('%d%d'%(i+1,j+1) for i, j in objetivos) return opciones def grafo_malabarm(bolas, altura, malabaristas): '''Crea el grafo de malabares para varios malabarista Acepta como argumento el numero de bolas y la lista de alturas máximas de cada malabarista''' total = altura*malabaristas cadenas = [ ''.join(('*' if j in ss else '_') for j in range(total)) for ss in Subsets(range(total), bolas) ] parte =lambda c: tuple(c[j:j+altura] for j in range(0, total, altura)) estadosm = [parte(c) for c in cadenas] transiciones = dict((estado,opcionesm(estado)) for estado in estadosm) return DiGraph(transiciones) 
       
#5 bolas, dos malabaristas a altura 3 cada uno g = grafo_malabarm(5, 3, 2) graphviz(g) 
       

Coda: un malabarista y un inútil

¿Podemos encontrar un truco en el que un inútil hace malabares con un malabarista?

  • el inútil no puede tener más de una bola en su lista de caída
  • el inútil no puede lanzar a altura mayor que 2
#3 bolas, el malabarista trabaja a altura 3, el inutil a altura 2 g = grafo_malabarm(3,3,2) #Añadimos la restricción de que el inútil #sólo puede tener una bola en la mano cota_bolas = 1 vs = [v for v in g.vertices() if sum(1 for c in v[0] if c=='*')<=cota_bolas ] sg = g.subgraph(vertices = vs) graphviz(sg) 
       
#Añadimos la restricción de que el inútil #sólo puede lanzar a altura menor o igual que dos cota_altura = 2 def criterio(arista): '''Decide si una arista exige que el primer malabarista tenga que lanzar mas alto que su cota ''' e1,e2,lanzamientos = arista m1, m2 = e1 if m1[0] == '_': return True if m2[0] == '_': return int(lanzamientos[1]) <= cota_altura return (int(lanzamientos[1]) <= cota_altura or int(lanzamientos[4]) <= cota_altura) aristas = [arista for arista in g.edges() if criterio(arista) ] sg2 = sg.subgraph(edges = aristas) graphviz(sg2) 
       
#Todos los circuitos g = sg2 for ls in g.all_simple_cycles(): aristas = [(ls[j],ls[j+1]) for j in range(len(ls)-1)] print ';'.join([str(g.edge_label(v1,v2)) for v1,v2 in aristas]) show(g, edge_labels=True, layout='circular', figsize = 8, vertex_size=800) subgrafos = [g.subgraph(edges = [(ls[j],ls[j+1]) for j in range(len(ls)-1)]) for ls in g.all_simple_cycles()] graphs_list.show_graphs(subgrafos) 
       
11,22
23
12,23;21
22,23;11
12,22;22
11,23;11,21
12,21;23
12,23;23;11
22,23;12;22
13,22;23;21
13,22;22;22
12,22;23;11,21
11,23;21,23;11
11,23;12,23;0
11,23;11,23;11
11,23;12,21;22
21,23;12;23
13,21;22;23
11,23;12;23
12,23;23;12;22
22,23;13;23;21
22,23;13;22;22
22,23;12;23;11,21
13,22;23;23;11
13,22;22;23;11,21
12,22;23;21,23;11
12,22;23;12,23;0
12,22;23;11,23;11
11,23;21,23;12;22
11,23;13,21;23;21
11,23;13,21;22;22
11,23;11,23;12;22
21,23;13;22;23
12,23;23;12;23;11,21
22,23;13;23;23;11
22,23;13;22;23;11,21
22,23;12;23;12,23;0
22,23;12;23;11,23;11
13,22;23;23;12;22
13,22;22;23;21,23;11
13,22;22;23;12,23;0
13,22;22;23;11,23;11
12,22;23;13,21;23;21
11,23;21,23;13;23;21
11,23;21,23;13;22;22
11,23;13,21;23;23;11
13,21;23;23;12;23
12,23;23;12;23;21,23;11
12,23;23;12;23;12,23;0
22,23;13;23;23;12;22
22,23;13;22;23;12,23;0
22,23;13;22;23;11,23;11
22,23;12;23;13,21;23;21
13,22;23;23;12;23;11,21
12,22;23;21,23;13;23;21
12,22;23;13,21;23;23;11
11,23;21,23;13;23;23;11
11,23;13,21;23;23;12;22
21,23;13;23;23;12;23
22,23;13;23;23;12;23;11,21
22,23;12;23;13,21;23;23;11
13,22;23;23;12;23;21,23;11
13,22;23;23;12;23;12,23;0
12,22;23;21,23;13;23;23;11
11,23;21,23;13;23;23;12;22
22,23;13;23;23;12;23;12,23;0
11,22
23
12,23;21
22,23;11
12,22;22
11,23;11,21
12,21;23
12,23;23;11
22,23;12;22
13,22;23;21
13,22;22;22
12,22;23;11,21
11,23;21,23;11
11,23;12,23;0
11,23;11,23;11
11,23;12,21;22
21,23;12;23
13,21;22;23
11,23;12;23
12,23;23;12;22
22,23;13;23;21
22,23;13;22;22
22,23;12;23;11,21
13,22;23;23;11
13,22;22;23;11,21
12,22;23;21,23;11
12,22;23;12,23;0
12,22;23;11,23;11
11,23;21,23;12;22
11,23;13,21;23;21
11,23;13,21;22;22
11,23;11,23;12;22
21,23;13;22;23
12,23;23;12;23;11,21
22,23;13;23;23;11
22,23;13;22;23;11,21
22,23;12;23;12,23;0
22,23;12;23;11,23;11
13,22;23;23;12;22
13,22;22;23;21,23;11
13,22;22;23;12,23;0
13,22;22;23;11,23;11
12,22;23;13,21;23;21
11,23;21,23;13;23;21
11,23;21,23;13;22;22
11,23;13,21;23;23;11
13,21;23;23;12;23
12,23;23;12;23;21,23;11
12,23;23;12;23;12,23;0
22,23;13;23;23;12;22
22,23;13;22;23;12,23;0
22,23;13;22;23;11,23;11
22,23;12;23;13,21;23;21
13,22;23;23;12;23;11,21
12,22;23;21,23;13;23;21
12,22;23;13,21;23;23;11
11,23;21,23;13;23;23;11
11,23;13,21;23;23;12;22
21,23;13;23;23;12;23
22,23;13;23;23;12;23;11,21
22,23;12;23;13,21;23;23;11
13,22;23;23;12;23;21,23;11
13,22;23;23;12;23;12,23;0
12,22;23;21,23;13;23;23;11
11,23;21,23;13;23;23;12;22
22,23;13;23;23;12;23;12,23;0



#El circuito mas largo g = sg2 L, circuito = max((len(ls), ls) for ls in g.all_simple_cycles()) subgrafo = g.subgraph(edges = [(circuito[j],circuito[j+1]) for j in range(len(circuito)-1)]) graphviz(subgrafo) 
       
 
       

Créditos

Esta presentación usa el programa Sage para hacer los cálculos sobre grafos y la librería graphviz para dibujar los grafos.

Muchas gracias a Daniel Sánchez, y a Nicolas M. Thiéry y Florent Hivert por sus comentarios (y a Clara, por supuesto).

Licencia

Este documento se distribuye con una licencia GFDL, ó cc-by-sa, a tu elección.

Licencia Creative Commons
Malabares y teoría de grafos por Pablo Angulo se encuentra bajo una Licencia Creative Commons Reconocimiento-CompartirIgual 3.0 Unported.