35

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

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

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:

Navegar por capítulo

Aprenda agora com os exercícios mais difíceis

R$29,90/mês

Cancele quando quiser, sem multa

Aproveite também

  • check Exercícios passo a passo
  • check Resumos por tópicos
  • check Disciplinas ilimitadas
  • check Ferramentas para otimizar seu tempo