3131
ASSUNTO: Árvores e caminho crítico
FICHA DE TRABALHO N.O 4NOME: ___________________________________________________________________________________________________ TURMA: ______________ N.O: ________
1. Dos grafos seguintes, indique os que são árvores:
I II III
IV V VI
2. Considere o grafo seguinte:
2.1 Descreva uma situação do quotidiano que possa ser modelada por este grafo.
2.2 Determine, usando o algoritmo de Kruskal, a árvore abrangente mínima e calcule o seu peso total.
6
13
3
3
7
5
75
46
7621
7
3
59
11
3
43
I
A
B C
D
E
FG
N
L
M
J
H
Matemática Aplicada às Ciências Sociais, 11.o ano – TEXTO
3232
3. Um antigo parque de diversões vai ser reaberto. Existe um pequeno comboio que percorre todo o parque,sobre trilhos (arestas), visitando todos os pontos de interesse (os vértices). Esta situação pode ser representa-da pelo grafo que se segue:
onde os pesos associados às arestas correspondem aos quilómetros entre pontos de interesse.
3.1 Determine quais dos trilhos deverão ser consertados de forma a minimizar os custos e que permite viajarde comboio a qualquer ponto de interesse.
3.2 Quantos quilómetros deverão ser arranjados (na totalidade)?
4. O esquema seguinte representa, através de um digrafo, a planificação de um projeto que envolve a realizaçãode sete tarefas e as respetivas durações (em dias):
4.1 Sintetize a informação fornecida pelo digrafo uma tabela em que constem as tarefas envolvidas e otempo de duração de cada uma, bem como as suas precedências.
4.2 O gestor responsável sabe que o projeto não pode exceder quinze dias, caso contrário terá de pagar aocliente por falta de cumprimento. Será que consegue cumprir o prazo estabelecido?
10
31
64
11
7
12 10
7
75
13
8
88
9
5
5
I
A
B
C DE
F
G
LM
JH
T1
2
T3
6
T5
1
T7
5
T4
4
T6
3
T2
5
Matemática Aplicada às Ciências Sociais, 11.o ano – TEXTO