01 INTRODUÇÃO A TEORIA DOS GRAFOS - ATIVIDAD

Prévia do material em texto

Atividade 1: Unidades de Estudo 1 e 2
Questão 1
As matrizes podem representar um conjunto de dados extraídos de diversas fontes, tornando-se uma
ferramenta matemática de extrema importância, principalmente quando existe a necessidade de se organizar
grandes quantidades de valores. A sua estrutura pode ser observada a seguir.
AAABBBCCCDDDEEE
AAA0 1 0 1 0
BBB1 0 1 0 1
CCC0 1 1 0 0
DDD1 0 0 0 1
EEE 0 1 0 1 0
Fonte: Elaborado pelo autor.
Assinale a alternativa que apresenta a afirmação correta.
Existe um laço no vértice CCC. (Correta)
Existe um laço no vértice EEE.
Existe uma aresta entre os vértices CCC e AAA.
O vértice DDD não está relacionado com EEE.
O vértice EEE se relaciona com BBB e CCC.
Resposta correta. A alternativa está correta, pois, na diagonal principal, onde são representados o cruzamento das linhas e colunas que representam AAA x
AAA, BBB x BBB, DDD x DDD e EEE x EEE, recebem o valor 0, indicando que não existe um laço. Já na terceira coluna (CCC) e terceira linha (CCC),
existe o valor 1, indicando um laço no vértice CCC.
Questão 2
Basicamente a matriz incidência utiliza as mesmas representações da matriz adjacência, porém, a sua forma
de expressar os relacionamentos se difere. Isso possibilita maiores representações de sistemas e,
consequentemente, a possibilidade de se desenvolver grafos complexos.
A partir do apresentado, analise as asserções a seguir e a relação proposta entre elas.
I. Na matriz incidência, a orientação de relacionamento dos vértices por meio das arestas é colunar.
Pois:
II. O valor 1 representa ausência de relacionamento entre os vértices, e o valor 2 indica que existe uma aresta
que liga os vértices.
A seguir, assinale a alternativa correta.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
A asserção I é uma proposição verdadeira e a asserção II é uma proposição falsa. (Correta)
As asserções I e II são proposições falsas. 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
Resposta correta. A alternativa está correta, pois a asserção I é uma proposição verdadeira, uma vez que há orientação de relacionamentos, devem ser
observados os valores expressos nas colunas da matriz. A asserção II está incorreta, pois o valor 2 não é utilizado para representar os relacionamentos,
mas sim o valor 1.
Questão 3
Os parquímetros são máquinas de autoatendimento que permitem ao usuário escolher a quantidade de horas
que o seu veículo irá ficar estacionado nas áreas demarcadas no município. Esse tipo de sistema é possível de
ser representado por meio de um grafo, sendo um conceito largamente utilizado com os autômatos.
O grafo a seguir representa o seu funcionamento, conforme pode ser observado.
image0025e3b18d8_20211113022224.jpg
Fonte: Elaborado pelo autor.
Nesse sentido, assinale a alternativa com a afirmação correta.
Existem apenas três arestas, que são representadas pelos laços.
Existem três arestas, que são R$ 0,25, R$ 0,50 e R$ 1,00.
Existem três vértices e cinco arestas, sendo três laços. (Correta)
Não existem arestas no grafo, apenas vértices.
Não existem laços no grafo.
Resposta correta. A alternativa está correta, pois são três vértices representados pelos valores das moedas R$ 0,25, R$ 0,50 e R$ 1,00, onde existe uma
aresta que liga R$ 0,25 em R$ 0,50 e R$ 0,50 em R$ 1,00 , ainda que exista laço em todos vértices do grafo.
Questão 4
As matrizes incidência podem representar os grafos por meio de um conjunto de dados extraídos de diversas
fontes Com isso, é possível utilizar essa ferramenta para representar relacionamento de vértices por meio de
arestas, em que se utilizam os valores 0 e 1 para que seja indicado se existe uma aresta.
Um exemplo pode ser observado a seguir.
image0085e3b18d8_20211113022221.jpg
Figura 2 - Matriz incidência
Fonte: Elaborada pelo autor.
Neste sentido, observe as afirmativas com as matrizes incidência a seguir.
Está correto o que se afirma em:
I, apenas. (Correta)
II, apenas.
III, apenas.
IV, apenas.
I, II, III e IV.
Resposta correta. A alternativa está correta, pois, na coluna a1, existe o relacionamento entre os vértices A e C; na coluna a2, ocorre o relacionamento
entre A e D; na coluna a3, os vértices B e C se relacionam; na coluna a5, existe o relacionamento entre C e D; e, na coluna a6, ocorre um laço em B.
Questão 5
Os cargos e as posições hierárquicas dentro das empresas são uma forma de organizar responsabilidades e
atribuições, a fim de se obter os melhores resultados. O vetor a seguir demonstra os relacionamentos de
cargos dentro de uma empresa. Esses cargos são expressos por códigos de uso interno e determinam a
posição hierárquica desse colaborador na empresa.
Para tanto, observe o vetor a seguir.
D1 D1D2 H1 
D2 D1D2 H1 G4
G4 D2M55 
M55G4 
H1 D1D2 H10 
H10H1H10 
Fonte: Elaborado pelo autor.
Nesse sentido, assinale a alternativa com o grafo relacionado ao vetor.
Considerando o vetor apresentado, analise as afirmativas com os grafos a seguir.
Está correto o que se afirma em:
I, II, III e IV.
I e IV, apenas.
II, apenas.(Correta)
II e III, apenas.
IV, apenas.
Resposta correta. A alternativa está correta, pois o colaborador D1 pode se relacionar com o próprio D1 e com D2 e H1; o colaborador D2 pode se
relacionar com o próprio D2, D1, H1 e G4; o G4 se relaciona com D2 e M55; o M55 se relaciona com G4; os colaboradores H1 se relacionam com D1, D2 e
H10; e o H10 pode se relacionar com o próprio H10 e com H1.
Questão 6
A utilização dos vetores nas aplicações relacionadas à teoria dos grafos permite que se tenha mais
ferramentas matemáticas que permitem desenvolver grafos, a fim de se possibilitar uma análise mais
detalhada do relacionamento entre as partes que compõem determinados sistemas. 
A respeito da estrutura encontrada nos vetores, analise as afirmativas a seguir e assinale V
para a(s) Verdadeira(s) e F para a(s) Falsa(s).
( ) No vetor, somente a direção é necessária para se calcular as grandezas escalares.
( ) Um ponto é um objeto que se desloca no plano.
( ) O vetor é representado por V = 1 x m .
( ) O módulo de um vetor é a distância entre dois pontos.
Assinale a alternativa que apresenta a sequência correta.
F, F, F, F.
F, F, V, V. (Correta)
F, V, F, V.
V, V, F, F.
V, V, F, V.
Resposta correta. A sequência está correta, já que, na terceira afirmativa, a expressão diz que um vetor é formado por uma linha e “n” colunas e, na quarta
afirmativa, consta que o módulo calculado em espaços vetoriais se expressa pela distância entre dois pontos, mostrando o seu valor vetorial.
Questão 7
Leia o excerto a seguir:
“[...] os vetores utilizados na teoria dos grafos são conhecidos como lista de adjacências. Esses permitem que,
por meio de uma lista de valores, seja possível compreender quais são as representações dos vértices, e os
respectivos relacionamentos efetuados pelas arestas”.
CARDOSO, D. M. Teoria dos grafos e aplicações. Aveiro: Universidade de Aveiro, 2005. p. 175.
Considerando o excerto apresentado, sobre as matrizes, analise as afirmativas a seguir.
I. A lista de adjacência na teoria dos grafos é representada por G (V, A).
II. Assim como as matrizes, os vetores possuem um conjunto numérico de valores em linhas e colunas.
III. O desenvolvimento de um grafo a partir de um vetor é orientado pelos valores expressos nas colunas.
IV. Não é possível representar laços nos grafos, por meio de matrizes.
Assinale a alternativa que apresenta a(s) afirmativa(s) correta(s).
I, II e III, apenas.
I,II e IV, apenas.
I e III, apenas. (Correta)
n
II,III e IV, apenas.
III, apenas.
Resposta correta. A alternativa está correta, pois os vetores permitem desenvolver grafos com vértices e arestas, representados por G (V,A). Como o vetor
contém apenas uma linha, os relacionamentos entre os vértices são representados nas colunas do vetor. Para representar o relacionamento entre vértices,
é utilizado o valor 1, e, para a falta de relacionamento,o valor 0.
Questão 8
Os grafos podem representar diversos tipos de sistemas, mostrando-se uma ferramenta matemática de grande
aplicabilidade. Considere que cada vértice representado no grafo seja uma cidade e as arestas sejam estradas
que levam o motorista de um ponto ao outro do estado, conforme pode ser observado a seguir.
image0135e3b18d8_20211113022224.jpg 
Figura 3 - Grafo não orientado de uma matriz adjacente
Fonte: Elaborada pelo autor.
A respeito do vetor que gerou o grafo apresentado, analise as afirmativas a seguir e assinale V para a(s)
Verdadeira(s) e F para a(s) Falsa(s).
( ) A linha do vetor que representa o vértice “A” tem os valores: C e F.
( ) A linha do vetor que representa o vértice “B” tem os valores: C e E.
( ) A linha do vetor que representa o vértice “C” tem os valores: A e D.
( ) A linha do vetor que representa o vértice “D” tem os valores: E e F.
( ) A linha do vetor que representa o vértice “E” tem os valores: B e D.
Assinale a alternativa que apresenta a sequência correta:
F, V, F, V, F.
V, F, V, F, V. (Correta)
V, V, F, F, V.
V, V, F, V, F.
V, V, V, V, F.
Resposta correta. A sequência está correta, pois o vértice A se relaciona com C e F; o vértice B se relaciona com C e F; o vértice C se relaciona com A e D;
o vértice D se relaciona com E e F; o vértice E se relaciona com B e D; e o vértice F se relaciona com A e B.
Questão 9
Os vetores podem representar um conjunto de dados extraídos de diversas fontes, configurando-se como uma
ferramenta matemática, mais especificamente ligada à geometria analítica, que permite aplicações nas
engenharias, na biologia, na estatística, na computação e em diversas outras áreas do conhecimento. 
Um exemplo pode ser observado a seguir.
113 
22 
3234
41 
Fonte: Elaborado pelo autor.
Nesse sentido, assinale a alternativa com a afirmação correta.
(ERRADA) Existem apenas três vértice se relacionando, e um isolado dos demais.
(ERRADA) Existem quatro arestas no grafo.
Existem três laços nos vértices. (Correta)
O vértice 1 não apresenta aresta com outro vértice, apenas o laço.
O vértice 4 se relaciona apenas com o próprio vértice.
Sua resposta está incorreta. A alternativa está incorreta, pois existe pelo menos um relacionamento entre os vértices, com características de um circuito.
Para desenvolver o grafo, são necessárias 7 arestas. O vértice 1 se relaciona com o 3, e o vértice 4 se relaciona com o vértice 1.
OBS1: Não sei se o tipo de matriz ficou claro nessa questão acho que da para argumentar se perdeu ponto
aqui.
OBS2: Achei a resposta correta depois, não validei
Questão 10
Leia o excerto a seguir:
“O diretor deve manter contato direto com os gerentes financeiro, operacional e contábil. Já o gerente
administrativo se reporta ao CEO, assim como o diretor”. Esse texto deve servir de orientação para que os
colaboradores da empresa possam compreender a política hierárquica da empresa e o fluxo da comunicação
interna.
Considerando o excerto apresentado, sobre as matrizes, analise as afirmativas a seguir.
I. Para construir um grafo a partir do texto apresentado, são necessários três laços, um para cada gerente que
se reporta ao diretor.
II. Para construir um grafo a partir do texto apresentado, são necessários três laços e seis arestas.
III. Para construir um grafo a partir do texto apresentado, são necessárias cinco arestas.
IV. Não é possível transformar o texto apresentado em um grafo.
Está correto o que se afirma em:
I, apenas.
I e II, apenas.
II e III, apenas.
III, apenas. (Correta)
IV, apenas.
Resposta correta. A alternativa está correta, pois existem arestas entre: CEO e diretor; CEO e gerente administrativo; diretor e gerente financeiro, diretor e
gerente operacional; diretor e gerente contábil.
 1
