Logo Passei Direto
Buscar

Exercícios sobre Grafos

User badge image
Mirelly

em

Ferramentas de estudo

Questões resolvidas

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

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

Questões resolvidas

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.

Mais conteúdos dessa disciplina