Considere um quadrado, ABCD. Intuitivamente, pareceu-me que seu polinômio cromático é onde existem cores disponíveis.λ(λ−1)(λ−1)(λ−2)λ(λ−1)(λ−1)(λ−2)\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2)λλ\lambda Ou seja, existem maneiras pelas quais uma cor para A pode ser escolhida, existem maneiras de...
Eu queria saber se este problema tem um nome: Dado um gráfico simples cujas bordas são de cor vermelha, azul e verde, , existe um-coloração vértice c : V → { B , R , G } de tal modo que cada extremidade tem um ponto de extremidade com a mesma cor?G = ( V, B ∪ R ∪ G )G=(V,B∪R∪G)G=(V,B\cup R\cup G)c...
Para provar que a 3 cores é decidível, basta dizer: Cada nó no gráfico possui 3 cores possíveis Portanto, podemos enumerar todas as possibilidades de e verificar se não há duas arestas conectando nós da mesma cor3n3n3^n Isso prova que a 3 cores é decidível? Ou preciso construir uma máquina de...
Eu tenho algumas dificuldades em entender o algoritmo distribuído para a árvore 6 - colorir no tempo .O(log∗n)O(log∗n)O(\log^*n) A descrição completa pode ser encontrada no seguinte artigo: Quebra de simetria paralela em gráficos esparsos. Goldberg, Plotkin, Shannon . Em suma, a ideia é ... A...
Eu estava lendo o teorema das quatro cores e me pergunto se existe alguma aplicação prática dele. (Não acho que separar o mapa em quatro cores diferentes possa ser considerado um aplicativo.) Eu tentei pesquisar no Google por aplicativos, mas não consegui encontrar