Prévia do material em texto
Você acertou 10 de 10 questões Verifique o seu desempenho e continue treinando! Você pode refazer o exercício quantas vezes quiser. Verificar Desempenho A B C D E A B 1 Marcar para revisão A topologia de um grafo é muito importante para a criação de um modelo de uma rede. Os grafos completos têm uma particularidade especial em relação à topologia. O que é um grafo completo? Um grafo no qual todos os vértices têm o mesmo grau. Um grafo com um número par de vértices e uma quantidade igual de arestas. Um grafo sem arestas múltiplas ou loops. Um grafo no qual todas as arestas têm a mesma orientação. Um grafo no qual todos os vértices são adjacentes entre si. Resposta correta Parabéns, você selecionou a alternativa correta. Confira o gabarito comentado! Gabarito Comentado Um grafo completo é definido como um grafo no qual todos os vértices são adjacentes entre si. Ou seja, cada vértice do grafo está ligado a todos os outros vértices do mesmo grafo. 2 Marcar para revisão Considera-se que o problema original da teoria dos grafos foi o das pontes de Königsber, resolvido por Euler. Qual foi a solução encontrada por Euler para o problema das sete pontes de Königsberg? A construção de mais pontes para possibilitar o percurso desejado. A remoção de algumas pontes para simplificar o problema. Questão 1 de 10 Corretas (10) Em branco (0) 1 2 3 4 5 6 7 8 9 10 Lista de exercícios Conceitos Básicos Em Grafos Sair C D E A B C D E A conclusão de que o problema não tinha solução. A utilização de um algoritmo para encontrar o caminho desejado. A determinação de múltiplas soluções para o problema proposto. Resposta correta Parabéns, você selecionou a alternativa correta. Confira o gabarito comentado! Gabarito Comentado Euler provou que o problema não tinha solução, pois cada ilha ou margem possuía uma quantidade ímpar de pontes, o que tornava impossível realizar o percurso sem repetir pontos. 3 Marcar para revisão Podemos representar um grafo através de uma matriz, existe mais de uma representação matricial. Qual é uma das principais estruturas de matrizes utilizadas para representar um grafo? Matriz de orientação. Matriz de conectividade. Matriz de adjacências. Matriz de interação. Matriz de cardinalidade. Resposta correta Parabéns, você selecionou a alternativa correta. Confira o gabarito comentado! Gabarito Comentado Uma das principais estruturas de matrizes utilizadas para representar um grafo é a Matriz de Adjacências, que descreve a relação de adjacência entre os vértices do grafo. 4 Marcar para revisão Dada a matriz de adjacências abaixo, assinale a opção que apresenta corretamente as informações sobre o grafo registrado na matriz: A B C D E A B C D E O grafo possui 5 vértices e a presença de zeros na sua diagonal principal indica que é um multigrafo. O grafo possui 5 vértices e apresenta o vértice 1 adjacente aos vértices 2, 3 e 4 O grafo é simples e o vértice 5 apresenta grau 2. O grafo é direcionado e por isso a sua matriz de adjacências é simétrica O grafo é simples e completo Resposta correta Parabéns, você selecionou a alternativa correta. Confira o gabarito comentado! Gabarito Comentado A matriz formada por zeros na diagonal principal indicando que este grafo não possui laços em nenhum vértice. Como a matriz é formada somente por 0 e 1, trata-se de um grafo simples e somando os valores da coluna 5, vemos que o grau do vértice 5 é igual a 2. 5 Marcar para revisão Matrizes de adjacências e listas de adjacências são os métodos mais comuns de representação de um grafo em memória. Qual é uma das principais vantagens das listas de adjacências em relação à matriz de adjacências na representação de grafos? Melhor desempenho em grafos densos. Melhor desempenho em grafos pequenos. Menor complexidade de tempo para determinar a existência de uma aresta. Menor complexidade espacial para grafos completos. Melhor representação de valores associados às arestas. Resposta correta Parabéns, você selecionou a alternativa correta. Confira o gabarito comentado! Gabarito Comentado A B C D E A B C D E Uma das principais vantagens das listas de adjacências é a menor complexidade de tempo para determinar a existência de uma aresta entre dois vértices, que pode ser O(n) no pior caso, em comparação com O(1) na matriz de adjacências. 6 Marcar para revisão Usamos a complexidade de espaço para estimar a quantidade de memória usada para representar um determinado dado em memória durante seu processamento. Qual é a complexidade espacial de uma lista de adjacências para representar um grafo com 𝑛 vértices e m arestas? O(n). O(m). O(n+m). O(n x m). O (1). Resposta correta Parabéns, você selecionou a alternativa correta. Confira o gabarito comentado! Gabarito Comentado A complexidade espacial de uma lista de adjacências é O(n+m), onde n é o número de vértices e M é o número de arestas do grafo. 7 Marcar para revisão O problema original da teoria dos grafos, as pontes de Königsberg, mostrou a importância dos caminhos em grafos. Os ciclos são caminhos com características especiais. Como é definido o grafo ciclo? Um grafo que possui uma única aresta. Um grafo que consiste em um único ciclo, com um número de vértices conectados em uma rede fechada. Um grafo com todos os vértices conectados entre si. Um grafo que possui mais de uma aresta interligando o mesmo par de vértices. Um grafo que não possui vértices adjacentes. A B C D E A B Resposta correta Parabéns, você selecionou a alternativa correta. Confira o gabarito comentado! Gabarito Comentado O grafo ciclo é definido como um grafo que consiste em um único ciclo, ou seja, um número de vértices conectados em uma rede fechada, onde o número de vértices é igual ao número de arestas. 8 Marcar para revisão A complexidade de tempo e espaço são métricas importantes na avaliação da representação e no tratamento de dados por algoritmos. Neste contexto, qual é a principal desvantagem da representação matricial de um grafo? Complexidade de implementação. Dificuldade na análise de conectividade. Espaço de armazenamento excessivo. Limitação na representação de grafos não direcionados. Falta de precisão na descrição das arestas. Resposta correta Parabéns, você selecionou a alternativa correta. Confira o gabarito comentado! Gabarito Comentado A principal desvantagem da representação matricial de um grafo, seja por matriz de adjacências ou matriz de incidência, é o espaço de armazenamento excessivo, especialmente quando o grafo é esparso, ou seja, possui muitos vértices e poucas arestas. Isso ocorre porque mesmo os elementos da matriz que representam a ausência de conexão (0) precisam ser armazenados. 9 Marcar para revisão Você já ouviu falar em multiconjuntos? É um conceito fundamental para definir o que é um multigrafo. O que é um multigrafo? Um grafo que contém vértices com diferentes graus. Um grafo que possui mais de uma aresta interligando o mesmo par de vértices. C D E A B C D E Um grafo que não possui arestas múltiplas ou loops. Um grafo no qual todas as arestas têm a mesma orientação. Um grafo que possui apenas vértices de grau ímpar. Resposta correta Parabéns, você selecionou a alternativa correta. Confira o gabarito comentado! Gabarito Comentado Um multigrafo é um grafo que possui mais de uma aresta interligando o mesmo par de vértices, ou seja, permite arestas múltiplas ou paralelas entre os vértices. 10 Marcar para revisão Euler foi um dos matemáticos mais importantes, deixou contribuições na geometria, cálculo e é considerado o pai da teoria dos grafos. Qual das seguintes afirmações melhor descreve uma das lições deixadas por Euler ao resolver o problema das sete pontes? É essencial considerar todos os detalhes irrelevantes ao criar um modelo matemático. Modelos matemáticos complexos são necessários para resolver problemas simples. Os modelos matemáticos devem representar fielmentetodos os aspectos do problema real. A simplificação da realidade por meio de modelos é útil para a compreensão e resolução de problemas. A representação gráfica de problemas é desnecessária para a resolução de problemas matemáticos. Resposta correta Parabéns, você selecionou a alternativa correta. Confira o gabarito comentado! Gabarito Comentado Euler demonstrou a importância de criar modelos simplificados que representassem fielmente as características essenciais do problema real, sem se preocupar com detalhes irrelevantes.