WorksheetsAlgoritmos
Total questions: 14
Worksheet time: 19mins
O que define um grafo como hamiltoniano?
Se todos os vértices possuem o mesmo grau.
Se todos os vértices possuem grau par.
Se existe um caminho que passa por todos os vértices exatamente uma vez.
Se existe um ciclo que passa por todos os vértices exatamente uma vez.
Algoritmo que garante encontrar um caminho entre dois vértices em um grafo:
(a)
Quais os 2 teoremas mais famosos dentro do assunto Grafos Hamiltonianos?
Teorema de Ore
Teorema de Newton
Teorema de Euler
Teorema de Dirac
A busca em largura é um algoritmo que utiliza uma abordagem de "exploração em profundidade"
Verdadeiro
Falso
A busca em largura pode ser implementada em Python utilizando uma fila para armazenar os vértices a serem explorados.
Verdadeiro
Falso
Para um grafo ser Hamiltoniano ele precisa essencialmente conter:
Um ciclo Hamiltoniano
Um caminho Hamiltoniano
A busca em largura é um algoritmo guloso.
Verdadeiro
Falso
Considerando o seguinte caso fictício:
Gustavo, trabalhador do IBGE, precisa visitar algumas casas (vértices) para realizar registros.
Sendo sua casa o vértice 1, sua rota pode ser considerada hamiltoniana?
Sim
Não
Existe um ciclo Hamiltoniano no grafo? Se sim, indique-o no desenho.
Este é um grafo hamiltoniano?
Sim
Não
Por que a busca em largura é considerada um algoritmo de "exploração em largura"?
Porque prioriza a exploração dos vértices mais profundos primeiro
Porque prioriza a exploração dos vértices mais próximos primeiro
Busca em Largura é ineficiente em grafos grandes ou profundos.
Verdadeiro
Falso
A Busca em Largura é um algoritmo de busca informada, uma vez que usa informação para direcionar a busca.
Verdadeiro
Falso
A Busca em Largura pode ser usada como uma técnica de busca para resolver problemas, como encontrar a solução para um quebra-cabeça ou encontrar o objetivo em um jogo.
Verdadeiro
Falso
