Olá amigo leitor, tudo bem com você?

Haverá um dia em que você estará no sofá da sua casa, escutando a música ParaTodos do Chico Buarque e ao constatar que ele tem um pai Paulista, um avô pernambucano, um bisavô mineiro e um tataravô baiano irá se perguntar:

Será que o Algoritmo de Prim traçaria uma rota para ajudar  o Chico Buarque a visitar todos esses parentes?

Eles estão em tudo

Espero muito que você chegue nesse ponto, porque esse é um dos melhores efeitos colaterais de estudar  grafos: nós começamos a enxergá-los em tudo.

Obs: Caso não saiba o que é um grafo, recomendo ler este artigo do Deviante  primeiro.

Por se tratar de um tópico da Matemática (que os Cientistas da Computação pegam emprestado de vez em quando) no qual as redes e conexões são examinadas, os grafos são muito bons para modelar problemas de nosso mundo real, que anda cada vez mais conectado.

Geralmente suas aplicações mais comuns são para:

1. Representar rotas e caminhos mais curtos que ligam um destino A com um destino B.
2. Representar relações entre pessoas numa rede social.
3. Ordenação e Classificação de  Informações (Disciplinas de uma grade escolar, que tenham dependências entre si, por exemplo).
4. Gerar recomendações de produtos, filmes e músicas baseados no histórico de dados de um usuário.

Contudo, os grafos também são usados para resolver outros problemas bem curiosos. Veja abaixo algumas situações inusitadas onde eles podem ou foram utilizados.

Resolvendo um antigo problema Matemático

Ao pintar um mapa da Inglaterra em 1852, o Matemático e Botânico Sul Africano Francis Guthrie, chegou a conclusão de que só eram necessárias 4 cores para colorir todos os estados que faziam fronteiras entre si.

Após abstrair um pouco,  Guthrie começou a consultar outros matemáticos se esta característica poderia ser aplicada a qualquer mapa existente.

Simplificação da prova de Appel e Haken, utilizando grafos e arestas. @anevolvedmonkey/the-four-colour-map-theorem">Fonte

Nascia ali o Teorema das 4 cores,  que teve sua prova realizada em 1976 pelos matemáticos Kenneth Ira Appel e Wolfgang Haken. 

Para realizar a prova, os matemáticos documentaram uma grande quantidade de grafos, representando diversos tipos de mapas, e utilizaram um computador para colorir as arestas que tinham conexões entre si, com cores distintas uma da outra.

A conclusão foi de que realmente só eram necessárias 4 delas para realizar o trabalho.

Em suma,  esse modelo mental é útil para entendermos diversos tipos de redes. De computadores a Sequenciamento de DNA.

Organização de pessoas com interesses comuns

Em 1966 Hedetniemi’s  propôs em sua tese de Doutorado um teorema chamado Conjectura de Hedetniemi’s que permaneceu sem uma contraprova por diversos anos.

Contudo em 2019, o Phd em Matemática Yaroslav Shitov conseguiu contestar essa tese.  Neste vídeo do excelente canal de Matemática Numberphille, a matemática e  pesquisadora Erica Klarreich explica a relação dessa contraprova com Grafos, através de exemplos.

Não tenho espaço neste artigo e nem a sofisticação matemática para explicar com profundidade os artigos acima. Contudo,  acredito que com um número pequeno de dados vamos conseguir criar uma analogia ao exemplo em que ela utiliza o conceito de Tensor Product.

Casamento fictício do Chico Buarque

Imagine que a mesma família da primeira estrofe da música ParaTodos irá participar da festa de um casamento fictício do Chico Buarque.

Você é o organizador do cerimonial e recebeu a singela lista de pessoas:

Além da lista foi solicitado para o cerimonial que:

1. Toda mesa precisa ter uma pessoa de cada estado.
2. É necessário que pelo menos um amigo do Chico e um amigo da Esposa estejam nas mesas (para os convidados não ficarem deslocados).

Pois bem, modelar essa situação em formato de grafos pode auxiliar bastante a resolução do problema.

Primeiramente iremos desenhar o layout da mesa e colocar uma cor para cada um dos estados:

Figura 1 : Representação da mesa em forma de grafo

Depois iremos representar a relação entre os convidados e os Amigos dos envolvidos com outro grafo.

Figura 2:  Relação entre convidados e amigos

Perceba que eu tracei uma linha vermelha entre os amigos da Esposa e os amigos do Chico de forma intencional. Irei explicar o motivo mais a frente.

Após isso, criamos uma representação dos grupos mesclados por estado e por relacionamento com o casamento.

Paulistas e Pernambucanos

Baianos e Mineiros

Configuração final

Com esta modelagem nas mãos, fica mais fácil realizar a estruturação das 4 mesas (uma vez que só são 16 convidados).

Abaixo segue a minha configuração final, mas você pode tentar gerar outras manualmente se quiser.

Perceba que, além de um número bem modesto de convidados, eu não coloquei neste problema nenhuma restrição entre os relacionamentos pessoais.

Tudo ficaria mais complexo se, para o mesmo cenário, houvesse premissas como:

1. Amigos da esposa e do Chico não podem ficar na mesma mesa (a linha vermelha ligando o ponto amarelo e o roxo não existiria).
2. Paulistas e Baianos, não podem ficar juntos em uma mesa (a linha vermelha ligando o ponto verde e o amarelo também não existiria).

Conclusão

Em suma,  este artigo é apenas um introdução.

No futuro, pretendo me aprofundar no análise do Algoritmo de Dijkstra, Algoritmo de Prim e outros para observar o quanto eles fazem parte da nossa vida de forma transparente e indireta.

Mas por enquanto é só.

Espero que essa tenha sido uma boa leitura para você e um grande abraço!