| Algoritmos em Grafos | Livros | WWW | Índice de Termos |
|
|
Bicoloração de vértices
Quando só dispomos de duas cores, o problema da coloração de vértices de um grafo não-dirigido é simples. O algoritmo que resolve a bicoloração é útil e importante.
Um grafo não-dirigido é bicromático (ou bipartido) se admite uma coloração dos vértices com não mais que 2 cores. (Grafos bicormáticos são usualmente desenhados de modo que os vértices de uma das cores fiquem alinhados na parte superior da figura e os da outra cor fiquem alinhados na parte inferior da figura.)
É fácil provar que um grafo é bicromático: basta exibir uma bicoloração dos vértices! Mas como é possível provar que um grafo não é bicromático? É óbvio que um grafo dotado de ciclo de comprimento ímpar (1,3,5, etc.) não é bicromático. É menos óbvio (mas não menos verdade) que a vale a recíproca. Resumindo:
Teorema: Um grafo é bicromático se e somente se não tem ciclo de comprimento ímpar.Portanto, para provar que um dado grafo não é bicromático, basta exibir um ciclo ímpar no grafo.
Exercícios
[Importante] Escreva uma função C que receba um grafo não-dirigido e devolva 1 se o grafo é bicromático e 0 em caso contrário. Além disso, no primeiro caso, a função deve marcar cada vértice com uma de duas cores.
[Continuação] Faça uma versão mais completa do exercício anterior: se o grafo não é bicromático então a função deixa marcado um ciclo ímpar z, z–>próx, z–>próx–>próx, . . . , z.
Exercícios
[Desafio] Escreva uma função C que pinte os vértices de um grafo dado com 3 cores ou menos ou diga que o grafo não admite tal coloração.