notebook.community

Edit and run



In [1]:

    
from havel_hakimi import Sucesion



In [2]:

    
a = Sucesion([4,4,3,2,2,2,1])



In [3]:

    
a.demolicion(True)









    



[4, 4, 3, 2, 2, 2, 1]
[0, 3, 2, 1, 1, 2, 1]
[0, 0, 1, 0, 1, 1, 1]
[0, 0, 0, 0, 1, 0, 1]
[0, 0, 0, 0, 0, 0, 0]



In [4]:

    
a.reconstruccion()



In [5]:

    
a.es_grafica()









    Out[5]:





True



In [6]:

    
b = Sucesion([6,6,6,4,3,3,2])



In [7]:

    
b.es_grafica()









    Out[7]:





False



In [8]:

    
b.demolicion(True)









    



[0, -1, -1, 0, 0, 0, 0]



In [9]:

    
c = Sucesion([7,5,5,4,2,3,3,3,3,2,2])



In [10]:

    
c.es_grafica()









    Out[10]:





False



In [11]:

    
c.demolicion(True)









    



[7, 5, 5, 4, 2, 3, 3, 3, 3, 2, 2]
[0, 4, 4, 3, 1, 2, 2, 2, 3, 2, 2]
[0, 0, 3, 2, 1, 1, 2, 2, 2, 2, 2]
[0, 0, 0, 1, 1, 1, 1, 2, 1, 2, 2]
[0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1]
[0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0]

Si intentamos dibujarla sin ser sucesión gráfica nos da un error



In [12]:

    
c.reconstruccion()









    



---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
<ipython-input-12-3adaaf0a935b> in <module>()
----> 1 c.reconstruccion()

/home/yabir/ugr/lmd/havel_hakimi.py in reconstruccion(self)
    100             self.__dibuja()
    101         else:
--> 102             raise Exception("No es sucesión grafica")
    103 
    104         return None

Exception: No es sucesión grafica



In [13]:

    
c.relaciones()









    Out[13]:





defaultdict(list,
            {1: [2, 3, 4, 5, 6, 7, 8],
             2: [3, 4, 9, 6],
             3: [4, 9, 7],
             4: [9],
             5: [7],
             7: [6],
             8: [10, 11],
             10: [11]})



In [14]:

    
Sucesion([7,5,5,4,3,3,3,3,3,2,2]).reconstruccion()



In [15]:

    
c = Sucesion([4,3,2,2,1,1,1])



In [16]:

    
c.es_grafica()









    Out[16]:





True



In [17]:

    
c.relaciones()









    Out[17]:





defaultdict(list, {1: [2, 3, 4, 5], 2: [3, 4], 6: [7]})



In [18]:

    
c.reconstruccion()

Árboles



In [19]:

    
from prufer import Prufer

Podemos tanto dato un código construir el árbol



In [20]:

    
p = Prufer( (4,4,3,1,7) )



In [21]:

    
p.construir()



In [22]:

    
p1 = Prufer( (5,5,1,3,3) )



In [23]:

    
p1.construir()

Como dado el árbol en forma de diccionario obtener su código



In [24]:

    
p2 = Prufer({5:[4,2], 1:[5,3], 3:[6,7]})



In [25]:

    
p2.codigo()









    Out[25]:





[5, 5, 1, 3, 3]



In [26]:

    
p3 = Prufer( {4:[5,2], 3:[4], 1:[3], 7:[1], 6:[7]} )



In [27]:

    
p3.codigo()









    Out[27]:





[4, 4, 3, 1, 7]

El algoritmo de Kruskal nos permite encontrar un árbol recubridor mínimo en un grafo conexo y ponderado.

Le podemos dar un grafo ponderado de la siguiente forma:

Una tupla de tuplas, cada tupla lleva como primera componente las letras de los nodos y la segunda componente es el valor del lado que los une.



In [28]:

    
a = (("AD",5), ("CE",5), ("DF", 6), ("AB",7), ("BE", 7), ("BC", 8),  ("EF", 8), ("DB", 9), ("EG",9), ("FG", 11),("DE", 15))



In [29]:

    
def Kruskal(grafo):
    
    final = {}
    
    def tiene_ciclos(lado):
        v1, v2 = lado[0], lado[1]
        dict.fromkeys(final, False)
        return ciclo_entre(v1, v2, dict(final))
    
    def ciclo_entre(v1, v2, lados):
        adyacentes = {k:v for (k,v) in lados.items() if v1 in k }
        if len(adyacentes) == 0:
            return False
        
        #No explorados
        validos = [k for (k,v) in adyacentes.items() if v == False]

        
        if len(validos) == 0:
            return False
        
        for lado in sorted(validos):
            lados[lado] = True
            if lado[0] == v1:
                otro_nodo = lado[1]
            else:
                otro_nodo = lado[0]

            if otro_nodo == v2 or ciclo_entre(otro_nodo, v2, lados):
                    return True 
    
    grafo_sorted = sorted(grafo, key = lambda t: t[1])
    
    
    for lado in grafo_sorted:
        vertices = lado[0]
        if not tiene_ciclos(vertices):
            final[vertices] = False
    return sorted([x for x in a if x[0] in final], key=lambda t: t[1])



In [30]:

    
Kruskal(a)









    Out[30]:





[('AD', 5), ('CE', 5), ('DF', 6), ('AB', 7), ('BE', 7), ('EG', 9)]