Revisão Teoria dos Grafos

Páginas: 2 (447 palavras) Publicado: 20 de outubro de 2014
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 Ede 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 Fno 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 asarestas 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 entretodos 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 primeirové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
senaose 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 buscanã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...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • A teoria dos Grafos
  • Teoria Grafos
  • Teoria dos Grafos
  • teoria dos grafos
  • Teoria dos grafos
  • Teoria dos grafos
  • Teoria de Grafos
  • Teoria Dos Grafos

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!