Matemática Discreta - Mais Sobre Gráficos

Coloração de Gráfico

A coloração do gráfico é o procedimento de atribuição de cores a cada vértice de um gráfico G de forma que nenhum vértice adjacente obtenha a mesma cor. O objetivo é minimizar o número de cores ao colorir um gráfico. O menor número de cores necessário para colorir um gráfico G é chamado de número cromático desse gráfico. O problema de coloração do gráfico é um problema NP Completo.

Método para colorir um gráfico

As etapas necessárias para colorir um gráfico G com n número de vértices são as seguintes -

Step 1 - Organize os vértices do gráfico em alguma ordem.

Step 2 - Escolha o primeiro vértice e pinte-o com a primeira cor.

Step 3- Escolha o próximo vértice e pinte-o com a cor de menor número que não foi colorida em nenhum vértice adjacente a ele. Se todos os vértices adjacentes forem coloridos com esta cor, atribua uma nova cor a ele. Repita esta etapa até que todos os vértices estejam coloridos.

Example

Na figura acima, no primeiro vértice $ a $ é colorido de vermelho. Como os vértices adjacentes do vértice a são novamente adjacentes, o vértice $ b $ e o vértice $ d $ são coloridos com cores diferentes, verde e azul respectivamente. Então, o vértice $ c $ é tão vermelho quanto nenhum vértice adjacente de $ c $ é colorido de vermelho. Portanto, poderíamos colorir o gráfico com 3 cores. Portanto, o número cromático do gráfico é 3.

Aplicações da coloração de grafos

Algumas aplicações de colorir gráficos incluem -

Registrar Alocação
Coloração do mapa
Verificação de gráfico bipartido
Atribuição de radiofrequência móvel
Fazendo cronograma, etc.

Gráfico Traversal

A travessia do gráfico é o problema de visitar todos os vértices de um gráfico em alguma ordem sistemática. Existem basicamente duas maneiras de percorrer um gráfico.

Largura da primeira pesquisa
Profundidade primeira pesquisa

Largura da primeira pesquisa

A primeira pesquisa de amplitude (BFS) começa no vértice de nível 0 $ X $ do gráfico $ G $. Em seguida, visitamos todos os vértices que são vizinhos de $ X $. Após a visita, marcamos os vértices como "visitados" e os colocamos no nível 1. Em seguida, começamos a partir dos vértices de nível 1 e aplicamos o mesmo método em todos os vértices de nível 1 e assim por diante. O percurso BFS termina quando todos os vértices do gráfico são visitados.

BFS Algorithm

O conceito é visitar todos os vértices vizinhos antes de visitar outros vértices vizinhos de vértices vizinhos.

Inicialize o status de todos os nós como “Pronto”.
Coloque o vértice de origem em uma fila e mude seu status para “Esperando”.
Repita as duas etapas a seguir até que a fila esteja vazia -
- Remova o primeiro vértice da fila e marque-o como “Visitado”.
- Adicione à parte traseira da fila todos os vizinhos do vértice removido cujo status é “Pronto”. Marque seu status como “Esperando”.

Problem

Vamos pegar um gráfico (o vértice de origem é 'a') e aplicar o algoritmo BFS para descobrir a ordem de travessia.

Solution -

Inicialize o status de todos os vértices para “Pronto”.
Coloque um na fila e mude seu status para “Esperando”.
Remova um da fila, marque-o como “Visitado”.
Adicionar um ‘s vizinhos em‘Ready’estado b, d e e até o fim da fila e marcá-los como‘espera’.
Remova b da fila, marque-o como “Visitado”, coloque seu vizinho “Pronto” c no final da fila e marque c como “Esperando”.
Remova d da fila e marque-o como “Visitados”. Não tem vizinho no estado “Pronto”.
Remova e da fila e marque-o como “Visitado”. Não tem vizinho no estado “Pronto”.
Remova c da fila e marque-o como “Visitado”. Não tem vizinho no estado “Pronto”.
A fila está vazia, então pare.

Portanto, a ordem de passagem é -

$ a \ rightarrow b \ rightarrow d \ rightarrow e \ rightarrow c $

As ordens alternativas de travessia são -

$ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $

