Upload
narcisa-alexandra-filipe
View
214
Download
0
Embed Size (px)
Citation preview
7/23/2019 11ft4
http://slidepdf.com/reader/full/11ft4 1/2
ASSUNTO: Árvores e caminho crítico
FICHA DE TRABALHO N.O 4
NOME: ___________________________________________________________________________________________________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
7 5
46
7
621
7
3
59
11
3
4
3
I
A
B C
D
E
F
G
N
L
M
J
H
Matemática Aplicada às Ciências Sociais, 11.o ano – TEXTO
7/23/2019 11ft4
http://slidepdf.com/reader/full/11ft4 2/2
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 viajar
de 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ção
de 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 o
tempo 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 ao
cliente por falta de cumprimento. Será que consegue cumprir o prazo estabelecido?
10
3 1
6
4
11
7
12 10
7
7
5
13
8
8
8
9
5
5
I
A
B
C D
E
F
G
L M
J H
T 1
2
T 3
6
T 5
1
T 7
5
T 4
4
T 6
3
T 2
5
Matemática Aplicada às Ciências Sociais, 11.o ano – TEXTO