1 A figura abaixo representa as ligações rodoviárias entre 14 cidades. Existe um caminho passando por cada cidade exatamente uma vez?
2 4. Em um conjunto de 2n pessoas, cada uma delas possui um número par de amigos. Prove que existem duas pessoas que possuem um número par de amigos em comum.
Anexos:
Soluções para a tarefa
Respondido por
0
1.
a)
Não, uma vez que a teoria dos grafos afirma que a incidência de três arestas em apenas um vértice torna impossível que se atravesse cada ponto apenas uma vez.
Para que fosse possível passar por cada ponto apenas uma vez, cada vértice deveria possuir apenas um par de arestas.
b)
Para solucionar o problema basta utilizar a proposta de teoria dos grafos, onde um vértice possui duas arestas, uma das quais, se houver um novo vértice, estará ligada à ele.
Espero ter ajudado, bons estudos.
Perguntas interessantes