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 G=(V,E) onde cada vértice em V representa um matemático e cada aresta em E liga dois vértices sempre que esses dois matemáticos escreveram juntos pelo menos um artigo. A componente conexa de um vértice v é o conjunto de todos os vértices que se conectam a v por algum caminho. O número de Erdős de um matemático m, denotado \mathrm{E}(m), é definido como a menor quilha (número de arestas) de um caminho de m até Paul Erdős; se não existir caminho, dizemos que \mathrm{E}(m)=\infty. Queremos mostrar que
m está na mesma componente conexa de Erdős”
se, e somente se, \mathrm{E}(m) é finito.

Passo 2

Suponha primeiro que \mathrm{E}(m) é finito. Por definição de “número de Erdős”, existe um caminho em G de Erdős até m com comprimento igual a \mathrm{E}(m)<\infty. Mas ter um caminho entre dois vértices significa exatamente que eles pertencem à mesma componente conexa. Logo, se \mathrm{E}(m) é finito, então m está na mesma componente conexa de Paul Erdős.

Passo 3

Agora suponha que m esteja na mesma componente conexa de Paul Erdős. Isso significa que existe pelo menos um caminho finito de Erdős até m em G. Como o número de Erdős é definido justamente como o comprimento mínimo entre todos os caminhos que ligam Erdős a m, esse comprimento mínimo será um número natural (ou zero, no caso de m= Erdős). Logo \mathrm{E}(m)<\infty. Assim, estar na mesma componente implica número de Erdős finito.

Resposta

Um matemático m pertence à mesma componente conexa de Paul Erdős se, e somente se, existe um caminho finito em G ligando-os; mas isso equivale exatamente a dizer que o menor comprimento de caminho (isto é, o número de Erdős de m) é finito.

Exercícios de Livros Relacionados