Amor e grafos

Será possível representar relações entre n pessoas através de um grafo que possua todas as arestas com o mesmo tamanho?

A ideia para este post surgiu com um twit do @MattSimonato:

Muito meigo nosso quadrado amoroso aí @leitedevaca, @grandeabobora e @eroguro <3 #grandevacabit

Descontando o teor altamente homossexual das palavras acima (e destas e destas também), eu vislumbrei um problema a ser atacado matematicamente.

Achei a expressão quadrado amoroso muito estranha. Já tinha ouvido falar, assim como vocês já devem ter ouvido, em triângulo amoroso. Mas quadrado nunca. Então pensei no seguinte, já descontando a baitolagem da afirmação matheusiana.

Suponha a amizade como uma relação simétrica (isto é, se A é amigo de B, então B é amigo de A). Suponha que a intensidade da amizade que as pessoas sentem seja constante de pessoa para pessoa. Será possível representar estas relações numa figura geométrica tipo um grafo (mas não necessariamente), onde a existência da amizade seja representada por arestas de comprimento constante?

Me pus a resolver este problema. Para o caso em que apenas duas pessoas se relacionam, a solução é trivial, como podemos ver na figura abaixo.

Se A e B se amam, a única maneira de conectá-los é através do único segmento de reta que passa simultaneamente pelos dois pontos. Mas e se adicionarmos mais uma pessoa a este universo, o que ocorre? Bem, o próprio nome deste tipo de configuração, caso falássemos de amor, já dá uma dica a respeito do que obteremos.

Um triângulo amoroso, nas condições que exigi para o problema, é resolvido através de um triângulo equilátero. Mas e se mais uma pessoa aparecer, se apaixonar pelas 3 já existentes (ou, voltando à proposta inicial, contrair amizade) e elas se apaixonarem por ela? Podemos ter um quadrado amoroso?

A resposta é não. Note que, apesar das relações AB, BC, CD e DA possuírem a mesma intensidade (como definido anteriormente, isto significa o mesmo tamanho para os segmentos de reta), AC e BD são claramente maiores. Um cálculo rápido nos indica que, se AB=1, então AC=√2.

Mas haverá outra configuração então, que não seja o quadrado?

Bem, paralelogramos e retângulos estão excluídos, pois não possuem os lados congruentes, em geral. Nos sobra o losango, mas ele também gera um problema.

Mesmo que, por definição de um losango, AB, BC, CD e DA sejam iguais, e façamos com que BD também tenha este mesmo comprimento, a diagonal AC será maior que todos os outros segmentos de reta. Logo, o losango não nos serve.

Por fim, podemos no basear no grafo utilizado para o triângulo amoroso e colocar um ponto nele um ponto D tal que D seja equidistante de A, B e C.

O problema é que este ponto não gera os segmentos de mesmo tamanho exigidos pelo problema. Note que, claramente, AD<AB.

Mas então, da forma que foi proposto, o problema é insolúvel?

Sim e não.

Sim, pois é insolúvel em duas dimensões.

Não, porque o tetraedro consegue satisfazer as exigências que fiz.

Um tetraedro é a figura mais simples que pode ser feita em três dimensões. É composto por quatro triângulos equiláteros, tendo assim as quatro arestas que exigi, todas elas com as mesmas dimensões por construção.

Mas vocês perceberam o padrão aqui?

• 2 pessoas -> Figura em 1 dimensão
• 3 pessoas -> Figura em 2 dimensões
• 4 pessoas -> Figura em 3 dimensões
• 5 pessoas -> Figura em 4 dimensões

QUATRO DIMENSÕES?

Sim, quatro dimensões. E ela se chama pentachoron, nome cuja tradução em português eu desconheço.

Anteriormente eu afirmei que o tetraedro é a figura mais simples a ser construída em três dimensões. Isso não foi por acaso. Estes conjuntos de pontos que exibem estas características são chamados de simplexos. O vídeo abaixo exibe a construção de simplexos da dimensão 0 (um ponto) até a dimensão 10.

^{Link para o vídeo}

O problema para nós, seres tridimensionais, é que figuras com mais de três dimensões são muito difíceis de visualizar. Pensem na seguinte analogia: se vivêssemos em um mundo de duas dimensões (uma folha de papel, por exemplo) e um ser de três dimensões cruzasse nosso espaço, somente veríamos sua projeção em duas dimensões.

Se, por exemplo, vivêssemos numa folha de papel horizontal e uma bola atravessasse esta folha no sentido vertical, primeiro veríamos um ponto, que viraria uma circunferência. Esta circunferência aumentaria de tamanho até atingir um valor máximo, que seria o diâmetro a esfera. Aí, diminuiria seu tamanho, até se tornar um ponto novamente.

Eu mentiria se eu dissesse que vejo o simplexo da quarta dimensão. Eu consigo fazer cálculos em n dimensões (na verdade, trabalho até com espaços vetoriais de dimensão infinita), mas nunca realmente enxergo o que estou fazendo.

Um adendo: compare o verbete simplex da wikipedia em inglês com o verbete simplex da wikipedia em português. A diferença é de chorar.