a) Pretende-se distribuir os 250 alunos de uma escola por 7 equipes para uma feira de ciências. Qual o maior valor de k para o qual se pode afirmar que necessariamente pelo menos uma equipe terá pelo menos k alunos?

b) Enuncie o teorema de Euler para um grafo planar qualquer e sua versão para uma

árvore (justifique).

Passo 1

E aiii, galerinhaa!!

Em a, queremos distribuir os 250 alunos de uma escola por 7 equipes e encontrar o maior valor de k que garante que pelo menos uma equipe terá k alunos? Bom, pelo princípio da casa dos pombos, nós teremos que:

250 - 1 7 + 1 = 35 + 1 = 36

Se fizermos 35*7, temos o resultado de 245 e restariam 5 alunos, já que temos 250. Com esses 5 alunos restando, pelo menos uma equipe receberia ao menos 1 aluno. Ou seja, teria pelo menos 36 alunos.

Passo 2

Em b, teremos que:

| v ( G ) | - | E ( G ) | + f = p + 1 , em que v(G) é o número de vértices, E(G) é o número de arestas, f são as faces e p+1 é o número de conexões.

Para uma árvore, teremos que p = 1, já que é conexa. Como não tem circuitos, f = 1, tendo apenas a face externa. Assim, em uma árvore, teríamos que

| v ( G ) | - | E ( G ) | = 1   o u   | v ( G ) | = | E ( G ) | + 1

Resposta

a) 36 alunos.

b) | v ( G ) | - | E ( G ) | + f = p + 1 e | v ( G ) | - | E ( G ) | = 1  

Exercícios Resolvidos de Método de Euler

Ver Teoria

Exercícios de Livros Relacionados