Teoria dos Grafos e Problemas de Otimização

Prévia do material em texto

Curso Pesquisa Operacional (GRD0005_01 / D.0370_80) 
Teste Parada para a Prática – Aula 03 
Iniciado 12/08/19 14:34 
Enviado 12/08/19 15:14 
Data de vencimento 12/08/19 23:59 
Status Completada 
Resultado da 
tentativa 
0,6 em 1 pontos 
Tempo decorrido 39 minutos 
Instruções Responda de acordo com o conteúdo visto nos capítulos 5 e 
6. 
Resultados exibidos Respostas enviadas, Respostas corretas, Comentários, Perguntas respondidas 
incorretamente 
 Pergunta 1 
0 em 0,2 pontos 
 
 
Leia o texto a seguir: 
 
A pesquisa operacional abrange o estudo dos problemas de escassez nos recursos 
operacionais. Dessa forma, é necessário que tais recursos sejam otimizados para que 
a empresa consiga se manter competitiva no mercado. Por isso, utiliza-se nesse estudo 
os modelos de redes para solucionar os problemas de otimização em redes. Esses 
modelos podem ser representados tanto por problemas em fluxos em redes como o 
problema da árvore geradora mínima. 
 
Na pesquisa operacional são utilizados os modelos de redes no processo de otimização 
dos recursos organizacionais. Considerando as informações do texto apresentado e do 
texto-base, assinale a alternativa correta sobre a importância dos modelos de redes e 
suas aplicações na pesquisa operacional. 
 
Resposta 
Selecionada: 
e. 
Caracterizam formatos diferentes que devem ser integrados para 
otimizar a rede. 
Resposta Correta: c. 
Representam um conjunto de grafos que permitem 
simular problemas reais. 
Comentário da 
resposta: 
Os modelos de redes são utilizados na pesquisa operacional para 
simular problemas reais, utilizando modelos matemáticos. Eles 
representam um conjunto de grafos que são formados por elementos 
e vértices, arcos ou arestas. 
 
 
 Pergunta 2 
0,2 em 0,2 pontos 
 
Observe a seguinte figura e leia o texto a seguir: 
 
 
A figura apresentada ilustra o surgimento da Teoria dos Grafos a partir do estudo de 
um problema encontrado pelo matemático e geômetra Leonhard Euler em 1736. 
Segundo Gomes et al. (2009) “Os problemas de Percurso em Arcos são dos mais 
antigos relacionados a grafos. A primeira referência que se conhece sobre eles vem do 
famoso problema das sete pontes de Königsberg.” 
GOMES, M.J. N. et al. O problema do carteiro chinês, algoritmos exatos e um ambiente 
MVI para análise de suas instâncias: sistema XNÊS. Pesqui. Oper. Rio de Janeiro, v. 
29, n. 2, p. 1, Aug. 2009. Disponível em: 
< http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382009000200005 >. Acesso 
em: 10/09/2017. 
 
 
O problema das setes pontes localizadas na antiga cidade de Königsberg serviu como 
base de estudo para o surgimento da Teoria dos Grafos. Considerando as informações 
do texto apresentado e os assuntos abordados no texto-base, assinale a alternativa 
correta sobre o objetivo do problema das sete pontes. 
Resposta 
Selecionada: 
d. 
Encontrar um caminho único que atravessasse as setes pontes 
até a margem de outra ilha. 
Resposta Correta: d. 
Encontrar um caminho único que atravessasse as setes pontes 
até a margem de outra ilha. 
Comentário da 
resposta: 
O problema de Euler tinha como objetivo encontrar um caminho que 
partisse de uma das margens e atravessasse num único caminho as 
setes pontes até a margem de outra ilha de forma que uma pessoa 
pudesse ir e voltar pelo mesmo caminho. 
 
 
 Pergunta 3 
0,2 em 0,2 pontos 
 
 
Leia o texto a seguir: 
 
