Algoritmos para Grafos | Índice
Muitos grafos não-dirigidos são naturalmente
bipartidos
:
imagine, por exemplo,
que alguns vértices representam pessoas à procura de emprego,
outros representam empresas que oferecem empregos,
e as arestas indicam que há compatibilidade
entre um vértice do primeiro tipo e um do segundo.
Sumário:
Uma bipartição,
ou bicoloração,
de um grafo não-dirigido é uma coloração válida do grafo com duas cores.
(Eu poderia dizer bicoloração válida
,
mas é melhor deixar o válida
subentendido.)
Portanto,
uma bicoloração
é uma atribuição de uma de duas cores —
preto e vermelho, por exemplo —
a cada vértice do grafo
de tal modo que as duas pontas de cada aresta tenham cores diferentes.
Um grafo não-dirigido é bipartido, ou bicolorido, se admite uma bicoloração. (Não confunda esse conceito com o conceito bem mais simples de grafo bipartido dirigido!)
Problema da bipartição: Decidir se um dado grafo não-dirigido é bipartido.
Eis uma pequena aplicação: Uma indústria química tem dois galpões para armazenar seu estoque de reagentes. Por segurança, certos pares de reagentes devem ficar separados. É possível distribuir os reagentes pelos dois galpões de modo a separar os que são incompatíveis?
O seguinte algoritmo recursivo A
decide se um grafo não-dirigido conexo G
admite bicoloração.
O algoritmo é bastante ingênuo.
Ele supõe dada uma bicoloração incompleta de G,
que pode ser vazia.
O algoritmo
recebe um vértice incolor v e uma cor c
e decide — sim
ou não
—
se existe uma bicoloração (completa) de G
que estende a bicoloração incompleta
e atribui cor c a v:
não
nãopara algum vizinho incolor w de v
não
sim
A seguinte função implementa o algoritmo para qualquer grafo não-dirigido, conexo ou não. A função tenta produzir uma bicoloração dos vértices fazendo uma busca em profundidade. Ela só fracassa se o grafo não tem bicoloração alguma.
#define UGraph Graph int color[1000];
/* A função decide se o grafo não-dirigido G admite bipartição. Em caso afirmativo, a função atribui uma cor, 0 ou 1, a cada vértice de G de tal forma que toda aresta tenha pontas de cores diferentes. As cores dos vértices são armazenadas no vetor color[] indexado pelos vértices. (Esta função supõe que G é representado por listas de adjacência. Código inspirado no programa 18.6 de Sedgewick.) */
bool UGRAPHtwoColor( UGraph G) { for (vertex v = 0; v < G->V; ++v) color[v] = -1; // incolor for (vertex v = 0; v < G->V; ++v) if (color[v] == -1) // começa nova etapa if (dfsRtwoColor( G, v, 0) == false) return false; return true; }
/* Decide se existe uma bicoloração de G que atribui cor c ao vértice v e estende a bicoloração incompleta color[] à componente conexa de G que contém v. */
static bool dfsRtwoColor( UGraph G, vertex v, int c) { color[v] = c; for (link a = G->adj[v]; a != NULL; a = a->next) { vertex w = a->w; if (color[w] == -1) { if (dfsRtwoColor( G, w, 1-c) == false) return false; } else { // v-w é de avanço ou de retorno if (color[w] == c) // base da recursão return false; } } return true; }
Se a função devolve true, é fácil entender que color[] representa uma bicoloração e portanto G é bipartido. Resta mostrar que se a função devolve false então G não admite bicoloração alguma. Faremos isso na próxima seção.
Exemplo A. Aplique a função GRAPHtwoColor() ao grafo da figura. Suponha que as listas de adjacência de todos os vértices estão em ordem crescente. Veja o rastreamento da execução da função.
0 dfsRtwoColor(0) cor 0 0-1 dfsRtwoColor(1) cor 1 1-0 1 return true 0-2 dfsRtwoColor(2) cor 1 2-0 2 return true 0-5 dfsRtwoColor(5) cor 1 5-0 5-3 dfsRtwoColor(3) cor 0 3-4 dfsRtwoColor(4) cor 1 4-3 4-5 return false 3-4 return false 5-3 return false 0-5 return false
Veja o estado final do vetor color[]:
v 0 1 2 3 4 5 6 color[v] 0 1 1 0 1 1 -
Exemplo B. Aplique a função GRAPHtwoColor() ao grafo definido pelas listas de adjacência abaixo. (Imagine que os vértices da figura estão numerados no sentido horário a partir do nordeste.)
0: 1 3 5 1: 0 2 4 2: 1 3 5 3: 0 2 4 4: 1 3 5 5: 0 2 4
Veja o rastreamento da execução da função.
0 dfsRtwoColor(0) cor 0 0-1 dfsRtwoColor(1) cor 1 1-0 1-2 dfsRtwoColor(2) cor 0 2-1 2-3 dfsRtwoColor(3) cor 1 3-0 3-2 3-4 dfsRtwoColor(4) cor 0 4-1 4-3 4-5 dfsRtwoColor(5) cor 1 5-0 5-2 5-4 5 return true 4 return true 3 return true 2-5 2 return true 1-4 1 return true 0-3 0-5 0 return true
Veja o estado final do vetor color[]:
v 0 1 2 3 4 5 color[v] 0 1 0 1 0 1
Desempenho. Quando aplicada a um grafo não-dirigido com V vértices e E arestas, a função UGRAPHtwoColor() consome tempo proporcional a V + E no pior caso. (Se o grafo é conexo, como acontece em muitas aplicações, podemos dizer que o consumo de tempo é proporcional a E.) O algoritmo é, portanto, linear.
Um circuito num grafo não-dirigido é ímpar (= odd) se seu comprimento for um número ímpar. Se um grafo tem um circuito ímpar, então é óbvio que não admite bipartição. A recíproca é menos óbvia, como veremos a seguir.
Suponha que um grafo não-dirigido G não admite bipartição.
Então a função UGRAPHtwoColor() acima
devolve false
quando recebe G.
Portanto, dois vértices v e w de G
têm a mesma cor em alguma execução da linha
if (color[w] == c)
do código.
Observe que
o arco v-w é de avanço ou de retorno,
uma vez que o grafo é não-dirigido.
Suponha, primeiramente,
que v-w é de retorno.
Seja w-x-y-...-u-v o
caminho de w a v na floresta DFS.
O comprimento do caminho é par,
uma vez que v e w têm a mesma cor
e as cores dos vértices se alternam
ao longo do caminho.
Portanto, w-x-y-...-u-v-w
é um circuito ímpar.
Suponha agora que v-w é de avanço.
Então um raciocínio análogo ao anterior
mostra que o arco w-v
pertence a um circuito ímpar.
Conclusão: Se a função G não tem uma bicoloração
então o grafo tem um circuito ímpar.
Essa discussão pode ser resumida no seguinte
Teorema: Um grafo não-dirigido é bipartido se e somente se não tem circuito ímpar.
O que é um grafo bipartido? Um grafo bipartido é um grafo sem circuitos ímpares.
Este grafo tem um circuito de comprimento 101. Podemos dizer então, com base em um teorema bem conhecido, que o grafo não é bicolorido.
Este capítulo traz mais uma caracterização demonstrada por um algoritmo. Eis as duas caracterizações desse tipo vistas até aqui:
A primeira caracterização foi demonstrada pela função GRAPHcycle0() no capítulo Ciclos e dags. A segunda é demonstrada pela função UGRAPHtwoColor() acima.
bicromáticono lugar de
bicoloridoe
bicolorível?
Resposta: Parece muito razoável. Mas a tradição da teoria dos grafos reserva o adjetivo bicromático a grafos que têm uma bicoloração mas não têm uma coloração com apenas uma cor (ou seja, têm pelo menos uma aresta).