Lista de Exercícios 01 - Otimização de Redes

Universidade Federal do Sul da Bahia Campus Jorge Amado Itabuna BA Otimização de Redes 20233 Lista de Exercícios 01 Professor Edcarllos Santos Assuntos Introdução aos Grafos Caminhos Conexidade Problemas Relacionados a Caminhos Algoritmos para Caminho Mínimo Entrega Até o dia 24112023 às 23h59 apenas pelo SIGAA Valor 100 pontos peso 30 Instruções Esta lista de exercícios contém seis questões Leia com atenção os enunciados pois a interpretação faz parte da proposta A lista deve ser resolvida individualmente trabalhos copiados terão desconto As respostas devem ser detalhadas apresentando todos os passos necessários para a resolução incluindo os valores das variáveis em cada iteração Q1 15 pontos Para o grafo da figura abaixo apresente a sequência de vértices após a aplicação da BFS a partir do vértice 7 Apresente o passo a passo do algoritmo Q2 15 pontos Para o grafo da figura abaixo apresente a sequência de vértices após a aplicação da DFS a partir do vértice 7 Apresente o passo a passo do algoritmo Q3 10 pontos Elabore um exemplo de um grafo com seis nós em que o caminho mais curto entre os vértices 1 e 6 somente poderá ser calculado pelo algoritmo de BellmanFord Justifique o exemplo Q4 30 pontos A tabela abaixo fornece os pesos comprimentos wx y dos arcos em um gráfico direcionado x corresponde à linha e y à coluna a Execute passo a passo o algoritmo de BellmanFord para determinar o caminho mais curto de A a C ou um circuito negativo se tal caminho não existir b Execute passo a passo o algoritmo FloydWarshall para determinar o caminho mais curto de A a C ou um circuito negativo se tal caminho não existir Q5 20 pontos Execute passo a passo o algoritmo de Dijkstra para determinar especificamente o menor caminho entre os vértices a e m do grafo abaixo Q6 10 ponto Sobre o grafo G abaixo responda a Apresente os três vértices de maior grau b Determine a lista de adjacência c Determine a matriz de adjacência d Determine a matriz de incidência