“Sabe-se que em muitas áreas da computação o universo dos problemas insolúveis é 
muito grande, sendo a Teoria dos Grafos uma destas, mais especificamente, a área de 
fluxo em redes. [...]. Assim cita-se o Problema de Fluxo de Custo Mínimo com 
Incertezas (PFCM Fuzzy) como um importante problema da área com aplicações nas 
áreas supracitadas. Este possui como objetivo atender, a um custo mínimo, a demanda 
em uma rede, dada a oferta de recursos e as restrições de capacidades dos arcos. Por 
trabalhar com diferentes tipos de parâmetros, o Problema de Fluxo de Custo Mínimo 
(PFCM) recebe duas classificações, o problema clássico (crisp) e o problema incerto 
(fuzzy).” 
FORBECK, F. R. KATAYAMA, J. P. M. K.; HERNNDES, F. Um algoritmo baseado no método simplex para redes 
aplicado no problema de fluxo de custo mínimo com incertezas. Hífen, Uruguaiana, v. 32, nº 62, p.59 - II Semestre - 
Ano 2008. Disponível 
em: http://revistaseletronicas.pucrs.br/ojs/index.php/hifen/article/download/4579/3468. Acesso em: 08/09/2017. 
 
O problema de fluxo de custo mínimo é dividido em dois tipos: clássico (crisp) e de 
incertezas (fuzzy). Considerando as informações apresentadas no texto e no texto-
base, sobre as duas classificações do problema de fluxo de custo mínimo, analise as 
afirmativas a seguir: 
I. O problema fuzzy utiliza valores incertos. 
II. O problema crisp utiliza valores exatos. 
III. O problema crisp é considerado impreciso. 
IV. O problema fuzzy visa atender o custo reduzido. 
 
Está correto apenas o que se afirma em: 
 
Resposta Selecionada: c. 
V, V, F, F. 
Resposta Correta: e. 
F, F, F, V. 
Comentário 
da resposta: 
A afirmativa I é falsa, pois o problema fuzzy trabalha com valores 
precisos e exatos. A afirmativa II é falsa, pois o problema crisp trabalha 
com valores incertos e riscos. A afirmativa III é falsa, pois o problema 
crisp trata valores certos, preciso e exatos. A afirmativa IV é verdadeira, 
pois o problema fuzzy buscar atender o custo reduzido, utilizando os 
recursos disponíveis e as restrições do problema. 
 
 
 Pergunta 4 
0 em 0,2 pontos 
 
 
Leia o texto a seguir: 
 
“Grafos são abstrações matemáticas particularmente convenientes quando se pretende 
expressar, não somente os dados, mas também, seu relacionamento característico. 
Estradas ligando facilidades (parques industriais, lojas, estações de abastecimento), 
estruturas interconectando transmissão de materiais, redes de computadores 
escoando informações e infraestrutura elétrica são alguns exemplos de estruturas 
 
materiais comumente representados na forma de grafos para computação de 
problemas”. 
FREITAS, V. H. R. Análise computacional de otimização em redes de fluxo saturadas 
pela metodologia do algoritmo de Ford e Fulkerson. Mossoró: Universidade do Estado 
do Rio Grande do Norte, 2014. Trabalho de Conclusão de Curso do Programa de Pós-
Graduação em Ciência da Computação. Disponível em: https://ppgcc.ufersa.edu.br/wp-
content/uploads/sites/42/2014/09/victor-hugo-regis-de-freitas.pdf. Acesso em: 07/09/2017. 
 
Os grafos são objeto de estudo da pesquisa operacional que estudam os problemas de 
fluxo em redes. Considerando as informações do excerto acima e do texto-base, 
analise as afirmativas a seguir sobre os grafos: 
 
I. A estrutura do grafo é composta de um par de conjuntos de elementos e vértices. 
II. O grafo é representado por G = (N, E) ou G = (N, A). 
III. Um grafo é a quantidade de fluxo enviado entre as redes. 
IV. Um grafo é um conjunto de elementos que conectam os vértices por nós. 
 
Está correto apenas o que se afirma em: 
Resposta Selecionada: a. 
III e IV. 
Resposta Correta: b. 
I, II e IV. 
Comentário 
da resposta: 
A afirmativa I é verdadeira, pois o grafo é composto por um conjunto 
de entidades formados por elementos e vértices ou arestas. A 
afirmativa II é verdadeira, pois o grafo é representado por N que é o 
conjunto de elementos e vértices ou arestas que é representado por 
E/A. A afirmativa III é falsa, pois o grafo estuda os problemas de fluxos 
em redes. A afirmativa IV é verdadeira, pois o grafo é um conjunto de 
elementos que visam conectaros vértices e nós. 
 
 
 Pergunta 5 
0,2 em 0,2 pontos 
 
 
Leia o texto a seguir: 
 
“Um grafo qualquer S = (VS, ES, LS) é dito subgrafo de um grafo G = (V, E, L) se e 
somente se satisfaz às seguintes regras: 
1. VS ⊆ V ; 
2. ES ⊆ E; 
3. ∀ µ ∈ VS ∪ ES, LS(µ) = L(µ). 
Em outras palavras, subgrafos são fragmentos de um grafo. A regra 1 diz que para um 
subgrafo S pertencer a um grafo G, o conjunto de vértices de S deve estar contido no 
conjunto de vértices de G. O mesmo vale para o conjunto de arestas na regra 2. A regra 
3 diz que para todos os elementos de S (vértices e arestas), a rotulagem deve combinar 
de forma exata com os elementos de G.” 
SANTANA, C. A. Gremlin: uma estratégia baseada em mineração de subgrafos para 
inferir padrões de interação na interface proteína-ligante. Viçosa, MG, 2017. p.11. 
 
Disponível 
em: http://locus.ufv.br/bitstream/handle/123456789/10064/texto%20completo.pdf?sequence=1&isAllowed=y. 
Acesso em: 11/09/2017. 
 
Os subgrafos correspondem a uma tipologia de grafos. Considerando os assuntos 
apresentados no texto, analise as afirmativas a seguir e assinale V para verdadeiro 
e F para falso: 
 
I. ( ) O subgrafo é o grafo que fica abaixo de outro grafo. 
II. ( ) O subgrafo é um grafo que dentro de outro grafo. 
III. ( ) O subgrafo é classificado em orientado e não-orientado. 
IV. ( ) O subgrafo é classificado em dois tipos: abrangente e induzido. 
 
Agora, assinale a alternativa que apresenta a sequência correta: 
Resposta Selecionada: a. 
F, V, F, V. 
Resposta Correta: a. 
F, V, F, V. 
Comentário 
da resposta: 
A afirmativa I é falsa, pois um subgrafo é aquele que fica dentro de 
outro grafo. A afirmativa II é verdadeira, pois um subgrafo é aquele que 
fica localizando dentro de outro grafo. A afirmativa III é falsa, pois o 
subgrafo é classificado como abrangente e induzido. A afirmativa IV é 
verdadeira, pois o subgrafo possui duas classificações, sendo 
abrangente quando ele tem a mesma quantidade de grafos que um G 
(grafo), e induzido, quando qualquer par de vértices é induzido por 
arestas de um grafo. 
 
 
 
 Pergunta 1 
0,2 em 0,2 pontos 
 
 
Leia o texto a seguir: 
 
“O problema da árvore geradora mínima aparece em uma série de aplicações [...] por 
exemplo, na instalação de linhas telefônicas (ou elétricas) entre um conjunto de 
localidades, utilizando a infraestrutura das rodovias com o menor uso de material. 
Outros casos como análise de clusters, armazenamento de informações, dentre outros, 
também podem ser resolvidos por essa modelagem, que possui eficientes algoritmos 
como Kruskal, Prim e Sollin”. 
ALMEIDA, T. A.; YAMAKAMI, A.; TAKAHASHI, M. T. Sistema imunológico artificial para 
resolver o problema da árvore geradora mínima com parâmetros fuzzy. Pesquisa 
Operacional, v.27, n.1, p.131-154, Janeiro a Abril de 2007. Disponível 
em: http://www.scielo.br/pdf/pope/v27n1/a08v27n1.pdf. Acesso em: 08/09/2017. 
 
O problema da árvore geradora mínima é outra forma de solucionar os problemas de 
otimização em redes. Considerando o texto apresentado e os assuntos abordados no 
 
texto-base, analise as afirmativas a seguir sobre as características da árvore geradora 
mínima: 
 
I. O grafo possui um formato de uma árvore. 
II. O grafo é conexo e cíclico. 
III. A árvore geradora mínima é determinada por dois algoritmos. 
IV. A árvore geradora mínima é aquela que conecta um nó e um vértice. 
 
Está correto apenas o que se afirma em: 
Resposta Selecionada: b. 
II e IV. 
Resposta Correta: e. 
I e III. 
Comentário 
da resposta: 
A afirmativa I é verdadeira, pois o formato do grafo de uma árvore 
geradora mínima é uma árvore. A afirmativa II é falsa, pois o grafo de 
uma árvore geradora mínima é conexo e sem ciclos. A afirmativa III é 
verdadeira, pois o problema da árvore geradora mínima é solucionada 
por dois algoritmos: o método kruskal e o método prim. A afirmativa IV 
é falsa, pois a árvore geradora mínima é aquela que conecta todos os 
pontos de uma rede, buscando caminhos mais curtos. 
 
 
 Pergunta 2 
0,2 em 0,2 pontos 
 
 
Leia o texto a seguir: 
 
A pesquisa operacional abrange o estudo dos problemas de escassez nos recursos 
operacionais. Dessa forma, é necessário que tais recursos sejam otimizados para que 
a empresa consiga se manter competitiva no mercado. Por isso, utiliza-se nesse estudo 
os modelos de redes para solucionar os problemas de otimização em redes. Esses 
modelos podem ser representados tanto por problemas em fluxos em redes como o 
problema da árvore geradora mínima. 
 
Na pesquisa operacional são utilizados os modelos de redes no processo de otimização 
dos recursos organizacionais. Considerando as informações do texto apresentado e do 
texto-base, assinale a alternativa correta sobre a importância dos modelos de redes e 
suas aplicações na pesquisa operacional. 
 
Resposta 
Selecionada: 
d. 
Representam um conjunto de grafos que permitem 
simular problemas reais. 
Resposta Correta: d. 
Representam um conjunto de grafos que permitem 
simular problemas reais. 
Comentário da 
resposta: 
Os modelos de redes são utilizados na pesquisa operacional para 
simular problemas reais, utilizando modelos matemáticos. Eles 
 
representam um conjunto de grafos que são formados por elementos 
e vértices, arcos ou arestas. 
 
 Pergunta 3 
0 em 0,2 pontos 
 
 
Leia o texto a seguir: 
 
“Grafos são abstrações matemáticas particularmente convenientes quando se pretende 
expressar, não somente os dados, mas também, seu relacionamento característico. 
Estradas ligando facilidades (parques industriais, lojas, estações de abastecimento), 
estruturas interconectando transmissão de materiais, redes de computadores 
escoando informações e infraestrutura elétrica são alguns exemplos de estruturas 
materiais comumente representados na forma de grafos para computação de 
problemas”. 
FREITAS, V. H. R. Análise computacional de otimização em redes de fluxo saturadas 
pela metodologia do algoritmo de Ford e Fulkerson. Mossoró: Universidade do Estado 
do Rio Grande do Norte, 2014. Trabalho de Conclusão de Curso do Programa de Pós-
Graduação em Ciência da Computação. Disponível em: https://ppgcc.ufersa.edu.br/wp-
content/uploads/sites/42/2014/09/victor-hugo-regis-de-freitas.pdf. Acesso em: 07/09/2017. 
 
Os grafos são objeto de estudo da pesquisa operacional que estudam os problemas de 
fluxo em redes. Considerando as informações do excerto acima e do texto-base, 
analise as afirmativas a seguir sobre os grafos: 
 
I. A estrutura do grafo é composta de um par de conjuntos de elementos e vértices. 
II. O grafo é representado por G = (N, E) ou G = (N, A). 
III. Um grafo é a quantidade de fluxo enviado entre as redes. 
IV. Um grafo é um conjunto de elementos que conectam os vértices por nós. 
 
Está correto apenas o que se afirma em: 
 
Resposta Selecionada: e. 
III e IV. 
Resposta Correta: d. 
I, II e IV. 
Comentário 
da resposta: 
A afirmativa I é verdadeira, pois o grafo é composto por um conjunto 
de entidades formados por elementos e vértices ou arestas. A 
afirmativa II é verdadeira, pois o grafo é representado por N que é o 
conjunto de elementos e vértices ou arestas que é representado por 
E/A. A afirmativa III é falsa, pois o grafo estuda os problemas de fluxos 
em redes. A afirmativa IV é verdadeira, pois o grafo é um conjunto de 
elementos que visam conectar os vértices e nós. 
 
 
 Pergunta 4 
0,2 em 0,2 pontos 
 
Observe a seguinte figura e leia o texto a seguir: 
 
 
A figura apresentadailustra o surgimento da Teoria dos Grafos a partir do estudo de 
um problema encontrado pelo matemático e geômetra Leonhard Euler em 1736. 
Segundo Gomes et al. (2009) “Os problemas de Percurso em Arcos são dos mais 
antigos relacionados a grafos. A primeira referência que se conhece sobre eles vem do 
famoso problema das sete pontes de Königsberg.” 
GOMES, M.J. N. et al. O problema do carteiro chinês, algoritmos exatos e um ambiente 
MVI para análise de suas instâncias: sistema XNÊS. Pesqui. Oper. Rio de Janeiro, v. 
29, n. 2, p. 1, Aug. 2009. Disponível em: 
< http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382009000200005 >. Acesso 
em: 10/09/2017. 
 
 
O problema das setes pontes localizadas na antiga cidade de Königsberg serviu como 
base de estudo para o surgimento da Teoria dos Grafos. Considerando as informações 
do texto apresentado e os assuntos abordados no texto-base, assinale a alternativa 
correta sobre o objetivo do problema das sete pontes. 
Resposta 
Selecionada: 
b. 
Encontrar um caminho único que atravessasse as setes pontes 
até a margem de outra ilha. 
Resposta Correta: b. 
Encontrar um caminho único que atravessasse as setes pontes 
até a margem de outra ilha. 
Comentário da 
resposta: 
O problema de Euler tinha como objetivo encontrar um caminho que 
partisse de uma das margens e atravessasse num único caminho as 
setes pontes até a margem de outra ilha de forma que uma pessoa 
pudesse ir e voltar pelo mesmo caminho. 
 
 
 Pergunta 5 
0,2 em 0,2 pontos 
 
 
Leia o texto a seguir: 
 
“Sabe-se que em muitas áreas da computação o universo dos problemas insolúveis é 
muito grande, sendo a Teoria dos Grafos uma destas, mais especificamente, a área de 
fluxo em redes. [...]. Assim cita-se o Problema de Fluxo de Custo Mínimo com 
Incertezas (PFCM Fuzzy) como um importante problema da área com aplicações nas 
áreas supracitadas. Este possui como objetivo atender, a um custo mínimo, a demanda 
em uma rede, dada a oferta de recursos e as restrições de capacidades dos arcos. Por 
trabalhar com diferentes tipos de parâmetros, o Problema de Fluxo de Custo Mínimo 
(PFCM) recebe duas classificações, o problema clássico (crisp) e o problema incerto 
(fuzzy).” 
FORBECK, F. R. KATAYAMA, J. P. M. K.; HERNNDES, F. Um algoritmo baseado no método simplex para redes 
aplicado no problema de fluxo de custo mínimo com incertezas. Hífen, Uruguaiana, v. 32, nº 62, p.59 - II Semestre - 
Ano 2008. Disponível 
em: http://revistaseletronicas.pucrs.br/ojs/index.php/hifen/article/download/4579/3468. Acesso em: 08/09/2017. 
 
O problema de fluxo de custo mínimo é dividido em dois tipos: clássico (crisp) e de 
incertezas (fuzzy). Considerando as informações apresentadas no texto e no texto-
base, sobre as duas classificações do problema de fluxo de custo mínimo, analise as 
afirmativas a seguir: 
I. O problema fuzzy utiliza valores incertos. 
II. O problema crisp utiliza valores exatos. 
III. O problema crisp é considerado impreciso. 
IV. O problema fuzzy visa atender o custo reduzido. 
 
Está correto apenas o que se afirma em: 
 
Resposta Selecionada: c. 
V, V, F, F. 
Resposta Correta: a. 
F, F, F, V. 
Comentário 
da resposta: 
A afirmativa I é falsa, pois o problema fuzzy trabalha com valores 
precisos e exatos. A afirmativa II é falsa, pois o problema crisp trabalha 
com valores incertos e riscos. A afirmativa III é falsa, pois o problema 
crisp trata valores certos, preciso e exatos. A afirmativa IV é verdadeira, 
pois o problema fuzzy buscar atender o custo reduzido, utilizando os 
recursos disponíveis e as restrições do problema. 
 
 
Quinta-feira, 24 de Outubro de 2019 17h01min02s BRT