Conjectura de Babai: grafos e redes de computadores

Ao criar uma rede de computadores buscamos a maneira mais inteligente de conectá-los.

Podemos, por exemplo, colocá-los em círculo, da seguinte forma.




Porém, essa não é uma boa forma de fazer a conexão. Observe que para enviar algo de um computador a outro será necessário passar por até 6 dispositivos diferentes. Quando temos muitos computadores, esse número se torna muito grande, e o processo fica muito lento.

Além disso, se um computador falhar, o tempo dobra e se dois destes computadores pararem de funcionar, partes do esquema se isolam completamente.

Outra opção seria conectar todos entre si.



Mas essa maneira de interligá-los não é viável, principalmente com um número grande de dispositivos.


Esses esquemas são chamados de grafos e o número de passos necessários para estabelecer a conexão entre qualquer par de computadores é chamado de diâmetro. Nos exemplos anteriores temos, respectivamente, diâmetros 6, 11, infinito e 1.


O que precisamos é um grafo no qual:

  • Cada ponto se conecte diretamente a poucos outros;

  • O diâmetro seja pequeno;

  • Nenhum ponto seja indispensável ao bom funcionamento.

Pensar em formas de construir uma estrutura com essas características é um grande desafio.

A conjectura de Babai sugere como isso pode ser feito. Ela teoriza que grafos construídos de uma determinada maneira tem diâmetro pequeno, ou pelo menos que cresce lentamente na medida em que se aumenta o número de pontos.


Por meio da conjectura, obtemos, por exemplo, a seguinte forma de conectar os computadores.





Fazemos isso associando uma matriz a cada computador e conectando cada uma delas a seu produto por outra matriz previamente definida.


Já foi provado que dessa forma encontramos um esquema eficiente para um número arbitrariamente grande de computadores. Além disso, todos os resultados obtidos até hoje apontam que o mesmo é válido para todos os grafos dos quais a conjectura fala, ou seja, que ela é verdadeira. Porém, isso ainda não foi comprovado e a questão permanece sem uma resposta definitiva.


Este texto foi produzido por Bárbara Muniz e é um resumo de seu trabalho de Iniciação Científica, que foi um dos escolhidos em outubro de 2020 no Departamento de Matemática da UFMG para ser apresentado na Semana do Conhecimento. A Bárbara foi orientada pelo professor Csaba Schneider.

87 visualizações