Connect with us

Hi, what are you looking for?

Ciência

Enigma de três décadas perdido acaba de ser decifrado

(Créditos da imagem: Pixabay).

Dois cientistas da computação dinamarqueses acabaram de resolver um enigma de três décadas perdido. O enigma havia sido proposto nos anos 1990 e, desde então, foi esquecido pelo tempo. 

A resolução foi realmente notável, e rendeu um artigo científico publicado no STOC 2020, a edição deste ano do Symposium on Theory of Computing (Simpósio de Teoria da Computação).

 Teoria dos grafos, o enigma de três décadas

O enigma faz parte um ramo da matemática chamado de teoria dos grafos. A teoria dos grafos é, em resumo, o estudo de elementos de um conjunto e suas mútuas relações.

Continua depois da publicidade

O nome ‘grafos’ (veja bem, não são garfos), vem do nome das estruturas utilizadas nas resoluções desses problemas: os grafos. Em um primeiro momento, os grafos se parecem bastante com aqueles joguinhos de ligar os pontos – sem querer ofender os matemáticos. 

Apesar de parecer simples, não é. Este problema específico, envolvia a criação de um algoritmo para se conseguir resolver a planaridade (o formato de um grafo que se cruza) em um gráfico dinâmico (que muda).

Entretanto, há um problema: essas linhas não podem se cruzar. Em alguns casos isso não é possível – pelo menos não em um mapa bidimensional. A situação muda quando se utiliza gráficos em três dimensões, já que há mais arestas possíveis.

Continua depois da publicidade

Existe um teorema chamado de Teorema de Kuratowski, que foi criado especificamente para auxiliar a desenvolver esta tarefa, que parece simples mas é realmente árdua.

Alguns problemas atingem um nível de complexidade o suficiente para que a resolução manual se torne impraticável, e para isso, há diversos algoritmos, para que um computador, que é capaz de realizar bilhões, ou até trilhões de cálculos por segundo.  

E foi nesse ponto que eles trabalharam. Se gráficos estáticos podem já representar desafios consideráveis, imagina um gráfico em constante mudança. A dupla conseguiu progredir em algoritmos parados desde os anos 1990.

Continua depois da publicidade

Um exemplo simples da teoria dos grafos

Grafos, gráficos estáticos, gráficos dinâmicos, algoritmos… assunto técnico e chato demais, não? Na verdade não. Vamos entender através de um exemplo simples e bastante famoso. 

Esta imagem abaixo representa o Problema dos Três Utilitários. A ideia principal por trás dele é simples. Você precisa apenas ligar os pontos, seguindo algumas regras, entretanto. 

São, como você pode ver, três chalés. Há, também, no plano, três companhias, que oferecem três serviços diferentes: uma oferece água, a segunda oferece gás, e a terceira, energia. 

Continua depois da publicidade

Agora, você precisa ligar cada um dos chalés até cada um dos serviços. Isso é simples, correto? Entretanto, você não pode fazer nenhuma linha se cruzar, e pode utilizar somente o plano, ou seja, apenas essas duas dimensões. Tente fazê-lo antes de terminar de ler. 

 

Parece difícil? Na verdade é impossível, como você pode ver na imagem acima. É provado matematicamente que este não é um gráfico plano. A única forma de resolvê-lo é com três dimensões.

Continua depois da publicidade

Este é apenas um exemplos simples, para ilustrar, que pode ser facilmente resolvido com três dimensões. Naquela mesma foto acima, se você considerar que aquela linha azul cruzando com a amarela está, na verdade, acima, está resolvido. Os problemas resolvidos computacionalmente, entretanto, são bem mais complicados.

Com informações de Science Alert.

 

Continua depois da publicidade
Avatar
Publicado por

É divulgador científico por paixão. Gradua-se em Física pela UFSCAR e atua principalmente na Ciencianautas e SoCientífica.


Populares hoje