AV3 Grafos

Prévia do material em texto

1a Questão 
Respondido em 02/12/2022 19:41 
 Ref.: 201910261455 
 
 
A estrutura de dados formada por conjuntos de pontos (nós ou vértices) 
em um conjunto de linhas (arestas e arcos) que conectam vários pontos é 
denominada? 
 
 
Pilha 
 
Lista Duplamente Encadeada 
 
Lista de Adjacência 
 
Grafos 
 
Árvores 
 
 
 
 2a Questão 
Respondido em 02/12/2022 19:42 
 Ref.: 201910307472 
 
 
Dado o grafo abaixo, após a execução do algoritmo de busca em largura, qual o melhor 
caminho que liga o vértice 0 ao vértice 8? Vale ressaltar que o vértice de origem é vértice 
zero (0). 
 
 
 
0 - 1 - 2 - 5 - 6 - 7 - 8 
 
0 - 1 - 2 - 3 - 5 - 8 
 
0 - 4 - 5 - 2 - 7 - 8 
 
Neste grafo não é possível rodar a busca em profundidade, pois o grafo não 
é orientado 
 
0 - 4 - 5 - 6 - 7 - 8 
 
 
 
 3a Questão 
Respondido em 02/12/2022 19:45 
 Ref.: 201910301016 
 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207700714/n/nStatus%20da%20quest%C3%A3o:%20Liberada%20para%20Uso.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207746731/n/nStatus%20da%20quest%C3%A3o:%20Liberada%20para%20Uso.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207740275/n/nStatus%20da%20quest%C3%A3o:%20Liberada%20para%20Uso.');
Analise o grafo abaixo e relacione com conceito a seguir: 
Grafo G = v6,v5,v4,v3,v2,v1,v6 
Um _________________ em um grafo conexo G é definido com um caminho simples 
fechado em que cada vértice de G é visitado uma única vez,com 
exceção do nó inicial. Assinale a alternativa que corresponde a definição. 
 
 
Caminho conexo 
 
Ciclo euleriano 
 
 
Ciclo Hamiltoneano 
 
 
Caminho Euleriano 
 
 
Caminho em ciclo 
 
 
 
 
 4a Questão 
Respondido em 02/12/2022 19:42 
 Ref.: 201910307171 
 
 
Sobre o conceito de percorrer grafo em busca de caminhos mínimos, um dos grafos mais 
aplicado neste processo é o algoritmo Dijkstra, que soluciona o problema do caminho 
mais curto num grafo dirigido ou não dirigido. Após a execução deste algoritmo, qual o 
peso final do vértice C? 
 
 
 
5 
 
6 
 
10 
 
7 
 
9 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207746430/n/nStatus%20da%20quest%C3%A3o:%20Liberada%20para%20Uso.');
 
 
 
 5a Questão 
Respondido em 02/12/2022 19:42 
 Ref.: 201910300879 
 
 
A representação de grafos se apresentam de diversas formas, quanto ao tipo conexo ou 
desconexo, regulares, simudouro e fonte. Essas classificações são com base em 
características e regras. Observe a definição a seguir e assinale a alternativa correta quanto 
a classificação do grafo. 
"Diz-se que um grafo é ______________________, se e somente se, todos os seus vértices 
tiverem o mesmo grau." 
 
 
Desconexo 
 
Conexo 
 
 
Fonte 
 
 
Regular 
 
Sumidouro 
 
 
 
 
 6a Questão 
Respondido em 02/12/2022 19:43 
 Ref.: 201910301021 
 
 
Descubra no grafo a seguir qual o menor caminho entre os vértices v1 e v7, com base nos pesos 
existentes. Assinale a alternativa correta. 
 
 
 
v1,v2,v3,v4 e v7 
 
 
v1,v2,v3,v4, v6 e v7 
 
v1,v2,v3,v6 e v7 
 
 
v1,v2,v6 e v7 
 
 
v1,v2,v3,v4, v8 e v7 
 
 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207740138/n/nStatus%20da%20quest%C3%A3o:%20Liberada%20para%20Uso.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207740280/n/nStatus%20da%20quest%C3%A3o:%20Liberada%20para%20Uso.');
 
 7a Questão 
Respondido em 02/12/2022 19:43 
 Ref.: 201910261405 
 
 
Suponha que um grafo simples, planar, conectado possui 24 vértices, todos os vértice de 
grau 3. Em quantas regiões podemos fazer a representação planar deste grafo? 
 
 
12 
 
36 
 
14 
 
10 
 
24 
 
 
 
 8a Questão 
Respondido em 02/12/2022 19:43 
 Ref.: 201910300872 
 
 
Observe a representação do grafo planar de K3;3, e assinale a alternativa que indica o tipo 
do grafo. 
 
 
 
Grafo K3;3 é planar 
 
Grafo K3;3 é desconexo 
 
Grafo K3;3 não é planar 
 
Grafo K3;3 é conexo 
 
Grafo K3;3 é regular 
 
 
 
 9a Questão 
Respondido em 02/12/2022 19:43 
 Ref.: 201910307374 
 
 
Quantas faces existem em um grafo planar com 10 vértices e grau 3? 
 
 
8 
 
7 
 
14 
 
15 
 
10 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207700664/n/nStatus%20da%20quest%C3%A3o:%20Liberada%20para%20Uso.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207740131/n/nStatus%20da%20quest%C3%A3o:%20Liberada%20para%20Uso.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207746633/n/nStatus%20da%20quest%C3%A3o:%20Liberada%20para%20Uso.');
 
 
 10a Questão 
Respondido em 02/12/2022 19:43 
 Ref.: 201910300707 
 
 
Observe as alternativas abaixo que se referem a grafos Planares e Assinale a alternativa que 
corresponde a um grafo que não é planar: 
 
 
K_3,3 
 
Um grafo ciclo par 
 
Um grafo ciclo de 3 vértices 
 
K_4 
 
Grafo bipartido com 2 vértices em cada partição 
 
 
 
 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%207739966/n/nStatus%20da%20quest%C3%A3o:%20Liberada%20para%20Uso.');