Logo Passei Direto
Buscar
Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Prévia do material em texto

Lista 1 - TGC
1 - Da teoria dos grafos, apresente a definição de árvore.
Grafo conexo e acíclico
2 - Qual o máximo de arestas possível em uma árvore com 11 vértices?
n-1: 10 arestas
3 - Quantos caminhos existem entre um par de vértices em uma árvore com 9 vértices?
1
4 - Qual o efeito da adição de uma nova aresta em uma árvore, sem alteração do número
de vértices?
Formação de ciclo
5 - Qual o nome atribuído a um conjunto de componentes que atendem às propriedades de
árvores?
Floresta
6 - Dado um grafo G submetido ao algoritmo a seguir, qual propriedade ele passa a
atender?
Enquanto G possui algum ciclo não selecionado anteriormente:
selecione um ciclo;
remova uma das arestas deste ciclo;
Passa a ser uma árvore geradora
7 - Considere o grafo a seguir, aplique o método de Prim para a obtenção de uma árvore
geradora de custo mínimo. 8 - Aplique o método de Kruskal para obtenção de uma árvore
geradora de custo mínimo.
Prim:
1 Adiciona-se a raiz (qualquer vértice);
2 Repete até que todos os vértices sejam adicionados na agm:
3 Adiciona-se a aresta de menor peso adjacente à agm intermediária que
envolve um novo vértice;
Kruskal:
0 Adiciona-se todos os vértices;
1 Ordena-se as arestas e coloca numa fila;
2 Enquanto o número de aresta for menor que n-1
3 Se a aresta não forma ciclo
4 inclui aresta na agm;
5 remove aresta da fila;
9 - Implemente uma forma de encontrar o menor caminho entre dois vértices (a, b) em um
grafo não-ponderado (pseudocódigo).
Busca em Largura:
L: ordem de conhecimento
nível: distância em relação a raiz
pai: conhecido através de quem
Execute o algoritmo de busca em largura a partir de a.
Retorne o valor de nível associado ao vértice b.
10 - A solução do exercício anterior retornará um caminho em um grafo ponderado?
Sim. Não garante que será mínimo.
11 - Apresente a definição de corte em grafo não direcionado.
Dado um grafo G e um subconjunto de vértices S, tal que os vértices de S são
vértices de G, um corte é um subconjunto de arestas tal que apenas uma das extremidades
das arestas está em S.
12 - Apresente a definição de corte em grafo direcionado.
Dado um grafo direcionado, um corte é um subconjunto de arestas com origem em
um subconjunto de vértices e o destino não.
13 - Considere o grafo do exercício 7, aplique o método de Dijkstra para identificar o menor
caminho entre o vértice 0 e o vértice 2.
Dijkstra:
Adiciona a raiz;
Para cada vértice que não seja a raiz:
Encontra a aresta do corte tal que dist[v] + distância da aresta seja
mínimo
Atualiza a distância, predecessor e subconjunto para verificação do
corte;
14 - Considere o grafo a seguir, aplique o método de Bellman-ford para identificar o menor
caminho entre o vértice 0 e o vértice 2.
15 - Cite circunstâncias em que seria melhor escolher cada um dos algoritmos de caminho
mínimo conhecidos na disciplina.
Dijkstra: pesos positivos, menor caminho e o tamanho do menor caminho entre 1 vértice e
os demais;
Bellman-ford: pesos negativos, menor caminho e o tamanho do menor caminho entre 1
vértice e os demais;
Floyd-warshall: descobrir o tamanho do menor caminho de todos os vértices para todos os
vértices.
E se eu quiser o menor caminho de todos os vértices para todos os vértices?
Executar n vezes Dijkstra (se pesos positivos) ou bellman-ford (se pesos negativos)
16 - Quais as características de um grafo que representa uma rede de fluxo em termos dos
vértices, arestas e seus atributos?
Existem 2 vértices especiais, source (s) e terminal(t) tal que não há arestas entrando
em s nem arestas saindo de t. Os vértices que não são source ou terminal são vértices
internos. A cada aresta está associada uma capacidade, que limita o fluxo por aquela
aresta.
17 - O que é um fluxo?
Fluxo é um valor não negativo associado a cada aresta que atende à condição de
capacidade e à condição de conservação.
a) Capacidade: é menor ou igual à capacidade da aresta.
b) Conservação: para todo vértice interno, o fluxo que entra é igual ao fluxo que sai.
18 - Defina o problema do fluxo máximo.
O problema do fluxo máximo consiste em descobrir o maior fluxo viável entre a fonte
s e o terminal t.
19 - Explique, com suas palavras, o teorema do fluxo máximo e corte mínimo.
O teorema do fluxo máximo e corte mínimo diz que, em qualquer rede de fluxo, o
valor do fluxo máximo entre s e t é igual à capacidade do menor corte s-t da rede.
20 - Diferencie o algoritmo de Ford-fulkerson do algoritmo de Edmonds-karp.
O algoritmo de edmonds-karp implementou uma melhoria no algoritmo de
ford-fulkerson ao evitar tantas repetições quanto o tamanho fluxo máximo. A medida para a
melhoria é, ao invés de selecionar qualquer caminho aumentante, concentrar-se no que
possui o menor número de arestas utilizando para tal a busca em largura.

Mais conteúdos dessa disciplina