TEORIA DOS GRAFOS E PESQUISA OPERACIONAL-A1

Prévia do material em texto

1. Com relação aos conceitos e definições dos grafos, podemos entender que um caminho 
específico em um grafo pode ser caracterizado como sendo uma sequência específica de 
vértices, de forma que, para todos os vértices, exceto o último, há a definição de uma aresta 
que parte dele e vai para o próximo vértice da sequência. 
 
Com base no apresentado, analise as asserções a seguir e a relação proposta entre elas. 
 
I. Especificamente, uma árvore pode ser classificada e nomeada como árvore geradora de custo (ou 
peso) mínimo – AGPM. 
PORQUE 
II. Especificamente, podemos considerar que o custo real, ou como pode ser denominado custo da 
árvore geradora, é identificado como efetivamente sempre menor ou igual quando comparado com o 
uso de qualquer outra árvore. 
 
A respeito dessas asserções, assinale a opção correta: 
Sua resposta está correta. 
Chave de resposta correta: A alternativa está correta. A asserção I é uma proposição verdadeira, uma 
vez que em relação aos algoritmos, a árvore geradora de valor mínimo é definida como sendo uma árvore 
que tem uma nomenclatura definida como AGMV. A asserção II é uma proposição verdadeira, uma vez 
que ao conhecermos os custos associados, estes são menores em relação a outras opções de árvores, 
sendo assim conhecidos como custos mínimos. Desta forma, a asserção II justifica a I. 
• 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. 
• 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 II é uma proposição falsa. 
✓ As asserções I e II são proposições verdadeiras, e a II é uma justificativa 
correta da I. 
 
2. De forma específica, podemos considerar como exemplo os requisitos para o 
desenvolvimento de uma solução ótima para uma rede de restaurantes: no momento em que 
o status de um pedido é atualizado, todos os dispositivos envolvidos no processo devem 
receber a informação correspondente. Os sistemas que devem ser atualizados incluem os 
seguintes itens: aqueles acessados pelo entregador, aqueles acessados pela linha de 
produção e aqueles acessados pela central de atendimento. Da mesma forma, existe a 
possibilidade de inclusão de outros sistemas no futuro, os quais devem se comportar da 
mesma maneira. 
 
Com base no exposto, analise as asserções a seguir e a relação proposta entre elas: 
 
I. O respectivo cenário e a condição de requisito demonstrada podem ser contemplados com a 
implantação e a utilização do padrão de projeto Observer. 
PORQUE 
II. O respectivo padrão de projeto Observer proporciona a realização de um estilo arquitetural na 
condição cliente-servidor, em que o respectivo servidor é responsável por assim enviar notificações 
aos clientes toda a vez que houver algum tipo de atualização. 
 
A respeito dessas asserções, assinale a opção correta: 
Sua resposta está correta. 
Chave de resposta correta: A alternativa está correta. A asserção I é uma proposição verdadeira, uma 
vez que a implementação poderia ser feita da seguinte forma: o pedido é o objeto que está sendo 
"observado" (Subject), os dispositivos são os "observadores" (Observer). Sempre que o objeto pedido 
sofrer alguma mudança em seu estado, um método ou função desse objeto deve ser acionado para 
notificar os dispositivos. A asserção II é uma proposição verdadeira, uma vez que a arquitetura cliente -
servidor é um padrão de arquitetura, e o padrão Observer é um padrão de projeto para projetos de 
software orientado a objetos. Efetivamente, a asserção II justifica a I. 
• 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. 
• 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 II é uma proposição falsa. 
✓ As asserções I e II são proposições verdadeiras, e a II é uma justificativa 
correta da I. 
 
3. De forma específica, podemos evidenciar que os chamados grafos eficientes possuem como 
uma característica única a possibilidade de serem mapeados e identificados como formas 
simétricas. Essa condição específica de simetria possibilita que sua respectiva análise seja 
muito mais eficiente. 
 
Com base no apresentado, analise as asserções a seguir e a relação proposta entre elas. 
 
I. Em relação às suas aplicações, os grafos eficientes possuem entrada nas mais diversas áreas 
existentes, em que podemos destacar áreas relacionadas com a matemática assim como a ciência 
da computação. 
PORQUE 
II. Efetivamente com suas técnicas, os grafos eficientes têm a capacidade de desenvolver e elucidar 
problemas típicos de estatísticas descritivas. 
 
