Matemática discreta

Alyson Xavier Leite

Trabalho de Matemática Discreta

Trabalho de Matemática Discreta, do Curso de Sistemas de Informação da Faculdade FACET. Prof. Sidney Pedroso

Curitiba
2009

1. Dada a planta de um conjunto de salas e da área externa de um imóvel;

[pic]

a) Faça a representação gráfica, através de vértices e arestas; [pic]

b) Construa a matriz adjacência; |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 |11 |E | |1 |0 |1 |0 |0 |0 |0 |0 |0 |1 |0 |0 |1 | |2 |1 |0 |0 |1 |0 |0 |1 |0 |0 |0 |0 |1 | |3 |0 |0 |0 |0 |1 |0 |1 |0 |0 |1 |0 |0 | |4 |0 |1 |0 |0 |1 |0 |1 |0 |1 |0 |0 |0 | |5 |0 |0 |1 |1 |0 |0 | 0 |0 | 0 | 0 | 0 |0 | |6 |0 |0 | 0 | 0 | 0 | 0 |0 |1 |0 | 1 | 0 | 1 | |7 |0 |1 |1 |1 |0 |0 | 0 | 0 | 0 | 0 |1 | 1 | |8 |0 |0 |0 | 0 |0 | 1 |0 | 0 |1 |0 |0 |1 | |9 |1 |0 | 0 | 1 |0 | 0 | 0 |1 |0 | 0 | 0 |1 | |10 |0 |0 |1 | 0 | 0 |1 |0 |0 | 0 |0 | 1 |1 | |11 |0 |0 | 0 |0 |0 | 0 |1 | 0 | 0 | 1 |0 |1 | |E |1 |1 | 0 | 0 | 0 | 1 |1 |1 |1 | 1 | 1 |0 | |
c) Quantos caminhos de tamanho 3 existe entre a sala 1 e sala 10?
R: 4 caminhos.

d) É possível, a partir da área externa, atravessar cada uma das portas uma única vez e terminar na área externa? Justifique;
R: Não, pois existem vértices de grau ímpar.

e) Se todas as portas de entre as salas estão destrancadas e somente as pelas portas salas 10 e 9 é possível alcançar a área externa, pergunta-se: a. Por qual sala deve-se começar uma caminhada para atravessar todas as portas destrancadas uma única vez? R: Começar na 2 ou na 3.

b. Qual o caminho a ser percorrido? R: 2 – 1 – 9 – 4 – 7 – 3 – 10 – E – 9 – 8 – 10 – 11 – 7 – 2 – 4 – 5 – 3

2. Indique e justifique qual o grafo é isomorfo ao grafo da questão 1.

a) [pic] b)[pic]

R: É o grafo B. Os graus do grafo B correspondem aos graus do grafo da questão 1.

3. O proprietário das salas deseja pintá-las de tal forma