ExerciciosResolvidos

EXERCÍCIOS RESOLVIDOS DE TEORIA DOS GRAFOS
1.) Considere a tabela de tarefas a seguir para a construção de uma casa de madeira:
TAREFAS
1. Limpeza do terreno
2. Produção e colocação da fundação
3. Produção da estrutura
4. Colocação do telhado
5. Colocação das tábuas externas
6. Instalação do encanamento e fiação
7. Colocação das janelas e portas
8. Instalação das janelas e portas
9. Pintura do interior

PRÉ-REQUISITOS
Nenhum
1
2
3
3
4e5
3
6
7e8

DIAS
4
3
7
6
4
6
5
5
5

a) Construa o diagrama PERT;
b) Determine o tempo mínimo para construir a casa;
c) Forneça o caminho crítico.

SOLUÇÃO
a)
5(4)

6(6)

3(7)
8(5)
1(4)

2(3)

4(6)

9(5)
7(5)

b)

TAREFA 1:
TAREFA 2:
TAREFA 3:
TAREFA 4:
TAREFA 5:
TAREFA 6:
TAREFA 7:
TAREFA 8:
TAREFA 9:

4 dias
3 + 4 = 7 dias
7 + 7 = 14 dias
14 + 6 = 20 dias
14 + 4 = 18 dias max (TAREFA 4, TAREFA 5) + TAREFA 6 = 20 + 6 = 26 dias
14 + 5 = 19 dias
26 + 5 = 31 dias max (TAREFA 7, TAREFA 8) + TAREFA 9 = 31 + 5 = 36 dias.

c) Percorrendo o diagrama PERT em ordem inversa e selecionando em cada ponto com mais de um pré-requisito o nó que contribui com o maior valor, resulta:
1–2–3–4–6–8–9
1

2.) Considere o grafo:
4
a4

a3 a5 3

5 a6 a2

7

2 a7 a1
6
1

e responda as seguintes perguntas:
a) O grafo é simples?
b) O grafo é completo?
c) O grafo é conexo?
d) É possível encontrar dois caminhos do nó 3 para o nó 6?
e) É possível encontrar um ciclo?
f) É possível encontrar um arco cuja remoção transforma o grafo em um grafo acíclico?
g) É possível encontrar um arco cuja remoção transforma o grafo em um grafo não-conexo?
SOLUÇÃO
a) Sim.
b) Não. Os nós 5 e 7, por exemplo, não são adjacentes.
c) Sim.
d) Sim: 1º caminho: 3 – a 5 – 5 – a 6 – 6 e 2º caminho: 3 – a 3 – 4 – a 4 – 5 – a 6 – 6.
e) Sim: 3 – a 3 – 4 – a 4 – 5 – a 5 – 3.
f) Sim: a 5.
g) Sim: a 7, por exemplo.
3.) Esboce um grafo com as seguintes características:
a) simples com 3 nós, cada um com grau 2;
b) 4 nós e ciclos de comprimento 1, 2, 3 e 4;
c) não completo com 4 nós, cada um com grau