QUESTOES AS TRABALHO

Prévia do material em texto

PERGUNTA 1
1. Quem foi o primeiro a propor uma solução utilizando grafos?
	
	a.
	Leonhard Euler.
	
	b.
	Isaac Newton.
	
	c.
	Nikola Tesla.
	
	d.
	Thomas Edison.
	
	e.
	Albert Einstein.
0,15 pontos   
PERGUNTA 2
1. 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:
	
	a.
	Somente as afirmações I e III estão corretas.
	
	b.
	Somente as afirmações II e III estão corretas.
	
	c.
	Somente a afirmação I esta correta.
	
	d.
	Somente as afirmações I e IV estão corretas.
	
	e.
	Somente as afirmações I e II estão corretas.
0,15 pontos   
PERGUNTA 3
1. 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.
	
	a.
	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 a utilização de tais placas em objetos eletrônicos.
	
	b.
	Placa de circuito eletrônica não utiliza grafos.
	
	c.
	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 pelas arestas, e os vértices representam a conexão entre os componentes.
	
	d.
	Nenhuma das alternativas anteriores.
	
	e.
	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.
0,15 pontos   
PERGUNTA 4
1. Segundo o texto, grafos podem ser utilizados em mapas de rodovias? Como?
	
	a.
	Nenhuma das alternativas anteriores.
	
	b.
	Sim, grafos podem representar a população no mapa.
	
	c.
	Sim, grafos podem representar as cidades por arestas, e os vértices podem representar as rodovias que ligam as cidades.
	
	d.
	Não, grafos não podem ser utilizados em mapas de rodovias.
	
	e.
	Sim, grafos podem representar cidades por vértices, e as arestas podem representar as rodovias que ligam as cidades.
PERGUNTA 1
1. O desenho a seguir é considerado um grafo? Se sim, quantos vértices e arestas ele possui?
	
	a.
	Sim, o desenho acima é um grafo de 6 vértices e 4 arestas.
	
	b.
	Sim, o desenho acima é um grafo de 2 vértices e 3 arestas.
	
	c.
	Não, o desenho acima não é um grafo.
	
	d.
	Sim, o desenho acima é um grafo de 4 vértices e 6 arestas.
	
	e.
	Sim, o desenho acima é um grafo de 4 vértices e 3 arestas.
0,15 pontos   
PERGUNTA 2
1. Segundo o texto, grafos podem ser utilizados em mapas de rodovias? Como?
	
	a.
	Nenhuma das alternativas anteriores.
	
	b.
	Não, grafos não podem ser utilizados em mapas de rodovias.
	
	c.
	Sim, grafos podem representar a população no mapa.
	
	d.
	Sim, grafos podem representar cidades por vértices, e as arestas podem representar as rodovias que ligam as cidades.
	
	e.
	Sim, grafos podem representar as cidades por arestas, e os vértices podem representar as rodovias que ligam as cidades.
0,15 pontos   
PERGUNTA 3
1. Quem foi o primeiro a propor uma solução utilizando grafos?
	
	a.
	Isaac Newton.
	
	b.
	Thomas Edison.
	
	c.
	Albert Einstein.
	
	d.
	Leonhard Euler.
	
	e.
	Nikola Tesla.
0,15 pontos   
PERGUNTA 4
1. 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:
	
	a.
	Somente as afirmações I e II estão corretas.
	
	b.
	Somente as afirmações I e III estão corretas.
	
	c.
	Somente as afirmações II e III estão corretas.
	
	d.
	Somente a afirmação I esta correta.
	
	e.
	Somente as afirmações I e IV estão corretas.
PERGUNTA 1
1. O desenho a seguir é considerado um grafo? Se sim, quantos vértices e arestas ele possui?
	
	a.
	Não, o desenho acima não é um grafo.
	
	b.
	Sim, o desenho acima é um grafo de 6 vértices e 4 arestas.
	
	c.
	Sim, o desenho acima é um grafo de 4 vértices e 3 arestas.
	
	d.
	Sim, o desenho acima é um grafo de 2 vértices e 3 arestas.
	
	e.
	Sim, o desenho acima é um grafo de 4 vértices e 6 arestas.
