Grafos e RedesApertos de mão e encontros

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 n×n−1n×n+1n2.

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 duas vezesuma única veztrês vezes, 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×n−12 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?

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