AVDS GRAFOS

Prévia do material em texto

1. Ref.: 6119790 
 
 
Um caminho em um grafo G=(V,E) é a sequência de vértices P v1,vk = v_1,v_2,v_3, ..., vk tal que 
(vn,vn+1) )∈ E, n < K. 
I - P v1,vk é chamado de ciclo se v1=vk. 
II - Um caminho P v1,vk é denominado caminho simples se vi ≠vj,∀ i, j < K 
III - Não existe correlação entre caminho e ciclos. 
 
 
 
Todas são verdadeiras. 
 
Todas são falsas. 
 Somente I e II são verdadeiras. 
 
Somente I é verdadeira. 
 Somente III é verdadeira. 
Respondido em 02/12/2022 19:51:56 
 
 
 2. Ref.: 6119936 
 
 
Um grafo G=(V,E) é uma entidade matemática abstrata. Analise as afirmativas abaixo e 
marque a opção correta. 
I - O conjunto V é o conjunto de nós do grafo e E o conjunto de arestas 
que são compostas por pares de nós de V . 
Esta característica faz do grafo 
II - Um modelo perfeito para redes de qualquer tipo. 
 
 
I é falsa e II é verdadeira. 
 
I e II são verdadeiros, porém não há relação entre I e II. 
 
Ambas são falsas. 
 I e II são verdadeiros e II justifica I. 
 
I é verdadeiro e II é falsa. 
Respondido em 02/12/2022 19:49:24 
 
 
 3. Ref.: 6119791 
 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206119790.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206119936.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206119791.');
Em relação ao percurso Euleriano, analise as afirmativas abaixo: 
I - Deve visitar obrigatoriamente todas as arestas do grafo uma única vez. 
II - Deve visitar obrigatoriamente todos os nós do grafo uma única vez. 
III - Pode ser determinado em tempo polinomial. 
 
 
Somente II é verdadeira. 
 
Somente I é verdadeira. 
 
Somente III é verdadeira. 
 
Somente II e III são verdadeiras. 
 Somente I e III são verdadeiras. 
Respondido em 02/12/2022 19:49:55 
 
 
 4. Ref.: 6119792 
 
 
Analise as afirmativas abaixo: 
I - O problema de determinar o ciclo hamiltoniano de um grafo é NP-completo. 
 
Isto quer dizer que: 
 
II - Não se conhece algoritmo que resolva o problema em tempo polinomial. 
 
 
I é falsa e II é verdadeira. 
 I e II são verdadeiras e II justifica I. 
 
I é verdadeira e II é falsa. 
 
I e II são verdadeiras, porém II não justifica I. 
 
Ambas são falsas. 
Respondido em 02/12/2022 19:48:35 
 
 
 5. Ref.: 7598690 
 
 
O percurso em largura é caracterizado por definir um critério na seleção das arestas não 
visitadas. O critério é: 
 
 
Organizar as arestas em um conjunto. 
 Organizar as arestas em uma fila. 
 
Organizar as arestas em um deque. 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206119792.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207598690.');
 
Organizar as arestas em uma pilha. 
 
Organizar as arestas em uma árvore. 
Respondido em 02/12/2022 19:47:27 
 
 
 6. Ref.: 6119789 
 
 
Muitas vezes nos referimos a um grafo e exibimos um diagrama. É muito comum isto 
acontecer. Dizemos que o diagrama é uma representação plana do grafo quando as arestas, 
que são representadas por linhas, não se cruzam em nenhum ponto. Analise as afirmativas 
abaixo: 
Todo grafo admite uma representação plana. 
A representação plana de um grafo pode não ser única. 
É fácil desenhar a representação plana de K5, isto é, o grafo completo com 5 vértices. 
 
 
Somente III é verdadeira. 
 
Somente I é verdadeira. 
 Somente II é verdadeira. 
 
Todas são falsas. 
 
Todas são verdadeiras. 
Respondido em 02/12/2022 19:50:22 
 
 
 7. Ref.: 7598855 
 
 
O percurso em profundidade é caracterizado por definir um critério na seleção das arestas não 
visitadas. O critério é: 
 
 
Organizar as arestas em um deque. 
 
Organizar as arestas em uma árvore. 
 
Organizar as arestas em um conjunto. 
 
Organizar as arestas em uma fila. 
 Organizar as arestas em uma pilha. 
Respondido em 02/12/2022 19:58:24 
 
 
 8. Ref.: 7598723 
 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206119789.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207598855.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207598723.');
O algoritmo genérico de percurso divide o conjunto de V de vértices e E de arestas 
em dois subconjuntos disjuntos V' e V'' ; E' e E'' , correspondendo aos vértices ou 
arestas marcados e não marcados respectivamente. No passo geral, o algoritmo seleciona uma 
aresta não marcada, marca esta aresta, isto é, insere em E'' e, caso um dos vértices ao qual a 
aresta é incidente não for marcado, marca este vértice V''. Com base nisso, podemos afirmar: 
 
 
O percurso é único. 
 
O percurso fica indefinido. 
 O percurso só existe se o grafo for conexo. 
 
O percurso pode não existir. 
 Podem existir diversos percursos diferentes. 
Respondido em 02/12/2022 19:51:33