Ae Macs11 Ava Fa 1

DOSSI DO PROFESSOR MACS 11
AVALIAO
FICHA DE AVALIAO 1 Durao do Teste: 90 minutos
NOME N. TURMA DATA AVALIAO PROFESSOR
Leia atentamente as situaes apresentadas e as questes formuladas.

Responda construindo frases completas onde evidencie o seu raciocnio, os clculos que efetuou e, quando oportuno,
a sua opinio.
1. Considere o grafo ao lado.

D exemplo de um ciclo de Hamilton que contenha as arestas BD
e EC.
2. Indique, justificando, o valor lgico das seguintes afirmaes:

(A) Um grafo completo com cinco vrtices tem seis arestas.
(B) Um grafo conexo admite um circuito de Euler se e s se contm, no mximo, dois vrtices de grau
mpar.
3. No grafo ao lado os vrtices representam alunos. Cada aresta liga dois

alunos que tm pelo menos uma disciplina em comum.
3.1. O Jorge e a Cristina tm alguma disciplina em comum? Justifique.
3.2. Qual o aluno que tem mais disciplinas em comum com os restantes?
3.3. Existe algum aluno sem disciplinas em comum com os demais?
3.4. Trata-se de um grafo conexo ou no? O que significa no contexto do problema?
4. A figura mostra um conjunto de pontes a ligar diversas ilhas entre si e s margens de um rio. A Maria,
que se encontra no local A, queria realizar um percurso por todas as pontes sem repetir nenhuma,
regressando ao local de onde partiu, mas no tem a certeza se tal possvel.
Numa pequena composio ajude a Maria a saber se tal percurso possvel ou no deve incluir os
seguintes aspetos:
representar a situao por um grafo;
referir se possvel passar por todas as pontes sem repetir nenhuma, comeando e terminando em A;
fornecer a soluo mais eficaz se o ponto anterior no for possvel;
indicar um percurso que em qualquer dos casos, a Maria dever realizar.
1
Areal Editores
AVALIAO
5. Uma carrinha tem de ir buscar clientes ao Aeroporto e distribu-los por cinco hotis, regressando ao
local de partida (aeroporto) no final da distribuio. As distncias esto dadas, em km, na tabela
seguinte:
H1 H2 H3 H4 H5
AEROPORTO 18 14 17 20 17
H1 - 9 19 21 15
H2 - - 13 24 22
H3 - - - 12 23
H4 - - - - 16
5.1. Por questes logsticas, a distribuio deve passar em primeiro lugar por H2 e de seguida H1 antes
de ir aos outros hotis.
Indique todos os percursos possveis obedecendo a este critrio e as distncias percorridas em
cada um deles.
5.2. Um dos motoristas da empresa afirma que a distribuio que percorre a menor distncia possvel
a obtida pelo algoritmo do vizinho mais prximo. Averigue se o motorista tem razo.
Na sua resposta, deve:
aplicar ao grafo que represente a situao, o algoritmo proposto pelo motorista;
determinar a distncia obtida pelo algoritmo;
comparar com os resultados obtidos na alnea anterior;
apresentar uma concluso.
6. Uma pequena companhia pretende ligar por cabo de fibra tica os edifcios das suas sedes
espalhadas por vrios quarteires. Pretende-se garantir o envio de mensagens entre qualquer par de
locais. Logo que o cabo esteja colocado, h de ser possvel enviar e receber mensagens para todos
os locais via cabo, muito embora nem todos os pares de stios estejam diretamente ligados. Os locais
esto representados por letras e os nmeros representam os custos em milhares de euros da
instalao do cabo onde possvel. A tabela indica quais as ligaes possveis:
A B C D E F
A 2 5 18
B 2 6 3 1
C 6 16
D 3 16 9 4
E 5 1 9 20
F 18 4 20
6.1. Modele a situao atravs de um grafo pesado.

6.2. D exemplos de duas instalaes diferentes que satisfaam as necessidades de a companhia ter
as suas sedes ligadas por cabo de fibra tica e refira o custo de cada uma delas.
6.3. Procure a instalao mais econmica para os objetivos pretendidos. No grafo, assinale as arestas
que lhe permitem obter a instalao mais econmica.
Explique o mtodo utilizado, bem como o motivo pelo qual muitas das ligaes no precisam de ser
usadas.
2
Areal Editores
AVALIAO
FIM
FORMULRIO
MODELOS DE GRAFOS
Condio necessria e suficiente para que um grafo conexo admita circuitos de Euler
Um grafo conexo admite circuitos de Euler se e s se todos os seus vrtices forem de grau par.
ALGORITMO DO VIZINHO MAIS PRXIMO

1. Escolher um vrtice para ponto de partida.
2. A partir desse vrtice escolher uma aresta com o menor peso possvel que ligue a um dos vrtices adjacentes
ainda no visitados (se houver mais do que uma hiptese escolher aleatoriamente).
3. Continuar a construir o ciclo, partindo de cada vrtice para um vrtice no visitado segundo a aresta com menor
peso.
4. Do ltimo vrtice no visitado, regressar ao ponto de partida.
ALGORITMO DAS ARESTAS ORDENADAS

1. Ordenam-se as arestas por ordem crescente dos seus pesos.
2. Selecionam-se, sucessivamente, as arestas de menor peso que verifiquem as condies seguintes:
um vrtice nunca poder aparecer 3 vezes;
nunca se fecha um circuito havendo vrtices por visitar.
3. Ordena-se a soluo consoante o vrtice de partida escolhido.
ALGORITMO DE KRUSKAL
1. Escolher a aresta com o menor peso.
2. Escolher a aresta seguinte com o menor peso, desde que essa aresta no forme ciclos.
3. Repetir o ponto anterior at que todos os vrtices faam parte da rvore, tendo em conta que:
se houver empate na escolha das arestas, seleciona-se a aresta aleatoriamente;
se a aresta a escolher fechar um ciclo, essa aresta no deve ser considerada.
COTAES
1. 2. (A) 2. (B) 3.1. 3.2. 3.3. 3.4. 4. 5.1. 5.2. 6.1. 6.2. 6.3. Total
15 10 10 6 6 6 12 45 25 20 10 15 20 200
3
Areal Editores

Ae Macs11 Ava Fa 1

Enviado por

Direitos autorais:

Formatos disponíveis

Ae Macs11 Ava Fa 1

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Ae Macs11 Ava Fa 1

Enviado por

Direitos autorais:

Formatos disponíveis

DOSSI DO PROFESSOR MACS 11

NOME N. TURMA DATA AVALIAO PROFESSOR

Leia atentamente as situaes apresentadas e as questes formuladas.

1. Considere o grafo ao lado.

2. Indique, justificando, o valor lgico das seguintes afirmaes:

3. No grafo ao lado os vrtices representam alunos. Cada aresta liga dois

6.1. Modele a situao atravs de um grafo pesado.

ALGORITMO DO VIZINHO MAIS PRXIMO

ALGORITMO DAS ARESTAS ORDENADAS

Você também pode gostar