0,15 pontos   
PERGUNTA 2
1. 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.
	
	a.
	Placa de circuito eletrônica não utiliza grafos.
	
	b.
	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 pelas arestas, e os vértices representam a conexão entre os componentes.
	
	c.
	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 a utilização de tais placas em objetos eletrônicos.
	
	d.
	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.
	
	e.
	Nenhuma das alternativas anteriores.
0,15 pontos   
PERGUNTA 3
1. 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:
	
	a.
	Somente as afirmações I e IV estão corretas.
	
	b.
	Somente a afirmação I esta correta.
	
	c.
	Somente as afirmações II e III estão corretas.
	
	d.
	Somente as afirmações I e II estão corretas.
	
	e.
	Somente as afirmações I e III estão corretas.
0,15 pontos   
PERGUNTA 4
1. A teoria dos grafos começou em 1736 com um matemático suíço. Ele propôs uma solução para um problema utilizando grafos. Qual foi esse problema?
	
	a.
	Problema dos 12 carros.
	
	b.
	Problema da forma de água.
	
	c.
	Nenhuma das alternativas anteriores.
	
	d.
	Problema da atmosfera da terra.
	
	e.
	Problema das sete pontes de Konigsberg.
AS 2
PERGUNTA 1
1. Com relação ao grafo abaixo, ele é:
	
	a.
	Hipergrafo.
	
	b.
	Trivial.
	
	c.
	Buquê.
	
	d.
	Nulo.
	
	e.
	Vazio.
0,15 pontos   
PERGUNTA 2
1. Observe o grafo abaixo e assinale a alternativa correta.
	
	a.
	Nenhuma das alternativas anteriores.
	
	b.
	É um grafo buquê.
	
	c.
	É um grafo bipartido.
	
	d.
	É um grafo orientado.
	
	e.
	É um grafo simples.
0,15 pontos   
PERGUNTA 3
1. O que são laços?
	
	a.
	Arestas que ligam um grafo bipartido.
	
	b.
	Arestas que ligam um vértice a ele mesmo.
	
	c.
	Nenhuma das alternativas anteriores.
	
	d.
	Arestas que ligam dois vértices diferentes.
	
	e.
	Arestas que ligam um grafo simples.
0,15 pontos   
PERGUNTA 4
1. Com relação ao grafo abaixo,ele é:
	
	a.
	Pseudografo.
	
	b.
	Bipartido.
	
	c.
	Reflexivo.
	
	d.
	Multigrafo.
	
	e.
	Simples.
PERGUNTA 2
1. Observe o grafo abaixo e assinale a alternativa correta.
	
	a.
	É um grafo bipartido.
	
	b.
	É um grafo orientado.
	
	c.
	Nenhuma das alternativas anteriores.
	
	d.
	É um grafo simples.
	
	e.
	É um grafo buquê.
0,15 pontos   
PERGUNTA 3
1. O que são laços?
	
	a.
	Arestas que ligam dois vértices diferentes.
	
	b.
	Arestas que ligam um grafo simples.
	
	c.
	Arestas que ligam um grafo bipartido.
	
	d.
	Arestas que ligam um vértice a ele mesmo.
	
	e.
	Nenhuma das alternativas anteriores.
0,15 pontos   
PERGUNTA 4
1. O que são grafos ponderados?
	
	a.
	Grafos que possuem buquê.
	
	b.
	Nenhuma das alternativas anteriores.
	
	c.
	Grafos que possuem laços.
	
	d.
	Grafos nulos.
	
	e.
	Grafos que possuem pesos associados em suas arestas ou vértices.
PERGUNTA 3
1. O que são grafos rotulados?
	
	a.
	Grafos triviais.
	
	b.
	Grafos nulos.
	
	c.
	Grafos que possuem arestas paralelas.
	
	d.
	Grafos que possuem laços.
	
	e.
	Grafos que possuem rótulos nos vértices ou arestas.
AS 3
PERGUNTA 1
1. O teorema de Kuratowski diz que um grafo G = (V, A) é
	
	a.
	planar se e somente se G não contém uma subdivisão K3 ou K1,1.
	
	b.
	conexo se e somente se G não contém uma subdivisão K5 ou K3,3.
	
	c.
	planar se e somente se G não contém uma subdivisão K3 ou K4,4.
	
	d.
	planar se e somente se G não contém uma subdivisão K5 ou K3,3.
	
	e.
	colorido se e somente se G não contém uma subdivisão K5 ou K3,3.
0,175 pontos   
PERGUNTA 2
1. Em um grafo G = (V, A)
	
	a.
	não direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe n caminhos direcionados 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) direcionado, se existe um caminho distinto em arestas de i para j em G.
	
	b.
	direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe mais de um 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 existe um caminho distinto em arestas de i para j em G.
	
	c.
	não 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) direcionado, se existem dois caminhos distintos em arestas de i para j em G.
	
	d.
	direcionado, é dito que dois vértices i e j estão fortemente conectados, se existe, pelo menos, dois caminhos direcionados 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 existe um caminho em arestas de i para j em G.
	
	e.
	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.
0,175 pontos   
PERGUNTA 3
1. Um grafo é denominado k-conexo quando para
	
	a.
	todas as arestas de G existem, pelo menos, K caminhos iguais entre as quais.
	
	b.
	todos os pares de vértices de G existem, pelo menos, 2 caminhos diferentes entre os quais.
	
	c.
	qualquer par de vértices de G existem, pelo menos, K caminhos diferentes entre os quais.
	
	d.
	qualquer par de vértices de G existem, pelo menos, 3 caminhos iguais entre os quais.
	
	e.
	todas as arestas de G existem, pelo menos, k-7 caminhos diferentes entre as quais.
0,175 pontos   
PERGUNTA 4
1. Um grafo G = (V, A) direcionado é dito fracamente conexo quando
	
	a.
	não 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 2.
	
	b.
	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.
	
	c.
	existe, pelo menos, dois pares de vértices i e j em G tal que o número de caminhos entre i e j seja maior que 1.
	
	d.
	existe, pelo menos, dois pares de vértices i e j em G tal que o número de caminhos entre i e j seja menor que 2.
	
	e.
	não existe, pelo menos, dois pares de vértices i e j em G tal que o número de caminhos entre i e j seja menor que 3.
As 04
PERGUNTA 1
1. Considerando uma busca em profundidade em um grafo G orientado, na floresta, caso w seja descendente de v, então a aresta será
	
	a.
	ponderada.
	
	b.
	orientada.
	
	c.
	de avanço..
	
	d.
	de retorno.
	
	e.
	de cruzamento.
0,175 pontos   
PERGUNTA 2
1. O algoritmo de busca em profundidade sempre analisa os filhos do vértice verificado, o que cria uma árvore de
	
	a.
	largura.
	
	b.
	retorno.
	
	c.
	cruzamento.
	
	d.
	profundidade.
	
	e.
	avanço.
0,175 pontos   
PERGUNTA 3
1. Tal como sugere o seu nome, o algoritmo busca em largura utiliza a técnica de busca em largura, cujo procedimento sempre
	
	a.
	analisa os vizinhos do vértice verificado, apenas.
	
	b.
	analisa os filhos do vértice verificado, apenas.
	
	c.
	busca um caminho alternativo.
	
	d.
	analisa o vértice final primeiro.
	
	e.
	analisa os filhos e vizinhos do vértice verificado.
0,175 pontos   
PERGUNTA 4
1. Tal como sugere o seu nome, o algoritmo busca em profundidade utiliza a técnica de profundidade, cujo procedimento sempre
	
	a.
	analisa os vizinhos do vértice verificado, apenas.
	
	b.
	analisa os filhos e vizinhos do vértice verificado.
	
	c.
	analisa o vértice final primeiro.
	
	d.
	analisa os filhos do vértice verificado, apenas.
	
	e.
	busca um caminho alternativo.
AS 05
PERGUNTA 1
1. O caminho mais curto entre dois vértices v e w de um grafo G ponderado é aquele cuja
	
	a.
	soma dos pesos das arestas possui o menor valor possível entre todos os caminhos entre v e w.
	
	b.
	multiplicação dos pesos das arestas possui o maior valor possível entre todos os caminhos entre v e w.
	
	c.
	soma dos pesos das arestas possui o maior valor possível entre todos os caminhos entre v e w.
	
	d.
	divisão dos pesos das arestas possui o maior valor possível entre todos os caminhos entre v e w.
	
	e.
	subtração dos pesos das arestas possui o maior valor possível entre todos os caminhos entre v e w.
0,175 pontos   
PERGUNTA 2
1. Um grafo é denominado hamiltoniano quando neste existe um caminho que
	
	a.
	contém somente o vértice final.
	
	b.
	não passa por nenhum vértice.
	
	c.
	contém todos os vértices de G.
	
	d.
	contém somente o vértice inicial.
	
	e.
	contém somente os vértices inicial e final.
0,175 pontos   
PERGUNTA 3
1. Um caminho em grafos pode ser definido como uma sequência de
	
	a.
	passeios, tal que para cada passeio há uma aresta para o vértice inicial.
	
	b.
	passeios, tal que para cada passeio há uma aresta para o vértice final.
	
	c.
	vértices, tal que para cada vértice da sequência há uma aresta para o próximo vértice da sequência.
	
	d.
	passeios, tal que para cada passeio há uma aresta para o vértice inicial e outra para o vértice final.
	
	e.
	passeios, tal que para cada passeio há mais de um vértice.
0,175 pontos   
PERGUNTA 4
1. Um grafo é denominado euleriano quando neste existe um ciclo que
	
	a.
	não passa pelo vértice inicial.
	
	b.
	não passa por aresta alguma.
	
	c.
	passa somente pelo vértice final.
	
	d.
	passa somente pelo vértice inicial.
	
	e.
	passa por todas as arestas de G sem repetição.
AS 06
PERGUNTA 1
1. Árvore geradora de um grafo G é um subgrafo gerador
	
	a.
	desconexo e cíclico.
	
	b.
	desconexo em vértices e cíclico em arestas.
	
	c.
	conexo e cíclico.
	
	d.
	desconexo e acíclico.
	
	e.
	conexo e acíclico.
0,175 pontos   
PERGUNTA 2
1. Na teoria dos grafos, árvore geradora mínima é a árvore geradora de
	
	a.
	custo igual a todos os vértices e todas as arestas de G.
	
	b.
	maior custo entre todas as possíveis em G.
	
	c.
	custo igual a todas as arestas de G.
	
	d.
	custo igual a todos os vértices de G.
	
	e.
	menor custo entre todas as possíveisem G.
0,175 pontos   
PERGUNTA 3
1. 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
	
	a.
	I e II, apenas.
	
	b.
	II e III, apenas.
	
	c.
	III, apenas.
	
	d.
	II, apenas.
	
	e.
	I, apenas.
0,175 pontos   
PERGUNTA 4
1. Fluxo em rede é o
	
	a.
	ato de não transportar objetos por diversas redes.
	
	b.
	mecanismo de não transportar objetos por uma rede.
	
	c.
	ato de não transportar objetos por uma rede.
	
	d.
	ato de transportar objetos por uma rede.
	
	e.
	grafo de tamanho G.