Coloração Equilibrada de Arestas

Afonso Henrique SampaioHenrique ChevreuxThiago Fioravante

Apresentação do problema• Dada uma coloração própria, pretende-se obter

uma coloração com distribuição mais equilibrada entre as cores utilizadas(ie, busca-se equilibrar a quantidade de elementos em cada matching)

• Aplicações: o Alocação de professores a turmas buscando minimizar

o número de períodos requeridos para ministrar todas aulas necessárias

o Alocação de canais de comunicação em redes sem fio

Entrada• Entrada consiste em um grafo propriamente

colorido(potencialmente não-equilibrado)

Saída• Saída é o grafo de entrada com coloração própria e

equilibrada

Definindo equilíbrio• Dada uma k-coloração própria, é sempre possível

obter outra k-coloração própria que usa cada cor no mínimo piso(|E|/k) e no máximo teto(|E|/k)

• Portanto, a diferença entre a quantidade de vezes que cada cor é utilizada(no equilíbrio) é no máximo 1 - ou então 0 quando piso(|E|/k) = teto(|E|/k). 

• No exemplo anterior:o |E| = 18o  k = 7o piso(|E|/k) = piso(18/7) = 2o teto(|E|/k) = teto(18/7) = 3

Não-equilibrada• |Laranja| = 1; |Azul-escuro| = 2; |Verde-claro| = 3; |Verde-

escuro| = 3; |Vermelho| = 3; |Rosa| = 3; |Azul-claro| = 3; 

Equilibrada• |Laranja| = 2; |Azul-escuro| = 2; |Verde-claro| = 3; |Verde-

escuro| = 3; |Vermelho| = 3; |Rosa| = 3; |Azul-claro| = 2; 

Implementação• Estruturas de dados implementadas

o Grafo armazenado em matriz de adjacências ponderada(o peso é a cor atual da aresta)

o Cada matching é uma lista de arestaso Para cada vértice há uma lista das cores representadas

naquele vértice

|V| = 10; |E|=40; k=10; limites=[4, 4]

antes da troca: |roxo| = 1; |verde-claro| = 5

depois da troca: |roxo| = 2; |verde-claro| = 4

antes da troca: |roxo| = 2; |verde-escuro| = 5

depois da troca: |roxo| = 3; |verde-escuro| = 4

antes da troca: |roxo| = 3; |laranja| = 5

caminhos de Kempe para cores laranja e roxo

construindo caminho de Kempe(começa com (1, 4))

insere aresta (4, 2) no caminho

insere aresta (2, 7) no caminho

insere aresta (1, 9) no outro extremo do caminho

insere aresta (9, 8) no caminho

inverte as cores no caminho de Kempe

coloração equilibrada, após todas as trocas

grafo original

Próximos passos• Testar o programa para instâncias maiores

• Avaliar estratégias ou estruturas mais eficientes

• Comparar execução para estratégias diferentes de implementação(cada uma utilizando uma estrutura em particular)