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.

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:

Número	Nome	Estado	Proximidade
1	Dr. Jack Shephard	Paulista	Amigo da Esposa
2	Kate Austen	Paulista	Convidado
3	John Locke	Paulista	Convidado
4	James Sawyer Ford	Paulista	Amigo da Esposa
5	Claire Littleton	Pernambucano	Convidado
6	Sayid Jarrah	Pernambucano	Convidado
7	Hugo Hurley Reyes	Pernambucano	Amigo da Esposa
8	Jin-Soo Kwon	Pernambucano	Convidado
9	Sun-Hwa Kwon	Mineiro	Amigo da Esposa
10	Boone Carlyle	Mineiro	Amigo do Chico
11	Walt Lloyd	Mineiro	Amigo do Chico
12	Miles Straume	Mineiro	Convidado
13	O Homem de Preto	Baiano	Amigo do Chico
14	Ilana Verdansky	Baiano	Convidado
15	Richard Alpert	Baiano	Amigo do Chico
16	Frank Lapidus	Baiano	Convidado

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:

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

 

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.

 

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.

Número	Nome	Estado	Proximidade	Mesa
2	Kate Austen	Paulista	Convidado	1
9	Sun-Hwa Kwon	Mineiro	Amigo da Esposa	1
15	Richard Alpert	Baiano	Amigo do Chico	1
3	John Locke	Paulista	Convidado	1
1	Dr. Jack Shephard	Paulista	Amigo da Esposa	2
5	Claire Littleton	Pernambucano	Convidado	2
12	Miles Straume	Mineiro	Convidado	2
13	O Homem de Preto	Baiano	Amigo do Chico	2
4	James Sawyer Ford	Paulista	Amigo da Esposa	3
6	Sayid Jarrah	Pernambucano	Convidado	3
11	Walt Lloyd	Mineiro	Amigo do Chico	3
16	Frank Lapidus	Baiano	Convidado	3
7	Hugo Hurley Reyes	Pernambucano	Amigo da Esposa	4
8	Jin-Soo Kwon	Pernambucano	Convidado	4
10	Boone Carlyle	Mineiro	Amigo do Chico	4
14	Ilana Verdansky	Baiano	Convidado	4

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!