Teoria dos Grafos

   No século XVIII moradores de Königsberg, se desafiaram com o seguinte problema: como seria possível dar um passeio pela cidade, passando apenas uma vez por cada uma das sete pontes que ligavam a região. Essa cidade tinha duas ilhas, com sete pontes ligando quatro porções de terra. Uma porção era conectada por cinco pontes e as demais eram conectadas por três pontes[1].

   Esse enigma foi solucionado por Leonhard Euler. Ele provou de forma matemática que era impossível dar o passeio a pé passando apenas uma vez por cada uma das pontes. Sua solução pode ser vista como um diagrama que tem quatro pontos representando as porções de terra e sete ligações representando as pontes[1][2].

Representação do método

Fonte: Wikipedia – Graph Theory

   Nesse modelo podemos chamar cada ponto de vértice, cada ligação entre os pontos de aresta, dessa forma raciocínio foi: para visitar um vértice é preciso de duas arestas, uma para entrar e outra para sair, isso significa que cada vértice diferente do início e fim precisaria ter um número par de arestas, o que não é o caso, já que todos os cinco vértices tem um número ímpar de arestas.

   O nome da representação feita por Euler é denominado atualmente como Grafo. Um grafo G= (V, E) é um conjunto de vértices V e arestas E. O raciocínio descrito por Euler tem imensa importância, pois através dele diversos outros problemas envolvendo esse tipo de representação puderam ser solucionados[3].

   Pode-se representar com grafos inúmeras coisas do mundo real, desde uma sequência de DNA, até a representação de malha viária, para fazer essas representações podemos também utilizar grafos com arestas direcionadas [4]. 

   Um exemplo seria sua aplicação em redes sociais: Alice  tem uma conta no Instagram, cada perfil nessa rede social é um vértice.  Alice é uma pessoa que tem vários seguidores, Bárbara é um de seus seguidores, podemos representar essa situação como A→B, ou seja, um perfil A segue o perfil B, em grafos podemos dizer que B é adjacente de A. Dentre esses seguidores Malu segue de volta alguns, o que em teoria dos Grafos pode ser representado da seguinte forma: A↔B, agora temos uma seta indo e voltando.

   A partir do modelo desenvolvido por Euler, foi possível solucionar vários problemas práticos em diversas áreas: matemática, engenharias, computação, etc.

  Sem os estudos nessa área de grafos está mundo presente no mundo atual. Na área de computação foram desenvolvidos diversos algoritmos capazes de solucionar alguns problemas, entre esses, um dos mais difundidos é o algoritmo de Dijkstra. Publicado em 1959, um artigo onde apresentava seu algoritmo capaz de encontrar o menor caminho entre dois pontos de um grafo.

   O algoritmo desenvolvido por Dijkstra é aplicado massivamente. Você já pediu um carro por aplicativo? Pois bem, o cálculo da rota do motorista até você usa esse algoritmo. Você fez uma pesquisa na internet? Isso também usou esse algoritmo. Contudo existem muitos outros outros algoritmos aplicados em grafos.

Autor: Yorranan Costa.

Referências.

[1] Rede Globo. Entenda o enigma das pontes de Königsberg que instigou a geometria. 2011. Disponível em: http://redeglobo.globo.com/globociencia/noticia/2011/12/entenda-o-enigma-das-pontes-de-konigsberg-que-instigou-geometria.html. Acesso em 22 de maio de 2023.

[2] Wiki Computação. Teoria dos Grafos. UTFPR. 2022. Disponível em: https://wiki.inf.ufpr.br/computacao/doku.php?id=t:teoria_dos_grafos. Acesso em: 21 de maio de 2023

[3]WAKABAYASHI, Y; KOHAYAKAWA, Y; FEOFILOFF, P. Teoria dos Grafos. São Paulo: SBM, 2000. Disponível em: https://www.ime.usp.br/~yw/publications/books/TeoriaDosGrafos.pdf. Acesso em: 22 maio 2023.

[4] AKITA, Fábio. Desbloqueando o “Algoritmo” do Twitter – Introdução a Grafos. 2023. Disponível em: https://www.youtube.com/watch?v=uIflMYQnp8A. Acesso em: 22 de abril de 2023