Lista de Exercícios 4

Prévia do material em texto

Professora: Laiane Ricardo Nota: 2.0 
Nome: Judy Ellen Vera Martins 
 
Atividades – Grafos 
 
1 – Defina Grafo: 
 
2- Existem diversas especialidades de grafos, defina cada um: 
 
a) b) 
 
 
 
 
 
 
 
 
 
 
 
 
 
c) 
d) 
 
 
 
 
 
 
 
 
 
 
 
 
e) f) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Optei em por as respostas ao final 
da atividade, por conta da questão 
número dois que ao responder saiu 
da formatação. 
g) h) 
 
 
 
 
 
 
 
 
 
 
 
 
i) 
 
 
 
 
 
 
 
 
 
 
 
 
 
3- Cite aplicações em que possam ser usados a teoria de grafos: 
 
4 – Como os grafos podem ser representados computacionalmente? 
 
5 – Explique as duas estratégias usadas para percorrer grafos e ainda dê a 
definição de caminho: 
 a)Busca em largura (BFS – Breath- First-Search) 
 b)Busca em profundidade (DFS – Depth-First-Search). 
 c) Caminho: 
 
6 – Relacione a figura com sua respectiva estratégia: 
 
a) b) 
 
 
 
 
 
 
 
 
 
 
 
 ( ) DFS-Busca em Profundidade ( ) BFS - Busca em Largura 
7- O que é necessário para produzir a ordenação topológica? 
 
8- Como Funciona o algoritmo de Dijkstra? 
 
 
RESPOSTAS 
 
1- É uma estrutura composta por um conjunto (não vazio) de pontos, os vértices, e 
um conjunto de linhas que ligam esses pontos, as arestas 
 
2- 
a. Grafo Acíclico 
b. Grafo simples 
c. Subconjunto Internamente Estável 
d. Grafo direcionado 
e. Grafo fortemente conexo. 
f. Sub-grafo 
g. Grafo não Direcionado 
h. Grafo conexo. 
i. 
 
3- Grade escolar, Robustez da malha elétrica, Transporte aéreo entre outros. 
 
4- Em forma de matriz adjacente e de lista adjacente. 
 
 
5- 
a. BFS - é um algoritmo que percorre o grafo pelos nós de um vértice e outro. 
Após visitar o primeiro, o mesmo percorre os nós até seu último, marcando 
cada um por que passa. Cada nó só pode ser percorrido uma vez. Sempre 
que acha a saída provavelmente será a mais curta. 
 
b. DFS – é um algoritmo que também visita todos os vértices e nós do grafo 
com uma certa ordem, verticalmente, e atribui um número para cada vértice 
visitada. Sempre que acha a saída não será necessariamente a menor. 
 
c. Um caminho em um grafo é uma sequência de vértices. Um caminho que 
não passa duas vezes no mesmo vértice é um caminho simples, o que não 
tem duas vezes a mesma aresta é um trajeto e o caminho onde o primeiro 
vértice é igual o último é denominado circuito, mas o que não repete o a 
vértice um ciclo. 
 
6- (a) DFS-Busca em Profundidade (b) BFS - Busca em Largura 
 
7- A implementação dos algoritmos de busca. 
 
8- O algoritmo de Dijkstra soluciona o problema do caminho mais curto de um grafo 
direcionado com arestas de peso não negativo. Ele constrói a STP uma aresta por 
vez, primeiramente adiciona um nó de origem a aresta que gera o caminho mais 
curto do nó de origem ao nó ainda não presente da STP. Este algoritmo roda até 
que todos os nós tenham sido visitados. Então a STP já contém o caminho mais 
curto e todos os demais visitados entre o processo.