Ou $ a \ rightarrow d \ rightarrow b \ rightarrow e \ rightarrow c $

Ou $ a \ rightarrow e \ rightarrow b \ rightarrow d \ rightarrow c $

Ou $ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $

Ou $ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $

Application of BFS

Encontrando o caminho mais curto
Árvore de abrangência mínima para gráfico não ponderado
Sistema de navegação GPS
Detectando ciclos em um gráfico não direcionado
Encontrar todos os nós em um componente conectado

Complexity Analysis

Seja $ G (V, E) $ um gráfico com $ | V | $ número de vértices e $ | E | $ número de arestas. Se o algoritmo de pesquisa em amplitude visitar todos os vértices do gráfico e verificar todas as arestas, então sua complexidade de tempo seria -

$$ O (| V | + | E |). O (| E |) $$

Pode variar entre $ O (1) $ e $ O (| V2 |) $

Profundidade primeira pesquisa

O algoritmo Depth First Search (DFS) começa a partir de um vértice $ v $, então atravessa seu vértice adjacente (digamos x) que não foi visitado antes e marca como "visitado" e continua com o vértice adjacente de $ x $ e em breve.

Se em qualquer vértice, ele encontra que todos os vértices adjacentes foram visitados, então ele retrocede até encontrar o primeiro vértice tendo um vértice adjacente que não foi percorrido antes. Então, ele atravessa aquele vértice, continua com seus vértices adjacentes até que ele atravessa todos os vértices visitados e tem que retroceder novamente. Desta forma, ele percorrerá todos os vértices alcançáveis do vértice inicial $ v $.

DFS Algorithm

O conceito é visitar todos os vértices vizinhos de um vértice vizinho antes de visitar os outros vértices vizinhos.

Inicializar o status de todos os nós como “Pronto”
Coloque o vértice de origem em uma pilha e mude seu status para "Esperando"
Repita as duas etapas a seguir até que a pilha esteja vazia -
- Destaque o vértice superior da pilha e marque-o como “Visitado”
- Empurre para o topo da pilha todos os vizinhos do vértice removido cujo status é “Pronto”. Marque seu status como “Esperando”.

Problem

Vamos pegar um gráfico (o vértice de origem é 'a') e aplicar o algoritmo DFS para descobrir a ordem de travessia.

Solution

Inicialize o status de todos os vértices para “Pronto”.
Coloque um na pilha e altere seu status para “Esperando”.
Abra um e marque-o como “Visitado”.
Empurre a vizinhos ‘s em‘Ready’estado e, d e b ao topo da pilha e marcá-los como‘espera’.
Retire b da pilha, marque-o como “Visitado” e empurre seu vizinho “Pronto” c para a pilha.
Retire c da pilha e marque-a como “Visitada”. Não tem vizinho “pronto”.
Pop d de pilha e marcá-lo como “visitou”. Não tem vizinho “pronto”.
Pop e de pilha e marcá-lo como “visitou”. Não tem vizinho “pronto”.
A pilha está vazia. Então para.

Portanto, a ordem de passagem é -

$ a \ rightarrow b \ rightarrow c \ rightarrow d \ rightarrow e $

As ordens alternativas de travessia são -

$ a \ rightarrow e \ rightarrow b \ rightarrow c \ rightarrow d $

Ou $ a \ rightarrow b \ rightarrow e \ rightarrow c \ rightarrow d $

Ou $ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $

Ou $ a \ rightarrow d \ rightarrow c \ rightarrow e \ rightarrow b $

Ou $ a \ rightarrow d \ rightarrow c \ rightarrow b \ rightarrow e $

Complexity Analysis

Seja $ G (V, E) $ um gráfico com $ | V | $ número de vértices e $ | E | $ número de arestas. Se o algoritmo DFS visitar todos os vértices do gráfico e verificar todas as arestas, a complexidade do tempo é -

$$ \ circleddash (| V | + | E |) $$

Applications

Detecção de ciclo em um gráfico
Para encontrar classificação topológica
Para testar se um gráfico é bipartido
Localizando componentes conectados
Encontrando as pontes de um gráfico
Encontrar bi-conectividade em gráficos
Resolvendo o problema do Knight's Tour
Resolvendo quebra-cabeças com apenas uma solução