Lista 3 - Grafos

Prévia do material em texto

Professora: Laiane Ricardo Nota: 2.0 
Nome: Judy Ellen Vera Martins 
 
Exercícios 3 
 
 
1(0.33) - Qual é a teoria dos grafos? 
 A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um 
determinado conjunto. Para tal são empregadas estruturas chamadas de grafos, G(V,A), onde V é um 
conjunto não vazio de objetos denominados vértices e A é um conjunto de pares não ordenados de V, 
chamado arestas. 
 
2(0.33)- O que é um grafo? 
 É uma estrutura composta por um conjunto (não vazio) de pontos (vértices) e um conjunto de 
linhas que ligam esses pontos (arestas). 
Definição formal: Um grafo G = (V(G), E(G)) é uma estrutura matemática composta por dois conjuntos: 
-V(G), um conjunto de elementos que são chamados de vértices; 
-E(G), um conjunto de pares de elementos de V(G), cada par é chamado de aresta. 
 
3(0.33)- Cite e descreva três tipos de grafos. 
Simples: grafo sem laços nem arestas múltiplas. 
Trivial: um grafo com apenas um vértice e nenhuma aresta. 
Grafo acíclico: grafo sem ciclos. O exemplo abaixo à esquerda é um grafo acíclico. 
 
4(0.33)- Descreva os dois tipos mais comuns de representação de um grafo. 
A matriz de adjacência de um grafo G = (V, A) contendo n vértices é uma matriz n × n de bits, 
onde A[i, j] é 1 (ou verdadeiro) se e somente se existe um arco do vértice i para o vértice j. Para grafos 
ponderados A[i, j] contém o rótulo ou peso associado com a aresta e, neste caso, a matriz não é de 
bits. É muito útil para algoritmos em que necessitamos saber com rapidez se existe uma aresta ligando 
dois vértices. • A maior desvantagem é que a matriz necessita Ω(|V | 2 ) de espaço. 
Os vértices de uma lista de adjacência são em geral armazenados em uma ordem arbitrária. 
Indicada para grafos esparsos, onde |A| é muito menor do que |V | 2. A principal desvantagem é que 
ela pode ter tempo O(|V |) para determinar se existe uma aresta entre o vértice i e o vértice j, pois 
podem existir O(|V |) vértices na lista de adjacentes do vértice i. 
 
5(0.33)- Descreva abstrações de grafos com tarefas do dia-a-dia. 
Pode ser usado os grafos para modelar mapas rodoviários, onde os vértices representam as 
intersecções e as arestas representam estradas. Arestas não orientadas representam estradas de mão 
dupla, e as arestas orientadas representam estradas de mão única. Arestas não orientadas múltiplas 
representam estradas de mão dupla múltiplas que conectam as mesmas duas intersecções. Arestas 
orientadas múltiplas representam estradas de mão única múltiplas que começam em uma intersecção 
e terminam em outra intersecção. Os grafos mistos são indispensáveis para representar mapas 
rodoviários, já que incluem tanto estradas de mão única como de mão dupla. 
6-(0.35) Cite alguns exemplos de aplicações que utilizam grafos exibidas durante a aula 
síncrona. 
Transporte aéreo (Objeto: cidades, Relacionamento: vôo comercial entre duas cidades); 
Atores e filmes (Objeto: atores, Relacionamento: atores atuaram em um mesmo filme) 
Web: (Objeto: páginas da web, Relacionamento: link de uma página para outra);