MAT233 – MATEMÁTICA DISCRETA A
NOME:
QUESTÃO 1:
a) Numerando as pontes na figura 1, descreva um percurso pelo qual você partiria da região A e
retornaria a ela, de forma que passasse por todas as pontes. Para realizar esse percurso você
precisou passar pela mesma ponte mais de uma vez?
b) Seria possível fazer esse passeio pela cidade cruzando cada ponte exatamente uma vez?
Procure no texto uma justificativa para sua resposta.
FIGURA 1
FIGURA 2
QUESTÃO 2:
a) De que forma você representaria uma rede de comunicação por cabos telefônicos entre as
cidades da figura 2, de tal maneira que possa haver comunicação entre cada par de cidades e
admitindo que qualquer cidade pode mandar mensagem para outra por uma terceira.
b) Sua representação seria uma das formas mais econômicas? Justifique.
QUESTÃO 3:
Quantas cores no mínimo são necessárias para colorir os mapas a seguir, de maneira que nenhum par
de regiões que tenham uma fronteira em comum (não apenas um ponto) seja da mesma cor?
MAPA 1
MAPA 2
QUESTÃO 4:
a) Considerando as regiões como nós e as pontes como arcos, a representação do problema das
pontes de Königsberg seria um grafo ou um multigrafo? Justifique.
b) Justifique porque o problema das pontes de Königsberg não tem solução.
c) Quais obras realizarias na cidade para que o problema tivesse solução?
d) Verifique se o teorema 8.1 é verdadeiro para este problema.
QUESTÃO 5:
Para minimizar o custo com a instalação de cabos entre as cidades da questão 2, utilizaríamos uma
representação em grafos ou multigrafos?
QUESTÃO 6:
Verifique se os (multi)grafos a seguir são eulerianos. Se forem, determine um circuito que percorre
cada arco exatamente uma vez.
QUESTÃO 7:
a) Dada a matriz de incidência a seguir, faça a representação do (multi)grafo.
[
]
b) Determine o grau de cada um dos nós.
QUESTÃO 8:
Utilize um dígrafo para representar, na figura abaixo, uma rota para um ônibus que deve
passar uma única vez em cada terminal e retornar ao ponto de partida.