Questão 1
Uma das etapas encontradas no algoritmo de Bellman-Ford está no processo de verificação de ciclos 
negativos, importante para se garantir que os resultados gerados sejam condizentes com as análises 
proporcionadas pelos algoritmos implementáveis na teoria dos grafos.
A partir do exposto, analise as asserções a seguir e a relação proposta entre elas.
I. O primeiro processo do algoritmo de Bellman-Ford faz a padronização dos valores de vértices não
relacionados.
Pois:
II. O processo que precede a verificação é o relaxamento, o qual é responsável por buscar o menor caminho
de menor custo entre os vértices.
A seguir, assinale a alternativa correta.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa.
As asserções I e II são proposições falsas.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. (Correta)
Resposta correta. A alternativa está correta, pois a asserção I é uma proposição verdadeira, já que a primeira etapa dos processos do algoritmo visa à
padronização dos vértices não relacionados. A asserção II também é uma proposição verdadeira e não justifica a I, pois se expõe que o processo de
relaxamento busca o menor custo e isso está correto, porém, em cada asserção, é explicado o funcionamento, mas ambas não se justificam.
Questão 2
Os algoritmos são sequências organizadas de execuções que são utilizadas para se garantir que determinados
problemas sejam resolvidos. No algoritmo de Dijkstra, isso não é diferente, pois o objetivo é ter uma entrada de
dados que permita fazer o processamento e, finalmente, que gere uma saída na qual foi programada.
Considerando o exposto, sobre o algoritmo de Dijkstra, analise as afirmativas a seguir.
https://www.ambfacil.com.br/index.php?/topic/1638-introdu%C3%A7%C3%A3o-a-teoria-dos-grafos/&do=showRepComment&comment=4214
https://www.ambfacil.com.br/index.php?/profile/6363-relativoounao/reputation/
https://www.ambfacil.com.br/index.php?/profile/6363-relativoounao/
I. O ponto inicial é utilizado na letra “P” com o valor 1.
II. É atribuído o valor infinito para todos os vértices no início do algoritmo.
III. Nas interações do algoritmo, o infinito deve ser substituído pelos custos negativos encontrados nos trajetos.
IV. Se existir um valor de menor custo no cruzamento de determinado vértice e se o algoritmo encontrar um
trajeto de menor custo entre dois vértices, então se sobrescreve o valor.
Está correto o que se afirma em:
I e II, apenas.
I, II e III, apenas.
II, III e IV, apenas.
II e III, apenas.
II e IV, apenas. (Correta)
Resposta correta. A alternativa está correta. A afirmativa II se apresenta de maneira adequada, pois, quando a rotina do algoritmo de Dijkstra é iniciada,
todos os vértices existentes no grafo recebem o valor infinito. A afirmativa IV também se apresenta de maneira adequada, pois a função principal do
algoritmo é buscar o menor peso (custo) entre os vértices do grafo.
Questão 3
Os algoritmos são rotinas organizadas de algumas execuções que obedecem a alguns padrões da lógica para
a resolução de alguns problemas. Esses algoritmos podem possuir implementações computacionais quando
necessário ou apenas organizar os processos de determinadas atividades.
A respeito do algoritmo de Kruskal, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s)
e F para a(s) Falsa(s).
I. ( ) O primeiro passo do algoritmo de Kruskal visa selecionar a aresta externa de menor custo.
II. ( ) O segundo passo do algoritmo de Kruskal visa determinar a aresta selecionada com o custo menor.
III. ( ) O terceiro passo do algoritmo de Kruskal visa considerar a árvore mínima geradora como A.
IV. ( ) O quarto passo do algoritmo de Kruskal visa acrescentar α em A se for formado um ciclo.
Assinale a alternativa que apresenta a sequência correta.
F, F, F, F.
F, F, V, V.
F, V, F, V.
V, F, F, F. (Correta)
V, V, F, F.
Resposta correta. A alternativa está correta, pois a afirmativa I é verdadeira, já que, na segunda etapa, ocorre a seleção das arestas de menor custo, 
considerando que já encontrou, anteriormente, ovértice inicial e atribuiu o valor zero. Assim, na etapa posterior, o algoritmo visa encontrar o vértice não 
processado que possui o valor infinito.
Questão 4
Considere este caso hipotético:uma transportadora localizada na cidade “A” recebeu o mapa com os 
municípios nos quais deverá fazer as entregas diariamente. Para otimizar as rotas, o gerente operacional 
solicitou que, com base no algoritmo de Bellman-Ford, fosse desenvolvido um vetor com os custos de 
deslocamento da cidade “A” para a cidade “E”, conforme pode ser observado na seguinte figura:
Referente ao exposto, assinale a alternativa com o vetor otimizado, correspondente ao grafo apresentado 
nessa figura.
Fonte: Elaborado pelo autor.
ABCDE
0 3 1 0 3
Fonte: Elaborado pelo autor.
ABCD E
0 3 2 NULL3
Fonte: Elaborado pelo autor.
ABCD E
0 4 1 NULL3
Fonte: Elaborado pelo autor.
ABCD E
2 3 1 NULL3
Resposta correta. A alternativa está correta, pois, de A para B, o menor custo é A - E - C - B, com 3. O menor custo de A para C é 1, com o trajeto A - E - C.
O custo de A para D é infinito, pois não existe relacionamento entre as duas arestas no grafo. O custo de A para E é 3, pois o trajeto otimizado se dá por A
diretamente para E.
Questão 5
A estrutura organizada no algoritmo de Bellman-Ford possui três elementos que o compõem. Tal algoritmo
determina como é organizado o fluxo de suas rotinas e isso permite um referencial teórico, possibilitando,
assim, que uma pessoa com conhecimentos e habilidades possa fazer uma implementação por meio de uma
linguagem de programação.
Considerando o exposto, sobre o algoritmo de Bellman-Ford, analise as afirmativas a seguir.
I. No processo de inicialização, ocorre a padronização dos valores que não possuem relacionamento.
II. O relaxamento faz o cálculo do menor custo entre os vértices.
III. O processo de ajuste faz a transformação dos valores negativos em positivos, quando se multiplica o valor
negativo por - 1.
IV. Na verificação, o algoritmo se certifica de que não esteja ocorrendo ciclos negativos.
Está correto o que se afirma em:
I e II, apenas.
I, II e III, apenas.
I, II e IV, apenas. (Correta)
II e III, apenas.
II, III e IV, apenas.
Resposta correta. A alternativa está correta. Na afirmativa I, define-se que, no processo de inicialização, ocorre a padronização dos valores, sendo esta a
sua função no algoritmo. A afirmativa II está correta, pois, no relaxamento, tem-se o processo do algoritmo, em que, de fato, é calculado o menor custo, Já
a afirmativa IV também está correta, pois, na verificação, é feita a checagem em que não ocorrem ciclos negativos. Por fim, a afirmativa III está incorreta,
porque o processo de tornar o valor positivo ao ser multiplicado por - 1 não existe em teoria dos grafos.
Questão 6
O mapeamento dos custos de deslocamento é uma variável de extrema importância, principalmente quando
estamos falando a respeito do planejamento da otimização de rotas. O grafo representado na seguinte figura
demonstra o custo de deslocamento entre algumas cidades:
image0015e6f7249_20211113022235.jpg
 Citar
 CORRETA 
