Havel-Hakimi
El código está en catalán pero es autoexplicativo.
def comprova(nodes):
if sum(nodes) % 2 != 0:
print 'la suma se graus no es parell'
return 0
if max(nodes) > len(nodes)-1:
print 'hi ha un node de grau mes gran que el total de nodes'
return 0
if min(nodes) < 0:
print 'hi ha un node de grau negatiu'
return 0
if max(nodes) == 0:
print 'es un graf correcte'
return 0
return 1
# mostra de Butà un hidrocarbó amb fórmula C4H10
nodes = [4,4,4,4,1,1,1,1,1,1,1,1,1,1]
# mostra d'una definició de graf incorrecte
# nodes = [6,5,5,5,5,2,1,1]
while (comprova(nodes)):
print nodes
nodes2 = list(nodes)
nodes.sort()
nodes.reverse()
if nodes!=nodes2: print str(nodes) + " ordenat"
node = nodes.pop(0)
for i in range(node):
nodes[i]=nodes[i]-1
print nodes
def comprova(nodes):
if sum(nodes) % 2 != 0:
print ‘la suma se graus no es parell’
return 0
if max(nodes) > len(nodes)-1:
print ‘hi ha un node de grau mes gran que el total de nodes’
return 0
if min(nodes) < 0:
print ‘hi ha un node de grau negatiu’
return 0
if max(nodes) == 0:
print ‘es un graf correcte’
return 0
return 1
if sum(nodes) % 2 != 0:
print ‘la suma se graus no es parell’
return 0
if max(nodes) > len(nodes)-1:
print ‘hi ha un node de grau mes gran que el total de nodes’
return 0
if min(nodes) < 0:
print ‘hi ha un node de grau negatiu’
return 0
if max(nodes) == 0:
print ‘es un graf correcte’
return 0
return 1
nodes = [7,5,4,3,2,2,2]
nodes = [7,6,5,4,4,3,2,1]
nodes = [5,5,3,2,2,1,1]
nodes = [4,3,2,2,2,2,1]
nodes = [6,5,5,5,5,2,1,1]
nodes = [4,4,4,4,1,1,1,1,1,1,1,1,1,1]
while (comprova(nodes)):
print nodes
nodes2 = list(nodes)
nodes.sort()
nodes.reverse()
if nodes!=nodes2: print str(nodes) + ” ordenat”
node = nodes.pop(0)
for i in range(node):
nodes[i]=nodes[i]-1
print nodes
2010 04 15
Oh! Havel-Hakimi!!! Ni me’n recordava!!! De fet, ja ni me’n recordo xD Molt gran Josep!