A respeito dessas asserções, assinale a opção correta: 
Sua resposta está correta. 
Chave de resposta correta: A alternativa está correta. A asserção I é uma proposição verdadeira, uma 
vez que em termos de utilização e aplicação, os grafos eficientes podem ser encontrados em ações e 
práticas para a resolução de problemas tanto matemáticos quanto computacionais e de teoria de jogos. 
A asserção II é uma proposição falsa, uma vez que a aplicação dos grafos eficientes proporciona que 
problemas de teoria combinatória sejam resolvidos e minimizados. Assim, a asserção II não justifica a I. 
• 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. 
• 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 II é uma proposição falsa. 
• As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. 
 
4. Além dos conceitos e definições que envolvem os aspectos técnicos de grafos, assim como 
das árvores, bem como também das chamadas árvores mínimas e das florestas, devemos ter 
uma compreensão também de outras definições técnicas, das quais podemos enumerar, por 
exemplo, as trilhas. 
 
Com base no apresentado, analise as asserções a seguir e a relação proposta entre elas: 
 
I. Em termos de estabelecimento de um grafo, ele pode ter em sua formação uma trilha denominada 
como euleriana ou fechada. 
PORQUE 
II. Especificamente, a trilha fechada é explicada e derivada da condição específica dessa trilha conter 
e assim passar por todas as arestas do grafo. 
 
A respeito dessas asserções, assinale a opção correta: 
Sua resposta está correta. 
Chave de resposta correta: A alternativa está correta. A asserção I é uma proposição verdadeira, uma 
vez que, especificamente, ao identificarmos e estabelecermos a trilha específica, seja ela euleriana ou 
fechada, também estamos lidando com grafos. A asserção II é uma proposição verdadeira, uma vez que, 
ao analisarmos a trilha fechada, podemos identificar que ela é derivada de uma condição na qual também 
estão envolvidas as arestas do grafo. Efetivamente, a asserção II justifica a I 
• 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. 
• 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 II é uma proposição falsa. 
✓ As asserções I e II são proposições verdadeiras, e a II é uma justificativa 
correta da I. 
 
5. Com aplicações diversas e em áreas cada vez mais abrangentes e diversas, os algoritmos 
eficientes são considerados e identificados como sendo especificamente um tipo totalmente 
especial de grafos. 
 
Com base no apresentado, avalie as afirmações a seguir: 
 
I.O conceito de "eficiência" está especificamente associado a uma condição de aplicação direcionada 
e compacta, bem como a resultados positivos. 
II.Em termos de estrutura, um grafo eficiente possui especificamente uma condição de bipartibilidade 
considerada regular.III.Ainda em termos de classificação, os grafos eficientes são caracterizados por possuírem o número 
de arestas determinado por nk/2. 
IV.Com relação à composição e estruturação, podemos evidenciar que os grafos eficientes são 
conhecidos principalmente por sua assimetria. 
 
É correto o que se afirma em: 
Sua resposta está correta. 
Chave de resposta correta: Alternativa correta. A afirmativa I está correta, visto que, ao avaliarmos a 
condição de eficiência dos grafos, ela se fundamenta em obter resultados satisfatórios e desejados por 
meio da aplicação de ações simples e compactas. A afirmativa II está correta, pois, ao considerarmos a 
estrutura dos grafos eficientes, eles são realmente bipartidos e também são considerados regulares em 
relação aos seus vértices. A afirmativa III está correta, uma vez que, ao tratarmos da classificação , os 
grafos identificados como eficientes têm o número de arestas associado à condição nk/2. A afirmativa 
IV está incorreta, uma vez que a estrutura dos grafos eficientes se relaciona a uma condição específica 
de assimetria. 
✓ I, II e III, apenas. 
• I e IV, apenas. 
• II e IV, apenas 
• II e III, apenas. 
• II, III e IV, apenas. 
 
6. Especificamente, a respectiva aplicação de alguns tipos de algoritmos é comumente voltada 
como uma específica forma para a resolução de problemas computacionais. Sobre essas 
respectivas escolhas consideradas como mais adequadas para um algoritmo de ordenação, 
considere as afirmativas a seguir: 
 