Fonte: Elaborado pelo autor. 
ABCD E
0 3 1 NULL3
 CORRETA 
Fonte: Elaborada pelo autor.
Com base no algoritmo de Floyd-Warshall, os valores foram expressos na matriz evidenciada no seguinte
quadro:
ABCD
A0 4 2 6
B∞0 3 4
C∞∞0 ∞
D∞∞5 0
Fonte: Elaborado pelo autor.
A partir do exposto, analise as asserções a seguir e a relação proposta entre elas.
I. A matriz utilizou seis símbolos de ∞.
Pois:
II. São utilizados para expressar que não existe uma aresta que liga um vértice ao outro naquela direção.
A seguir, assinale a alternativa correta.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
A asserção I é uma proposição verdadeira, e a asserção II é uma proposição falsa. (Selecionada, Cai no conto
de um comentário no brainly)
As asserções I e II são proposições falsas.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. (Correta)
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
Sua resposta está incorreta. A alternativa está incorreta, pois as duas asserções apresentadas são proposições verdadeiras e a asserção II justifica a I, já
que existem seis ocorrências de falta de relacionamento entre os vértices, especificamente entre: B para A, C para A, C para B, C para D, D para A e D
para B. Ademais, o símbolo de infinito na matriz expressa essa falta de relacionamento entre os vértices, considerando a direção da aresta.
Questão 7
Uma viagem em família requer planejamento e estratégias, a fim de se ter um deslocamento com segurança,
com o menor custo e, se possível, evitar longos congestionamentos que acabam por aumentar o tempo gasto
entre dois pontos, os quais, muitas vezes, não são tão distantes. Todas essas análises estão diretamente
ligadas à teoria dos grafos e, intuitivamente, busca-se o caminho com menor custo entre dois pontos. O
algoritmo de Floyd é uma das técnicas responsáveis por encontrar tais informações.
A respeito do algoritmo de Floyd-Warshall, analise as afirmativas a seguir e assinale V
para a(s) Verdadeira(s) e F para a(s) Falsa(s).
I. ( ) Se o vértice inicial do grafo é dado por “i” e o vértice final é dado por “n”, então os vértices intermediários
são compreendidos entre “i” e “n -1”.
II. ( ) Os vértices intermediários são um conjunto de um grafo G.
III. ( ) Na matriz utilizada pelo algoritmo de Floyd, apresenta-se i = j, então o valor será 0 (zero).
IV. ( ) Se i for diferente de j e apresentar a aresta, então o menor custo deverá substituir o valor na matriz, no
algoritmo de Floyd.
Assinale a alternativa que apresenta a sequência correta.
F, F, F, F.
F, F, V, V. (Correto)
F, V, F, V.
V, V, F, F.
V, V, V, V.
Resposta correta. A alternativa está correta. A afirmativa III é verdadeira, pois, se não fosse atribuído o valor 0 (zero), seria possível ter laços no grafo, não
sendo o objetivo de análise do algoritmo de Floyd. A afirmativa IV também é verdadeira, pois, basicamente, o algoritmo de Floyd busca trajetos entre os
vértices de menor custo e, quando encontrado, esse valor é substituído pelo atual valor da matriz.
Questão 8
Leia o excerto a seguir.
“[...] o corte utilizado em cada iteração é o corte mínimo com probabilidade de, pelo menos, 1 / n . Em qualquer
estágio do algoritmo de Kruskal, o conjunto de vértices é particionado. As arestas elegíveis para serem
adicionadas à árvore têm suas extremidades em componentes distintos.”
DASGUPTA, S. Algoritmos. Porto Alegre: AMGH, 2009. p. 140.
Considerando o exposto, sobre o algoritmo de Kruskal, analise as afirmativas a seguir.
I. O algoritmo de Kruskal utiliza a recursividade para determinar o menor custo.
II. O algoritmo de Kruskal prioriza os custos negativos antes dos positivos.
III. O algoritmo de Kruskal não permite gerar grafo com característica hamiltoniana.
IV. O algoritmo de Kruskal busca fazer a eliminação de vértices que, ao passarem pelas arestas, retornam à
origem do caminho.
Está correto o que se afirma em:
I e II, apenas.
I, II e III, apenas.
I, II e IV, apenas.
II e III, apenas.
III e IV, apenas. (Correta)
Resposta correta. A alternativa está correta, pois, na afirmativa III, define-se que não podem ser utilizados grafos gerados pelo algoritmo de Kruskal em que
há circuitos fechados. A afirmativa IV está correta, porque, após ser aplicado o algoritmo de Kruskal em um grafo, este deve ser escolhido em todos os
ciclos.
Questão 9
Leia o excerto a seguir.
“[...] um exemplo clássico do uso de algoritmos é a tabela que se consulta atlas e guias rodoviários, que dão as
distâncias de várias cidades. Atualmente, fazemos esse tipo de consulta, porém com a utilização de programas
computacionais que efetuam os cálculos.”
CORMEN, J. Desmistificando Algoritmos. Rio de Janeiro: Elsevier, 2017. p. 93.
Considerando o exposto, sobre o algoritmo de Floyd-Warshall, analise as afirmativas a seguir.
I. O algoritmo de Floyd utiliza a recursividade para determinar o menorcusto, porém não poderia ser utilizado
para a consulta de guias rodoviários.
II. O algoritmo de Floyd resolve os problemas menores e, gradativamente, vai resolvendo problemas mais
complexos.
III. O algoritmo de Floyd utiliza valores negativos nas arestas entre os vértices.
IV. O algoritmo de Floyd busca fazer a eliminação de vértices para se obter uma estrutura mínima.
Está correto o que se afirma em:
I, II e IV, apenas.
II e III, apenas.
II, apenas. (Correta)
II, III e IV, apenas.
III, apenas.
Resposta correta. A alternativa está correta. A afirmativa I está incorreta, pois o algoritmo de Floyd não utiliza recursividade, ainda que poderia ser utilizado
para a consulta de guias rodoviários. A afirmativa II está correta, visto que o algoritmo de Floyd é modular, ou seja, resolve os problemas menores
inicialmente e vai aumentando aos poucos. A afirmativa III está incorreta, pois o algoritmo de Floyd não utiliza valores negativos para cálculo. A afirmativa IV
está incorreta, porque não minimiza os grafos, tratando-se de outras técnicas.
Questão 10
2
O algoritmo de Bellman-Ford pode tratar de custos negativos em valores expressos nas arestas que ligam os
vértices direcionados. A seguinte figura demonstra o custo de 1 para R$ 1.000,00 ao transporte de valores,
com uma equipe composta por um motorista, um encarregado e dois seguranças:
image0075e6f7249_20211113022235.jpg
Fonte: Elaborada pelo autor.
A respeito do algoritmo de Bellman-Ford, analise as afirmativas a seguir e assinale V
para a(s) Verdadeira(s) e F para a(s) Falsa(s).
I. ( ) Não é possível ter um ciclo negativo no grafo apresentado.
II. ( ) No vetor inicial de um trajeto de A para D, teriam os valores: 0, Infinito, -2, Infinito, 3.
III. ( ) Seria possível apenas ter um ciclo negativo no grafo.
IV. ( ) No vetor inicial de um trajeto de C para D, teriam os valores: Infinito, 2, 0, Infinito, 3.
Assinale a alternativa que apresenta a sequência correta.
F, F, F, F.
F, F, V, V.
F, V, F, V. (Correta)
V, V, F, F.
V, V, V, V.
Resposta correta. A alternativa está correta. A afirmativa II é verdadeira, pois o vetor partindo de A gera o valor 0 na primeira coluna, porque i = j é igual a
zero. Como não existe relacionamento entre A para B e A para D, recebem Infinito como valor. O relacionamento entre A para C recebe - 2 e A para E
recebe 3. A afirmativa IV é verdadeira, pois o vetor partindo de C gera o valor 0 na primeira coluna, já que i = j é igual a zero. Como não existe
relacionamento entre C para A e C para D, recebem Infinito como valor. O relacionamento entre C para B recebe 2 e C para E recebe 3.