4

Gostaria de saber se é possível utilizar a técnica de coloração em grafos direcionados? Se sim ou não, porque?

1 Resposta 1

2

Sim, mas note que se existe uma aresta A → B, então A e B têm que ter cores diferentes, pois, caso contrário, A teria um vizinho (B) com a mesma cor. O mesmo raciocínio vale, mas ao contrário, se a aresta for B → A. Colorir um grafo dirigido não é diferente de colorir um grafo não-dirigido; por isso que ninguém distingue os dois casos.


Isso é diferente do que acontece e.g. no problema de achar a árvore geradora mínima: considere o grafo abaixo.

grafo A → B (peso 1), B → C (peso 2), C → A (peso 3)

Se o grafo não fosse dirigido, a menor árvore geradora mínima (no sentido se ser o subgrafo de peso mínimo onde sempre existe um caminho entre quaisquer dois vértices) seria obviamente composto das arestas A – B e B – C.

Dado que é o grafo é dirigido, no entanto, esse subgrafo de peso mínimo é a arborescência geradora mínima, que, no caso, tem que ter as três arestas A → B, B → C, C → A; para esse outro problema, o grafo ser dirigido ou não faz, sim, diferença.

4
  • Entendi, a minha pergunta foi justamente porque ninguém distingue os dois casos, obrigado! Commented 5/06/2015 às 13:26
  • mas e a coloração de vertices e faces, também é possivel? Commented 5/06/2015 às 14:03
  • Colorir faces é equivalente a colorir os vértices do grafo dual (e aí vale novamente a resposta acima).
    – user25930
    Commented 5/06/2015 às 14:06
  • "Arborescência"? Commented 23/11/2017 às 3:34

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .