Como calcular graus de separação

Havia uma vez um jogo, "seis graus de Kevin Bacon"

O objectivo disto era ser a pessoa que pudesse ligar um actor aleatório com o actor epónimo com o menor número de graus de separação.

Kevin Bacon é zero graus

Uma pessoa que tenha estado num filme com Kevin Bacon é um grau de separação dele

Uma pessoa que tenha estado num filme com alguém que tenha estado num filme com Kevin Bacon é dois graus de separação dele.

e assim por diante.

Aparentemente é, ou pelo menos era quando este jogo era popular, difícil encontrar QUALQUER ator que tenha estado em um filme que esteja a mais de seis graus de separação de Kevin Bacon, e é por isso que este jogo foi construído em torno dele.

Later, uma faculdade ou universidade da Virginia... acho que foi a Virginia Tech ou algo assim... criou o "Bacon Engine" que encontraria o número mínimo de Bacon para qualquer ator no IMDB.

De qualquer forma, essa é uma longa maneira de dizer que alguém tem zero graus de separação se for a própria pessoa, um grau se se associar diretamente com essa pessoa, dois graus se se associar com alguém que se associa diretamente com essa pessoa e assim por diante.

Do seu comentário, eu poderia alterar isso para "está em um grupo com" ao invés de "associa-se com"

Por exemplo, quantas pessoas seriam necessárias para que esse grupo fosse dois graus de separação de todos em uma cidade?

Esse é o seu comentário real. Não faz sentido nenhum. Que grupo?

De qualquer forma, digamos que a sua cidade requer que todos usem a mesma empresa de transporte de lixo... então todos na sua cidade estão separados em um grau de separação. É mais difícil imaginar como se chega a dois em vez de um. Oh, aqui vamos nós cada bairro usa um transportador de lixo diferente, mas todos os transportadores vão para o mesmo lixão. Então vocês estão todos a dois graus um do outro.