Coloração de gráfico
A coloração de gráficos pode ser descrita como um processo de atribuição de cores aos vértices de um gráfico. Neste, a mesma cor não deve ser utilizada para preencher os dois vértices adjacentes. Também podemos chamar a coloração de gráficos como Vertex Coloring. Na coloração de grafos, temos que tomar cuidado para que um grafo não contenha nenhuma aresta cujos vértices finais sejam coloridos pela mesma cor. Este tipo de gráfico é conhecido como gráfico com cores adequadas.
Exemplo de coloração de gráfico
classificar um array em java
Neste gráfico, estamos mostrando o gráfico colorido corretamente, que é descrito a seguir:
O gráfico acima contém alguns pontos, que são descritos a seguir:
- A mesma cor não pode ser usada para colorir os dois vértices adjacentes.
- Portanto, podemos chamá-lo de um gráfico colorido adequadamente.
Aplicações de coloração de gráficos
Existem várias aplicações de coloração de gráficos. Algumas de suas aplicações importantes são descritas a seguir:
- Atribuição
- Coloração do mapa
- Agendando as tarefas
- Sudoku
- Preparar cronograma
- Resolução de conflitos
Número Cromático
O número cromático pode ser descrito como o número mínimo de cores necessárias para colorir adequadamente qualquer gráfico. Em outras palavras, o número cromático pode ser descrito como um número mínimo de cores necessárias para colorir qualquer gráfico de tal forma que dois vértices adjacentes de um gráfico não recebam a mesma cor.
Exemplo de número cromático:
Para entender o número cromático, consideraremos um gráfico, que é descrito a seguir:
O gráfico acima contém alguns pontos, que são descritos a seguir:
- A mesma cor não é usada para colorir os dois vértices adjacentes.
- O número mínimo de cores deste gráfico é 3, necessário para colorir adequadamente os vértices.
- Portanto, neste gráfico, o número cromático = 3
- Se quisermos colorir adequadamente este gráfico, neste caso, serão necessárias pelo menos 3 cores.
Tipos de número cromático de gráficos:
Existem vários tipos de número cromático de gráficos, que são descritos a seguir:
Gráfico de ciclo:
Um gráfico será conhecido como gráfico de ciclo se contiver 'n' arestas e 'n' vértices (n >= 3), que formam um ciclo de comprimento 'n'. Pode haver apenas 2 ou 3 números de graus de todos os vértices no gráfico de ciclo.
Número cromático:
- O número cromático em um gráfico de ciclo será 2 se o número de vértices nesse gráfico for par.
- O número cromático em um gráfico de ciclo será 3 se o número de vértices nesse gráfico for ímpar.
Exemplos de gráfico de ciclo:
Existem vários exemplos de gráficos de ciclo. Alguns deles são descritos a seguir:
Exemplo 1: No gráfico a seguir, temos que determinar o número cromático.
Solução: No gráfico de ciclo acima, existem 3 cores diferentes para três vértices e nenhum dos vértices adjacentes é colorido com a mesma cor. Neste gráfico, o número de vértices é ímpar. Então
Número cromático = 3
Exemplo 2: No gráfico a seguir, temos que determinar o número cromático.
Solução: No gráfico de ciclo acima, existem 2 cores para quatro vértices e nenhum dos vértices adjacentes é colorido com a mesma cor. Neste gráfico, o número de vértices é par. Então
Número cromático = 2
Exemplo 3: No gráfico a seguir, temos que determinar o número cromático.
Solução: No gráfico acima, existem 4 cores diferentes para cinco vértices, e dois vértices adjacentes são coloridos com a mesma cor (azul). Portanto, este gráfico não é um gráfico de ciclo e não contém um número cromático.
Exemplo 4: No gráfico a seguir, temos que determinar o número cromático.
Solução: No gráfico acima, existem 2 cores diferentes para seis vértices e nenhum dos vértices adjacentes é colorido com a mesma cor. Neste gráfico, o número de vértices é par. Então
Número cromático = 2
Gráfico do planejador
Um gráfico será conhecido como gráfico planejador se for desenhado em um plano. As bordas do gráfico do planejador não devem se cruzar.
Número Cromático:
- Em um gráfico planejador, o número cromático deve ser menor ou igual a 4.
- O gráfico do planejador também pode ser mostrado por todos os gráficos de ciclo acima, exceto o exemplo 3.
Exemplos de gráfico Planer:
Existem vários exemplos de gráficos planos. Alguns deles são descritos a seguir:
Exemplo 1: No gráfico a seguir, temos que determinar o número cromático.
Solução: No gráfico acima, existem 3 cores diferentes para três vértices, e nenhuma das arestas deste gráfico se cruza. Então
Powershell de comentário multilinha
Número cromático = 3
Aqui, o número cromático é menor que 4, então este gráfico é um gráfico plano.
Exemplo 2: No gráfico a seguir, temos que determinar o número cromático.
Solução: No gráfico acima, existem 2 cores diferentes para quatro vértices e nenhuma das arestas deste gráfico se cruza. Então
Número cromático = 2
Aqui, o número cromático é menor que 4, então este gráfico é um gráfico plano.
Exemplo 3: No gráfico a seguir, temos que determinar o número cromático.
Solução: No gráfico acima, existem 5 cores diferentes para cinco vértices, e nenhuma das arestas deste gráfico se cruza. Então
Número cromático = 5
Aqui, o número cromático é maior que 4, portanto este gráfico não é um gráfico plano.
Exemplo 4: No gráfico a seguir, temos que determinar o número cromático.
Solução: No gráfico acima, existem 2 cores diferentes para seis vértices, e nenhuma das arestas deste gráfico se cruza. Então
Número cromático = 2
Aqui, o número cromático é menor que 4, então este gráfico é um gráfico plano.
Gráfico Completo
Um grafo será conhecido como grafo completo se apenas uma aresta for usada para unir cada dois vértices distintos. Cada vértice em um gráfico completo está conectado a todos os outros vértices. Neste gráfico, cada vértice será colorido com uma cor diferente. Isso significa que no gráfico completo, dois vértices não contêm a mesma cor.
Número Cromático
Em um gráfico completo, o número cromático será igual ao número de vértices desse gráfico.
Exemplos de gráfico completo:
Existem vários exemplos de gráficos completos. Alguns deles são descritos a seguir:
Exemplo 1: No gráfico a seguir, temos que determinar o número cromático.
Solução: Existem 4 cores diferentes para 4 vértices diferentes e nenhuma das cores é igual no gráfico acima. De acordo com a definição, um número cromático é o número de vértices. Então,
substituir da string em java
Número cromático = 4
Exemplo 2: No gráfico a seguir, temos que determinar o número cromático.
Solução: Existem 5 cores diferentes para 5 vértices diferentes e nenhuma das cores é igual no gráfico acima. De acordo com a definição, um número cromático é o número de vértices. Então,
Número cromático = 5
Exemplo 3: No gráfico a seguir, temos que determinar o número cromático.
Solução: Existem 3 cores diferentes para 4 vértices diferentes e uma cor é repetida em dois vértices no gráfico acima. Portanto, este gráfico não é um gráfico completo e não contém um número cromático.
Gráfico Bipartido
Um grafo será conhecido como grafo bipartido se contiver dois conjuntos de vértices, A e B. O vértice de A só pode unir-se aos vértices de B. Isso significa que as arestas não podem unir os vértices a um conjunto.
Número Cromático
Em qualquer grafo bipartido, o número cromático é sempre igual a 2.
Exemplos de gráfico bipartido:
Existem vários exemplos de gráficos bipartidos. Alguns deles são descritos a seguir:
Exemplo 1: No gráfico a seguir, temos que determinar o número cromático.
Solução: Existem 2 conjuntos diferentes de vértices no gráfico acima. Portanto, o número cromático de todos os gráficos bipartidos será sempre 2. Então
Número cromático = 2
Árvore:
Um grafo conectado será conhecido como árvore se não houver circuitos nesse grafo. Em uma árvore, o número cromático será igual a 2, não importa quantos vértices existam na árvore. Todo grafo bipartido também é uma árvore.
Número Cromático
Em qualquer árvore, o número cromático é igual a 2.
código de amostra java
Exemplos de árvore:
Existem vários exemplos de árvore. Alguns deles são descritos a seguir:
Exemplo 1: Na árvore a seguir, temos que determinar o número cromático.
Solução: Existem 2 cores diferentes para quatro vértices. Uma árvore com qualquer número de vértices deve conter o número cromático 2 na árvore acima. Então,
Número cromático = 2
Exemplo 2: Na árvore a seguir, temos que determinar o número cromático.
Solução: Existem 2 cores diferentes para cinco vértices. Uma árvore com qualquer número de vértices deve conter o número cromático 2 na árvore acima. Então,
Número cromático = 2
Exemplo da vida real de número cromático
Suponha que Marry seja gerente da Xyz Company. A empresa contrata alguns novos funcionários e ela precisa definir um cronograma de treinamento para esses novos funcionários. Ela tem que agendar as três reuniões e está tentando aproveitar ao máximo os poucos horários possíveis para as reuniões. Se houver um funcionário que precise estar em duas reuniões diferentes, o gerente precisará usar horários diferentes para essas reuniões. Suponha que queiramos obter uma representação visual desta reunião.
Para a representação visual, Marry utiliza o ponto para indicar o encontro. Se houver um funcionário que tem duas reuniões e precisa ingressar em ambas as reuniões, ambas as reuniões serão conectadas com a ajuda de um edge. Os diferentes intervalos de tempo são representados com a ajuda de cores. Assim o gerente preenche os pontos com essas cores de forma que dois pontos não contenham a mesma cor que compartilha uma borda. (Isso significa que um funcionário que precisa comparecer às duas reuniões não deve ter o mesmo horário). A representação visual disso é descrita a seguir:
