Teoria dos Grafos 1 a 6

Prévia do material em texto

Teoria dos Grafos - Turma_001 
AS – Unidade I 
Pergunta 1 
O desenho a seguir é considerado um grafo? Se sim, quantos vértices e arestas ele 
possui? 
 
Sim, o desenho acima é um grafo de 4 vértices e 6 arestas. 
 
Pergunta 2 
Grafos são bastante utilizados para modelar e resolver problemas. Na modelagem de 
placas de circuitos eletrônicos, são utilizados grafos. Assinale a alternativa que explica 
corretamente como os grafos são utilizados nessa modelagem. 
Uma placa de circuito eletrônica é composta por diversos componentes eletrônicos. 
Correntes elétricas percorrem por tais componentes. Dessa forma, grafos podem ser 
utilizados para representar o percurso das correntes entre os componentes, onde os 
componentes são representados pelos vértices, e as arestas representam a conexão 
entre os componentes. 
 
Pergunta 3 
Leia as afirmações a seguir: 
I. Grafos são compostos por vértices e arestas; 
II. A Teoria dos grafos tem como enfoque principal o estudo da natureza; 
III. O objetivo da teoria dos grafos é estudar o relacionamento entre os objetos; 
IV. Grafos podem se compreendidos como estruturas do mundo real utilizadas na 
natureza. 
Analisando estas informações, é possível afirmar que: 
Somente as afirmações I e III estão corretas. 
 
Pergunta 4 
Quem foi o primeiro a propor uma solução utilizando grafos? 
Leonhard Euler. 
 
Pergunta 5 
 
 
Pergunta 6 
 
 
AS – Unidade II 
Pergunta 1 
O que são grafos rotulados? 
Grafos que possuem rótulos nos vértices ou arestas. 
 
Pergunta 2 
Observe o grafo abaixo e assinale a alternativa correta. 
 
É um grafo simples. 
 
Pergunta 3 
O que são grafos ponderados? 
Grafos que possuem pesos associados em suas arestas ou vértices. 
 
Pergunta 4 
Com relação ao grafo abaixo, ele é: 
 
Vazio. 
 
Pergunta 5 
 
 
Pergunta 6 
 
AS – Unidade III 
Pergunta 1 
O teorema de Kuratowski diz que um grafo G = (V, A) é 
planar se e somente se G não contém uma subdivisão K5 ou K3,3. 
 
Pergunta 2 
Um grafo G = (V, A) direcionado é dito fracamente conexo quando 
existe, pelo menos, um par de vértices i e j em G tal que o número de caminhos entre i 
e j seja menor que 1. 
 
Pergunta 3 
Em um grafo G = (V, A) 
direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe 
caminho direcionado de i para j e de j para i em G. Agora, dois vértices i e j estão 
fortemente conectados em um grafo G = (V, A) não direcionado, se existem dois 
caminhos distintos em arestas de i para j em G. 
 
Pergunta 4 
Um grafo é denominado k-conexo quando para 
qualquer par de vértices de G existem, pelo menos, K caminhos diferentes entre os 
quais. 
 
Pergunta 5 
 
Pergunta 6 
 
AS – Unidade IV 
Pergunta 1 
Tal como sugere o seu nome, o algoritmo busca em largura utiliza a técnica de busca 
em largura, cujo procedimento sempre 
analisa os vizinhos do vértice verificado, apenas. 
 
Pergunta 2 
O algoritmo de busca em profundidade sempre analisa os filhos do vértice verificado, o 
que cria uma árvore de 
profundidade. 
 
Pergunta 3 
Considerando uma busca em profundidade em um grafo G orientado, na floresta, caso 
v seja descendente de w, então a aresta será 
de retorno. 
 
Pergunta 4 
Considerando uma busca em profundidade em um grafo G orientado, na floresta, caso 
w seja descendente de v, então a aresta será 
de avanço.. 
 
Pergunta 5 
 
 
 
Pergunta 6 
 
 
 
 
AS – Unidade V 
Pergunta 1 
Um caminho mais curto entre dois vértices v e w de um grafo G NÃO ponderado é 
aquele 
que acumula a menor quantidade de arestas entre v e w. 
 
Pergunta 2 
Um grafo é denominado euleriano quando neste existe um ciclo que 
passa por todas as arestas de G sem repetição. 
 
Pergunta 3 
O caminho mais curto entre dois vértices v e w de um grafo G ponderado é aquele 
cuja 
soma dos pesos das arestas possui o menor valor possível entre todos os caminhos 
entre v e w. 
 
Pergunta 4 
Passeio em grafos consiste de uma sequência 
finita alternada de vértices e arestas, que começa e termina por vértices, tal que cada 
aresta é incidente ao vértice que a precede e ao que a sucede. 
 
Pergunta 5
 
 
 
Pergunta 6 
 
 
 
AS – Unidade VI 
Pergunta 1 
QUESTÃO ANULADA 
Leia atentamente as seguintes afirmações: 
I Árvore geradora de grau mínimo é uma árvore geradora desenvolvida em um grafo 
não ponderado e possuindo o menor grau máximo possível. 
II Árvore geradora mínima com mínimo grau é uma árvore geradora mínima de um 
grafo ponderado na qual possui o menor grau máximo possível. 
III Árvore geradora de grau mínimo e árvore geradora mínima com mínimo grau são 
sinônimos. 
É VERDADEIRO o que se afirma em 
II e III, apenas. 
 
Pergunta 2 
Árvore geradora de um grafo G é um subgrafo gerador 
conexo e acíclico. 
 
Pergunta 3 
Fluxo em rede é o 
ato de transportar objetos por uma rede. 
 
Pergunta 4 
Leia atentamente as seguintes afirmações: 
I Floresta é um conjunto de árvores sem vértice em comum. 
II Floresta geradora contém todos os vértices de G. 
III Floresta geradora é um grafo que generaliza o conceito de árvore geradora. 
É VERDADEIRO o que se afirma em 
I e II, apenas. 
 
Pergunta 5