Lista 3

Prévia do material em texto

Lista 3 – Grafos 
 
1. Desenhe com 5 nós que seja um grafo simples, direcionado, 
rotulado, que possua um nó isolado e pelo menos um nó de grau 
3. 
 
 
2. Desenhe um grafo simples e completo com 5 nós, ou seja, um k5 
 
3. Desenhe um grafo com ciclos de comprimento 1, 3, 5 
 
 
4. Desenhe um grafo bipartido completo K1,4 
 
 
5. Os grafos a seguir são isomorfos? Explique sua resposta: 
 
6. Um não é um grafo planar, demostre por que, baseado no 
teorema de Euler: 
 
 
7. A tabela a seguir representa as tarefas para construir uma casa de 
madeira: 
 
TAREFAS PRÉ – REQUISITOS DIAS 
1 – Limpeza do terreno Nenhum 4 
2 – Fundação 1 3 
3 – Estrutura 2 7 
4 – Telhado 3 6 
5 – Tábuas externas 3 4 
6 – Encanamento e fiação 4 e 5 6 
7 – Colocação janelas e portas 3 5 
8 – Instalação de janelas e portas 6 5 
9 – Pintura 7 e 8 5 
 
a)Construa um grafo a partir das tarefas da construção 
b)Determine o tempo mínimo para construir a casa; 
c)Forneça o caminho crítico. 
 
8. Considere o grafo 
 
 
 
a. Encontre dois vértices que não sejam adjacentes. 
b. Encontre um vértice que seja adjacente a ele mesmo. 
c. Encontre um laço. 
d. Encontre duas arestas paralelas. 
e. Encontre o grau do vértice 3. 
f. Encontre um caminho de comprimento 5. 
g. Encontre um ciclo. 
h. Este grafo é completo? 
i. Este grafo é conexo? 
j. 
9. 𝑘5 é um grafo conexo simples com cinco vértices (e 10 arestas). 
Ele é planar? 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
10. Nos exercícios a seguir, verifique se os grafos são isomorfos. Se 
forem, forneça a bijeção (no caso de grafos simples) ou bijeções 
que estabelecem o isomorfismo. Se não forem, explique por quê.