Glossário

Selecione uma das palavras-chave à esquerda…

Grafos e RedesApertos de mão e encontros

Tempo de leitura: ~15 min

Você e seus amigos foram convidados para uma festa de aniversário maravilhosa. Incluindo você e o anfitrião, há ${hnd} pessoas presentes. À noite, quando os convidados se preparam para sair, todo mundo aperta a mão de todo mundo. Quantos apertos de mão foram dados no total? Podemos representar os apertos de mão usando um grafo: toda pessoa é , e todo aperto de mão é . Agora, é fácil contar o número de arestas no grafo. Com ${hnd} pessoas, existem ${hnd*(hnd-1)/2} apertos de mão.

Em vez de contar todas as arestas em grafos grandes, também podemos tentar encontrar uma fórmula simples que nos informe o resultado para qualquer número de convidados. Cada uma das ${n} pessoas na festa aperta a mão de outras ${n-1}. Com isso, há ${n} × ${n-1} = ${n×(n-1)} apertos de mão no total. Para n pessoas, o número de apertos de mão seria .

Infelizmente, esta resposta não está correta. Note como os primeiros elementos da linha do topo são na realidade os mesmos, só que virados ao contrário.

De fato, contamos cada aperto de mão , pois contamos cada aperto de cada uma das duas pessoas que apertaram as mãos. Isso significa que o número correto de apertos de mãos para ${n} convidados é ${n}×${n-1}2=${n*(n-1)/2}.

Os grafos de apertos de mão são especiais porque todos os vértices estão conectados a todos os outros vértices. Os grafos com essa propriedade são chamados grafos completos. O grafo completo com 4 vértices é frequentemente abreviado como K4, o grafo completo com 5 vértices é conhecido como K5 e assim por diante. Acabamos de mostrar que um grafo completo com n vértices Kn tem n×n12 arestas.

Em um dia diferente, você foi convidado para um encontro rápido com ${m} meninos e ${f} meninas. Há muitas mesas pequenas e todo garoto passa 5 minutos com cada uma das meninas. Quantos “encontros” individuais existem no total?

Nesse caso, o grafo representando esta situação consiste em dois conjuntos de vértices. Estes conjuntos estão separados e todo vértice está conectado a todos os vértices do mas nenhum dos vértices do . Os grafos que possuem essa configuração são chamados de grafos bipartidos.

O grafo bipartido com dois conjuntos de tamanho x e y é frequentemente escrito como Kx,y. Possui arestas, o que significa que no exemplo acima existem ${m} × ${f} = ${m×f} encontros.