Lab 04 - Grafos (1)

Prévia do material em texto

Roteiro para a aula de laboratório de Grafos
Baixar no SIGAA os slides de aula e ler o conteúdo da aula para apoio aos exercícios. Essa
atividade valerá nota e contará como uma atividade de implementação da unidade 1.
Atividade 4
Ler os slides de aula “Aula 6 - Subgrafos, Contração de Vértices e Arestas”
As funções abaixo devem ser adicionadas na sua biblioteca básica de grafos. Todas as
funções devem ser feitas somente para a Estrutura de Adjacência.
Exercício 4.1
Implementar uma função na sua biblioteca de grafos que retorna um subgrafo a partir de um
grafo previamente instanciado.
A função deve retornar uma nova instância do grafo.
Recebe como parâmetro um conjunto de vértices e um conjunto de arestas. Os vértices
podem ser definidos pelo índice deles na estrutura de adjacências e as arestas podem ser
definidas como um par de vértices.
A função deve retornar um subgrafo com os vértices e arestas passados como parâmetro.
Fiquem atentos na definição de subgrafo para implementar a função corretamente.
Exercício 4.2
Implementar a função de subgrafo induzido. A função deve receber como parâmetro um
conjunto X de vértices e retornar o subgrafo G[X].
Exercício 4.3
Implementar a função de subtração de vértices. A função deve receber como parâmetro um
conjunto X de vértices e implementar a operação G - X.
Exercício 4.4
Implementar a função de subgrafo aresta-induzido A função deve receber como parâmetro
um conjunto E de arestas e retornar o subgrafo aresta-induzido G[E]
Exercício 4.5
Implementar a função de subtração de arestas. A função deve receber como parâmetro um
conjunto E de vértices e implementar a operação G - E.
Exercício 4.6
Carregar o grafo abaixo e gerar os seguintes exemplos:
a) Gerar um subgrafo próprio
b) Gerar um subgrafo gerador
c) Seja X1 = {y, v, x, u}, gerar o subgrafo induzido G[X1]
d) Seja X2 = {u,w}, gerar G-X
e) Seja E1 = {a,c,e,g}, gerar o subgrafo aresta-induzido G[E1]
f) Seja E2 = {a,b,f}, gerar G-E2