Jump to content

Numero Cromatico de um grafo


mundo
 Share

Recommended Posts

Boa noite, estou a tentar resolver um exercicio cujo enunciado é:

"O objectivo deste programa é determinar o número cromático de um grafo, ou seja, o menor número de cores necessário para colorir um grafo de tal forma que nodos adjacentes tenham cores distintas. Irá receber uma lista de pares de nodos que são adjacentes entre si e deverá imprimir o número cromático do grafo."

Como exemplo de input temos:

portugal espanha

espanha franca

franca alemanha

alemanha belgica

belgica franca

usa canada

usa mexico

marrocos argelia

argelia libia

argelia mali

e o output deveria ser 2 para este caso.

Eu fiz o seguinte código:

import sys

# Funcao para preencher o grafo
def arestaAB(grafo, origem, destino):
   if origem in grafo:
       grafo[origem].append(destino)
   else:
       grafo[origem] = [destino]

   if destino in grafo:
       grafo[destino].append(origem)
   else:
       grafo[destino] = [origem]


#Funcao que verifica se ha uma solucao, e vai preenchendo o sol com a solucao
def find(sol, i, k):

   #so ha um vertice por isso existe solucao
   if i == k:
       return True
   # caso contrario e necessario verificar o resto
   else:

       #para o numero de vertices vamos verificar se existe solucao
       for j in range(1,k):

           #adicionamos a solucao a lista
           sol[i] = j

           #continuamos de forma recursiva
           if find(sol, i+1, k):
               return True

   #Chegamos aqui nao ha solucao
   return False


grafo = {}

for line in sys.stdin:
   a,b = line.split()
   arestaAB(grafo,a,b)

#print grafo

sol = []
cores = len(grafo.keys())

for i in range(cores):
   if find(sol,i,cores) == True:
       print i

Isto está a dar IndexError na linha

sol[i] = j 

e não estou a perceber porquê, se alguém poder ajudar agradeço.

Cumprimentos

Edited by mundo
Link to comment
Share on other sites

É importante meteres o erro aqui para conseguirmos perceber melhor o que está a acontecer.

No teu caso em particular diria que é um erro de indexação. Como o "sol" está vazio (sol=[]) quando tentas aceder a uma posição (que não existe) ele dá problemas.

Link to comment
Share on other sites

devias inciiar a lista de sol [ ] com o tamanho de 'k' assim já não terias problemas de indexação. podes também alterar a linha 'sol = j' para sol.append(j) mas ao fazeres isto vais aumentar o tamanho final da lista porque enquanto 'i' estiver em range de 'cores' o teu algoritmo vai sempre adicionar elementos a lista (se bem percebi o código)

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.