Explique por que no grafo de colaboração dos matemáticos um vértice que representa um matemático está na mesma componente conexa do vértice que representa Paul Erdös se e somente se o matemático tem um número de Erdös finito.
Passo 1
O enunciado fala do grafo de colaboração dos matemáticos, que é o grafo
onde cada vértice em
representa um matemático e cada aresta em
liga dois vértices sempre que esses dois matemáticos escreveram juntos pelo menos um artigo. A componente conexa de um vértice
é o conjunto de todos os vértices que se conectam a
por algum caminho. O número de Erdős de um matemático
, denotado
, é definido como a menor quilha (número de arestas) de um caminho de
até Paul Erdős; se não existir caminho, dizemos que
. Queremos mostrar que
“ está na mesma componente conexa de Erdős”
se, e somente se, é finito.
“
se, e somente se,
Passo 2
Suponha primeiro que
é finito. Por definição de “número de Erdős”, existe um caminho em
de Erdős até
com comprimento igual a
. Mas ter um caminho entre dois vértices significa exatamente que eles pertencem à mesma componente conexa. Logo, se
é finito, então
está na mesma componente conexa de Paul Erdős.
Passo 3
Agora suponha que
esteja na mesma componente conexa de Paul Erdős. Isso significa que existe pelo menos um caminho finito de Erdős até
em
. Como o número de Erdős é definido justamente como o comprimento mínimo entre todos os caminhos que ligam Erdős a
, esse comprimento mínimo será um número natural (ou zero, no caso de
Erdős). Logo
. Assim, estar na mesma componente implica número de Erdős finito.
Resposta
Um matemático
pertence à mesma componente conexa de Paul Erdős se, e somente se, existe um caminho finito em
ligando-os; mas isso equivale exatamente a dizer que o menor comprimento de caminho (isto é, o número de Erdős de
) é finito.