GRAFOS- Ficha 1
1. Considera o seguinte grafo e indica:
1.1. As arestas paralelas; 1.2.
Dois vértices adjacentes.
1.3. Um lacete;
1.4. Um vértice de grau 4;
1.5. Um vértice terminal;
1.6. Uma ponte;
1.7. Duas arestas não adjacentes.
1.8. Um caminho que comece em B e
termine H e contenha o vértice A
2. Indique, justificando, o valor lógico das seguintes afirmações:
(A) Um grafo completo com cinco vértices tem seis arestas.
(B) Um grafo conexo admite um circuito de Euler se e só se contém, no máximo, dois vértices de grau
ímpar.
3. No grafo ao lado os vértices representam alunos. Cada aresta
liga dois alunos que têm pelo menos uma disciplina em comum.
3.1. O Jorge e a Cristina têm 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 não? O que significa no contexto do problema?
3.5. Eulerize o grafo e indique um circuito de Euler.
4. A Sara e o João abriram uma conta poupança-habitação nas seguintes condições:
▪ 1000 euros de capital inicial:
▪ depósitos trimestrais, a partir do final do 1º trimestre, de 500 euros; ▪ taxa de
juro 1,5% capitalizado trimestralmente.
4.1. O capital acumulado ao fim de dois anos. Apresenta todos os cálculos efetuados.
4.2. Se para comprar uma casa é necessário ter, pelo menos, 6 000 euros na conta, quantos
anos devem decorrer desde o primeiro depósito até que tal aconteça?
5. A cadeia de lojas
A cadeia de lojas de roupa NOVAMODA, com sede em Lisboa, abriu cinco surcusais nas capitais
de distrito do Sul do país. A recente certificação da empresa obriga a que quinzenalmente o
diretor de Qualidade saia da sede e visite todas as filiais. A tabela seguinte representa as
respetivas distâncias:
5.1. Quantos circuitos poderá o diretor de Qualidade utilizar para visitar todas as sucursais?
5.2. Utlize o algoritimo da “cidade mais próxima” de modo a aconselhar o diretor de
Qualidade
sobre o melhor trajeto a realizar.
5.3. Encontre a árvore geradora mínima do grafo correspondente à tabela.
5.4. Suponha que em determinada semana o diretor de Qualidade teve de se deslocar
diretamente de Lisboa a Évora devido a uma emergência. Utilize o algoritmo da
“cidade mais próxima”
para a definição do resto do trajeto a aconselhar.
5.5. Critique o resultado anterior e as escolhas efetuadas tendo por base o algoritmo da
“cidade mais próxima”.