Revisão Teoria dos Grafos

1) Dado o conceito de grafos abaixo:
"Um grafo G(V, E) é um conjunto V infinito(FINITO), não-vazio de pontos, cujos elementos são chamados de vértices (nodos ou nós), conectados por um conjunto E de linhas, chamada de arestas (ou arcos). Uma aresta é um par DISTINTO não ordenado (vi, vj), onde vi e vj são elementos DISTINTOS de V. "

Diga o que está incorreto na frase e explique por que. (1,0)

Dado o Grafo abaixo:

Responda:

2) Faça o grafo de arestas para o mesmo. (0,5)

3)Sobre ciclo hamiltoniano e ciclo euleriano, marque V no que for verdadeiro e F no que for falso:

( V ) É chamado de ciclo hamiltoniano, o ciclo simples entre todos os vértices de um grafo; (0,5)
( V ) É chamado de ciclo euleriano, o ciclo do trajeto que contém todas as arestas de um grafo; (0,5)
( F ) Um grafo, que contém um caminho euleriano e não possui um ciclo euleriano, é chamado de universal; (0,5)
( F ) É chamado de ciclo hamiltoniano, o ciclo simples entre todos as arestas de um grafo;(0,5)

4) Dado o algoritmo de busca em grafo abaixo:

escolha uma raiz s de G marque s insira s em F enquanto F não está vazia faça seja v o primeiro vértice de F para cada w ∈ listaDeAdjacência de v faça se w não está marcado então visite aresta entre v e w marque w insira w em F senao se w ∈ F entao visite aresta entre v e w fim se fim para retira v de F fim enquanto

Marque a que estiver correta: (1,0)
a) é uma busca em profundidade;
b) é uma busca em largura;
c) é Djkstra
d) é um árvore expandida mínima;

Justifique sua resposta.

5)Dada a definição abaixo: (1,0)

Formalmente, este algoritmo de busca realiza uma busca não-informada que progride através da expansão do primeiro nó filho da árvore de busca, e se aprofunda cada vez mais, até que o alvo da busca seja encontrado ou até que ele se depare com um nó que não