Gostaria de saber se é possível utilizar a técnica de coloração em grafos direcionados? Se sim ou não, porque?
1 Resposta
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.
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.
-
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).– user25930Commented 5/06/2015 às 14:06
-