Uma das matérias mais odiadas por todo mundo que está no colégio ou para quem já esteve, é a famosa matemática. Para você ter sucesso nessa matéria, você precisa ter uma incrível facilidade com problemas de lógica e pensamento rápido, além de muita atenção para que nada saia errado. Qualquer número ou sinal incorreto pode fazer você errar o problema grotescamente.

E mesmo os próprios matemáticos, às vezes, não conseguem responder os problemas feitos. E eles ficam anos, décadas e até milênios sem uma resposta. Esses dois cientistas da computação dinamarqueses conseguiram resolver um enigma matemático bem antigo. Ele ficou adormecido por décadas. E desde os anos 1990 que os pesquisadores não conseguiram progressos com ele.

O problema em questão faz parte do que é chamado de "teoria dos grafos". E diz respeito, especificamente, ao desafio de encontrar um algoritmo para resolver a planaridade de um gráfico dinâmico.

Problema

Em 1913, por mais que os conceitos matemáticos possam provavelmente ser rastreados bem mais longe, foi publicado um quebra-cabeça chamado problema dos três utilitários. Colocando de forma simples, imagine que exista três casas alinhadas em uma linha que você poderia desenhar em um pedaço de papel. Embaixo dela você também pode desenhar três utilitários separados. Como por exemplo, água, gás e eletricidade.

Publicidade
continue a leitura

O desafio é traçar linhas no gráfico conectando os três utilitários a cada casa. Mas existe um problema. Nenhuma das linhas, que são nove no total, podem se cruzar. No sentido mais convencional, em uma folha de papel comum bidimensional, não tem como resolver esse problema. Não serão todas as casas que receberão suas conexões.

Mas esse problema não é um quebra-cabeça qualquer. Ele é um exemplo de como alguns tipos de redes grafos não são planas. Ou seja, capazes de ter arestas, as linhas, conectando vários vértices, as casas e utilitários, sem que as linhas se cruzem.

Quando se está mexendo com gráficos mais complexos com mais vértices, o teorema de Kuratowski ajuda os matemáticos a determinar se os gráficos são ou não planos. E desde a década de 1970 os pesquisadores vem desenvolvendo algoritmos para fazer a mesma coisa de forma mais rápida.

Algoritmo

Publicidade
continue a leitura

Mas depois de um avanço algorítmico que aconteceu na década de 1990, mais nenhum progresso substancial foi feito durante décadas. Foi então que, no ano passado, os cientistas da computação Jacob Holm, da Universidade de Copenhagen, e Eva Rotenberg, da Universidade Técnica da Dinamarca, estavam trabalhando para resolver o problema.

“Quase desistimos de pegar a última peça e resolver o enigma. Imaginamos que ainda haveria mais cinco anos de trabalho, na melhor das hipóteses, antes de sermos capazes de resolver o quebra-cabeça", disse Holm.

Então, quase que por acidente, eles perceberam que já tinham resolvido a maior parte do problema em outro trabalho de pesquisa. Em um artigo sobre conceitos planares relacionados que eles tinham feito em 2019.

Com essa solução oculta já publicada, a dupla melhorou o algoritmo de representação gráfica. Que não tinha sofrido nenhum aprimoramento desde os anos 1990. “Trabalhamos no artigo sem parar, por cinco a seis semanas. E acabou enchendo mais de 80 páginas”, disse Rotenberg.

Publicidade
continue a leitura

Resultados

Os resultados publicados dão um algoritmo que leva menos tempo para resolver a questão de se um gráfico dinâmico pode suportar um embedding plano. Em outras palavras, se ele poderia ser desenhado em um papel sem que as linhas se cruzassem.

Esse é um grande avanço. Já que as dificuldades presentes em uma coisa conceitualmente simples, como o problema dos três utilitários, se torna muito mais insondáveis em campos como projeto de microchip ou planejamento de estradas.

“Acontece que, para problemas de gráfico dinâmico, muitas vezes é possível construir alguma estrutura de dados que pode ser usada para recalcular a resposta após cada mudança no gráfico muito mais rápido do que recomputar a resposta do zero. Este resultado é obviamente uma grande vitória pessoal para nós”, concluiu Holms.

Publicado em: 20/08/20 17h06