I.Especificamente, quando temos uma condição em que os cenários são identificados como sendo de 
pior caso, o algoritmo mais adequado é o heap sort. 
II.Na condição em que o vetor apresenta a maioria dos elementos considerados como ordenados, o 
algoritmo mais adequado é o insertion sort. 
III.Na condição em que há um bom resultado para a condição do caso médio, o algoritmo mais 
adequado é o quick sort. 
IV.Na condição em que há interesse pelo melhor caso, assim como o pior caso, de mesma 
complexidade, o algoritmo mais adequado é o bubble sort. 
 
É correto o que se afirma em: 
Sua resposta está correta. 
Chave de resposta correta: Alternativa correta. A afirmativa I está correta, uma vez que efetivamente 
temos a tendência de aplicar o algoritmo conhecido como heap sort em momentos e estudos que sejam 
considerados mais complexos e que necessitem de uma atuação mais efetiva e direcionada. A afirmativa 
II está correta, uma vez que efetivamente temos a tendência e o direcionamento de aplicarmos e 
utilizarmos as ações do algoritmo conhecido como insertion sort quando observamos uma condição de 
estudo que demonstre que os respectivos vetores estejam em uma condição específica de ordenação. A 
afirmativa III está correta, uma vez que efetivamente temos a tendência de utilizar as bases do algoritmo 
quick sort quando observamos a existência de estudos considerados como de complexidade média. A 
afirmativa IV está incorreta, uma vez que efetivamente podemos considerar o algoritmo bubble sort 
como um exemplo de algoritmo considerado um dos piores em relação à resposta específica de 
ordenação. 
✓ I, II e III, apenas. 
• I e IV, apenas. 
• II e IV, apenas. 
• II e III, apenas. 
• II, III e IV, apenas. 
 
7. Especificamente, quando tratamos dos conceitos e aplicações dos algoritmos de Hopcroft-
Karp, compreendemos que, efetivamente, em termos de funções, a base de sua utilização 
está alinhada na condição de possibilitar o início do algoritmo e efetivar o retorno do 
emparelhamento na condição máxima. 
 
Com base no apresentado, avalie as afirmações a seguir: 
 
I.Efetivamente, o processo de aplicação do algoritmo de Hopcroft-Karp está baseado na utilização de 
duas funções consideradas como auxiliares: BFS e DFS. 
II.Especificamente, a função BFS determina uma condição de obtenção de uma largura que é 
responsável pela determinação de um caminho aumentante no grafo. 
III.Operacionalmente, a respectiva busca da largura possibilita que seja preenchido o chamado vetor D, 
responsável por armazenar a distância de cada vértice. 
IV.O chamado vértice nulo é um vértice efetivo que pertence a um específico conjunto e tem a função 
de verificar se a busca foi efetiva. 
 
É correto o que se afirma em: 
Sua resposta está correta. 
Chave de resposta correta: A alternativa está correta. A afirmativa I está correta, visto que o algoritmo 
Hopcroft-Karp, quando utilizado, faz referência às funções BFS, assim como também à DFS. A afirmativa 
II está correta, pois quando consideramos a respectiva função BFS, podemos evidenciar que a mesma é 
responsável pela determinação da largura e pelo consequente caminho aumentante no grafo. A 
afirmativa III está correta, uma vez que, ao buscarmos a largura, há uma condição de estabelecimento e, 
consequentemente, o respectivo preenchimento do vetor. A afirmativa IV está incorreta, uma vez que o 
chamado vértice nulo é um vértice identificado como sendo fictício e, portanto, não está vinculado a 
nenhum grupo. 
✓ I, II e III, apenas. 
• I e IV, apenas. 
• II e IV, apenas. 
• II e III, apenas. 
• II, III e IV, apenas. 
 
8. No que tange às questões associadas aos chamados algoritmos de menor caminho, podemos 
determinar efetivamente que estes são algoritmos especificamente utilizados para possibilitar 
o estabelecimento de uma condição de um caminho mais curto entre dois pontos em um 
grafo ponderado. 
 
Com base no apresentado, analise as asserções a seguir e a relação proposta entre elas. 
 
I. Especificamente, o algoritmo de Dijkstra tem a condição de alcançar a condição do caminho mais 
curto entre um vértice inicial e todos os outros vértices, sendo esta aplicação para um grafo 
ponderado não direcionado. 
PORQUE 
II. Há uma condição onde é executada a expansão do respectivo conjunto de vértices, onde há a 
procura de uma específica ordem crescente de suas distâncias do vértice inicial. 
 
