24

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

ALUNOS QUE TAMBÉM VISUALIZARAM

  • +6.229

Passo 1 de 5keyboard_arrow_downkeyboard_arrow_up

Nesse exercício vamos imaginar uma festa em que professores se cumprimentam através de apertos de mão. Cada professor conta quantas pessoas cumprimentou. Ao final da festa, essa contagem de cada professor é somada. Vamos provar que o resultado dessa soma sempre será par (lema do cumprimento):

Passo 2 de 5keyboard_arrow_downkeyboard_arrow_up

Perceba que essa demonstração é equivalente a provar que a soma dos graus de todos os vértices de um grafo não direcionado é sempre par. Isso ocorre pois podemos modelar esse problema como um grafo não direcionado, onde os professores são os vértices e os cumprimentos são as arestas, não direcionadas pois sempre que um professor cumprimenta um professor , o cumprimento inverso também ocorre.

Passo 3 de 5keyboard_arrow_downkeyboard_arrow_up

Vamos chamar de uma função que assume valor 1 se cumprimentar e 0, caso contrário. Calculando o somatório dos graus em termos dessa função f, temos:

Passo 4 de 5keyboard_arrow_downkeyboard_arrow_up

Podemos alterar esse somatório em termos das arestas, isto é, para cada aresta temos dois professores contando tal aperto de mão, portanto:

Passo 5 de 5keyboard_arrow_downkeyboard_arrow_up

Provamos, portanto, usando analogia entre aperto de mãos e grafo não direcionado, que a soma dos graus dos vértices de um grafo não direcionado é par e dado pela seguinte expressão:

Depoimentos de estudantes que já assinaram o Exercícios Resolvidos

Nathalia Nascimento fez um comentárioCEFET/RJ • Engenharia
Foi um apoio àquelas aulas que não acabam totalmente com as dúvidas ou mesmo naquele momento de aprender o conteúdo sozinha. Além disso, dispensou a necessidade de um orientador e por isso, permitiu que eu estudasse em qualquer local e hora.
Valdivam Cardozo fez um comentárioUFRB • Engenharia
Tive uma sensação maior de autonomia nos estudos, as vezes era frustante não conseguir resolver uma determinada questão e nem sempre os professores corrigem as listas que passam.