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.