A respeito dessas asserções, assinale a opção correta: 
Sua resposta está correta. 
Chave de resposta correta: A alternativa está correta. A asserção I é uma proposição verdadeira, uma 
vez que o algoritmo de Dijkstra possibilita o encurtamento das distâncias entre os vértices onde essa 
ação é realizada em grafos ponderados sem direção. A asserção II é uma proposição verdadeira, uma 
vez que o encurtamento dessa condição é obtido por meio da expansão dos conjuntos de vértices. 
Assim, a asserção II justifica a I. 
• 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. 
• 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 II é uma proposição falsa. 
✓ As asserções I e II são proposições verdadeiras, e a II é uma justificativa 
correta da I. 
 
9. No que tange à sua estrutura, os grafos eficientes são notabilizados por sua alta simetria, 
assim como pela condição específica de ter uma densidade fixa, o que possibilita total 
independência em relação ao seu tamanho. 
 
Com base no apresentado, avalie as afirmações a seguir: 
 
I.Efetivamente, o processo que enumera as configurações de emparelhamento perfeito em um grafo 
eficiente é realizado por meio do algoritmo de Hopcroft-Karp. 
II.Especificamente, o algoritmo de Hopcroft-Karp traduz um processo iterativo que possibilita a 
identificação de uma condição de emparelhamento. 
III.Especificamente, o algoritmo de Hopcroft-Karp permite que o processo de emparelhamento seja 
realizado sucessivamente até que não haja mais condições. 
IV.De forma específica, o algoritmo tem início com um emparelhamento vazio M e uma floresta de 
caminhos que diminui especificamente em P. 
 
É correto o que se afirma em: 
Sua resposta está correta. 
Chave de resposta correta: A alternativa está correta. A alternativa está correta. A afirmativa I está 
correta, visto que o algoritmo de Hopcroft-Karp possibilitauma efetiva enumeração das configurações 
específicas de um emparelhamento perfeito. A afirmativa II está correta, pois quando consideramos a 
condição específica do algoritmo de Hopcroft-Karp, este é responsável pela determinação e 
identificação da condição de emparelhamentos. A afirmativa III está correta, uma vez que o algoritmo de 
Hopcroft-Karp faz com que os emparelhamentos sejam constantes e sucessivos até que não haja mais 
condições. A afirmativa IV está incorreta, uma vez que o algoritmo apresenta um emparelhamento 
considerado vazio M, além de também ter uma floresta de caminhos que especificamente aumenta em P. 
✓ I, II e III, apenas. 
• I e IV, apenas. 
• II e IV, apenas. 
• II e III, apenas. 
• II, III e IV, apenas. 
 
10. Ao compreender e entender as características relacionadas à teoria dos grafos, podemos 
compreender e entender também as respectivas relações existentes na combinação, onde 
são aplicadas formas específicas para o cálculo do número de caminhos ou o número de 
ciclos em um grafo. 
 
Com base no apresentado, avalie as afirmações a seguir: 
 
I.Quando consideramos a formulação matemática, compreendemos que, para um grafo simples, a 
fórmula relaciona o número de arranjos de elementos e sua ordem. 
II.Com relação ao cálculo do número de ciclos de um grafo simples, há a específica necessidade de 
relacionar o chamado polinômio cromático do grafo. 
III.Ao compreender a relação do número de ciclos em um grafo simples, devemos especificamente 
levar em consideração a elevação do elemento pelo comprimento r. 
IV.Em termos conceituais, o elemento C(n, r) representa o número de vértices associados ao ciclo de 
um grafo completo. 
 
É correto o que se afirma em: 
Sua resposta está correta. 
Chave de resposta correta: A alternativa está correta. A afirmativa I está correta, visto que, em termos de 
representação matemática para um grafo simples, há a relação específica entre o número de arranjos e 
as respectivas ordens apresentadas. A afirmativa II está correta, pois, ao considerarmos o cálculo do 
número de ciclos relacionados a um grafo simples, é necessário levar em conta o polinômio cromático 
do grafo. A afirmativa III está correta, uma vez que, para determinar o número de ciclos de um grafo 
considerado simples, matematicamente é necessário elevar o elemento pela extensão definida por r. A 
afirmativa IV está incorreta, uma vez que a base da determinação da expressão matemática estabelece 
que o elemento C(n, r) seja definido como o número total de permutações de n elementos. 
✓ I, II e III, apenas. 
• I e IV, apenas. 
• II e IV, apenas. 
• II e III, apenas. 
• II, III e IV, apenas.