Teoria dos Grafos

Prévia do material em texto

Avaliação ll - TEORIA DE GRAFOS 
 
1. Um típico problema em que algoritmos gulosos são aplicados é conhecido como agendamento para 
minimizar o tempo médio de finalização. Várias estratégias têm sido propostas para oferecer uma 
solução em tempo computacionalmente viável. Suponha um conjunto S = ｛ a1, a2, …, an ｝ de tarefas, 
em que cada tarefa ai demanda pi unidades de tempo para ser concluída a partir do momento em que 
é iniciada. As tarefas podem ser executadas apenas uma por vez. Seja ci o tempo para finalização da 
tarefa ai, isto é, o tempo em que a tarefa ai completa seu processamento. Considerando que o objetivo 
é minimizar o tempo médio para finalização de todas as tarefas, ou seja, minimizar: 
Analise as afirmativas a seguir e marque V (verdadeira) ou F (falsa): 
I. ( ) Se as tarefas forem ordenadas pela quantidade de unidades de tempo para serem finalizadas (pi), 
então a complexidade do algoritmo será O(n log n). 
II. ( ) Um algoritmo guloso que processa as tarefas em ordem crescente de pi obtém a solução ótima 
para qualquer conjunto de tarefas. 
III. ( ) Considerando S composto apenas de duas tarefas a1 e a2 com p1 = 3 e p2 = 5, o tempo médio de 
finalização de S é independente da ordem de execução das tarefas. 
IV. ( ) Uma solução gulosa baseada no tempo de processamento de cada tarefa apresenta uma 
estrutura local ótima em cada iteração. Agora, assinale a alternativa que apresenta a sequência correta. 
 
F, F, V, V. 
 
V, V, F, V. (Alternativa correta) 
 
V, F, V, F. 
 
F, V, F, V. 
2. O algoritmo de Prim é um dos algoritmos mais tradicionais aplicados ao problema da árvore 
geradora mínima de um grafo. Diversas estruturas de dados podem ser utilizadas tanto na 
modelagem do grafo como na representação da fila de prioridades usada por ele. Apesar disso, o seu 
caráter iterativo e incremental na condução das expansões sobre uma subárvore inicial não é 
alterado. Considerando que o algoritmo de Prim foi executado sobre o grafo a seguir e que o vértice a 
foi tomado como inicial, avalie as afirmativas a respeito: 
 
I. O maior tamanho alcançado pela fronteira é de 3 vértices. 
II. O último vértice a ser inserido na solução é o d. 
III. Após a terceira iteração, o vértice e se torna parte da solução. 
IV. A soma dos pesos da árvore final tem valor 18. Quais estão corretas? 
 
II, III e IV. 
 
 
I e II. (Alternativa correta) 
 
II e IV. 
 
 
I, II e III. 
 
3. Dado um grafo não orientado e conexo G = (V, E), pode-se dizer que uma árvore geradora T é um 
subgrafo que consegue visitar todos os n vértices de G a partir de n - 1 arestas. Dessa forma, um grafo 
G pode ter muitas árvores geradoras e, mesmo assim, alcançar todos os vértices. 
 
 
A partir do grafo, determine suas árvores geradoras. 
 
AG1 = ｛(a,c), (c,d), (d,b), (d,e)｝, AG2 = {(a,d), (c,d), (d,b), (d,e)}, AG3 = {(a,c), (a,d), (d,b), (d,e)}. 
 (Alternativa correta) 
 
AG1 = ｛(a,c), (c,d), (d,b), (d,e)｝, AG2 = {(a,d), (c,d), (d,b), (d,e)}, AG3 = {(a,c), (a,a), (d,b), (d,e)}. 
 
AG1 = ｛(a,c), (c,d), (d,b), (d,e)｝, AG2 = {(a,d), (c,d), (d,b), (d,e)}, AG3 = {(a,c), (a,d), (d,b), (a,e)}. 
 
AG1 = ｛(a,c), (c,d), (d,b), (d,e)｝, AG2 = {(a,d), (c, e), (d,b), (d,e)}, AG3 = {(a,c), (a,d), (d,b), (d,e)}. 
 
4. É comum encontrar as árvores geradoras T ao ser fornecido um grafo não direcionado e conexo G = 
(V, E). Entretanto, é possível fazer uma engenharia reversa para encontrar o grafo G = (V, E) a partir de 
suas árvores geradoras T. As árvores geradoras G são as seguintes: AG1 = ｛(a,d), (d,b), (b,c)｝, 
AG2 = {(d,a), (a,c), (c,b)}, 
AG3 = {(d,b), (b,c), (c,a)}, 
AG4 = {(b,d), (d,a), (a,c)}, 
AG5 = {(d,b), (b,a), (a,c)}, 
AG6 = {(d,a), (a,b), (b,c)}, 
AG7 = {(d,a), (a,b), (a,c)}, 
AG8 = {(d,b), (a,b), (c,b)}. 
De acordo com as oito árvores geradoras, determine o grafo G. 
 
G = (V = ｛a,b,c,d｝ e E = {(a,d), (a,b), (a,c), (d,b), (c,b)}). (Alternativa correta) 
 
G = (V = ｛a,b,c,d｝ e E = {(a,d), (a,a), (a,c), (d,b), (c,b)}). 
 
G = (V = ｛a,b,c,d,e｝ e E = {(a,d), (a,b), (a,c), (d,b), (c,b)}). 
 
G = (V = ｛a,b,c,d｝ e E = {(a,d), (a,b), (a,c), (d,b), (d,c)}). 
 
5. A principal finalidade das árvores geradoras é visitar todos os n vértices de determinado grafo – 
isso a partir de n - 1 arestas. Entretanto, há uma especialidade das árvores geradoras chamadas de 
árvores geradoras mínimas, sendo classicamente conhecidas por conta dos algoritmos de Prim e 
Kruskal. A figura 3 apresenta um grafo para identificar a sua árvore geradora mínima. 
 
De acordo com a figura, determine as arestas que compõem a árvore geradora mínima deste grafo. 
 
AGM = ｛(a,e),(e,c), (c,b), (b,d)｝ (Alternativa correta) 
 
AGM = ｛(a,e),(e,c), (c,b), (a,d)｝. 
 
AGM = ｛(a,e),(e,c), (e,b), (b,d)｝. 
 
AGM = ｛(a,b),(e,c), (c,b), (b,d)｝. 
 
6. Os algoritmos de Prim e Kruskal constituem estratégias clássicas para a obtenção da árvore 
geradora mínima de grafos. Ambos podem alcançar bom desempenho computacional desde que suas 
particularidades sejam levadas em consideração durante a implementação. Apesar disso, os dois 
algoritmos diferem significativamente quanto ao processo de obtenção da solução ótima. Nesse 
contexto, considere os grafos (a) e (b) apresentados a seguir e as seguintes condições: 
 
Considere o seguinte: - Apesar de as arestas ainda não adicionadas à solução não estarem 
explicitamente representadas, ambos os grafos são conexos e não direcionados. - Cada grafo representa 
a árvore geradora mínima que está sendo construída por um dos algoritmos. - As 4 arestas 
representadas por linhas sólidas indicam a parte da árvore geradora mínima que já foi construída. - O 
próximo passo a ser executado por um dos algoritmos é representado por uma linha tracejada. Assinale 
a alternativa que apresenta a análise correta das seguintes afirmativas: 
I. Os grafos (a) e (b) indicam o processo de geração da árvore geradora mínima dos algoritmos de 
Kruskal e de Prim, respectivamente. 
PORQUE 
 II. A distância geométrica entre os vértices está sendo usada como medida de peso associada às arestas 
do grafo. 
 
As afirmações I e II são proposições verdadeiras e a II justifica a I. 
 
 
A afirmação I é uma proposição verdadeira e a II, falsa. 
 
 
A afirmação I é uma proposição falsa e a II, verdadeira. (Alternativa correta) 
 
As afirmações I e II são proposições verdadeiras, mas a II não justifica a I. 
 
7. O BFS implementa uma fila na qual são inseridos os nós conectados ao nó visitado em cada 
camada. Esse processo se repete até que nenhum outro nó conste na fila. Dado o grafo, determine a 
sequência da fila se for executado um algoritmo do tipo BFS: 
 
 
 
[A, B, C] 
[C, E, D] 
[E, D] 
[D, F] 
[F] 
 
 
[B, C] 
[C, E, D] 
[E, D] 
[D, F] 
[F] 
[] 
 
[A] 
[B, C] 
[C, E, D] 
[E, D] 
[D, F] 
[F] 
[] 
 (Alternativa correta) 
 
[A] 
[B, C] 
[E, D] 
[D] 
[F] 
[] 
 
8. Os algoritmos de correspondência de strings incluem o algoritmo de força bruta (BF), o algoritmo 
Knuth-Morris-Pratt (KMP) e o algoritmo Boyer-Moore (BM), alguns dos algoritmos de pesquisa mais 
famosos. Todos eles executam os passos de busca de padrões com algumas semelhanças. Qual 
alternativa representa uma semelhança entre esses algoritmos? 
 
A pesquisa inicial por comparação da janela de caracteres é feita com caracteres do texto. Esse processo 
é denominado "tentativa". 
 
Os algoritmos, assim que encontram o padrão no texto, marcam o primeiro padrão e param. 
 
Esses algoritmos mudam a janela para a direita para que a pesquisa analise outra posição no vetor que 
armazena o padrão. 
 
Os algoritmos escaneiam o texto pela janela. Cada janela tem o mesmo comprimento do padrão a ser 
pesquisado e é igual a m. (Alternativa correta) 
 
9. Um problema tradicional em que algoritmos gulosos são aplicados é o de escalonar os intervalos de 
tempo para uso de determinado recurso. Considerando um conjunto R de n requisições, em que cada 
requisição i retém o recurso por um intervalo de tempo[ s(i), f(i) ], o objetivo é atender ao maior 
número de solicitações possível. Porém, requisições com sobreposição de tempo são descartadas. 
Nesse cenário, analise as afirmações a seguir e a relação proposta entre elas: I. Um algoritmo guloso 
que itera sobre R aceitando a primeira requisição i com o menor f(i) possível, retorna um conjunto A 
com uma solução ótima, considerando que, para todos os índices r ≤ k, tem-se f(ir) ≤ f(jk). PORQUE II. 
Se for assumido que A não é um conjunto composto pela solução ótima, uma contradição é obtida 
para a condição de parada R = ∅ do algoritmo. Assinale a alternativa correta. 
 
A afirmação I é uma proposição verdadeira e a II é uma proposição falsa. 
 
As afirmações I e II são proposições verdadeiras e a II é uma justificativa correta da I. 
 (Alternativa correta) 
 
As afirmações I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. 
 
A afirmação I é uma proposição falsa e a II é uma proposição verdadeira. 
 
10. Vários são os problemas que podem ser modelados com grafos. Dentre os vários benefícios dessa 
modelagem, estão o uso de estruturas de dados otimizadas e a possibilidade de projetar algoritmos 
gulosos adaptados às particularidades do cenário. Um exemplo tradicional é o problema conhecido 
como cobertura de conjunto: dados um conjunto a ser coberto e uma coleção de subconjuntos, o 
objetivo é encontrar a menor coleção de subconjuntos cuja união resulte no conjunto informado. 
Uma típica aplicação desse problema é na distribuição de instalações a um custo mínimo. Um Estado 
brasileiro está no início de um planejamento e está decidindo onde instalar escolas. Existem apenas 
duas restrições: cada escola deve estar em apenas uma cidade e ninguém deve ter que viajar mais do 
que 30 quilômetros para chegar a uma delas. A figura a seguir descreve as cidades que estão a 30 
quilômetros umas das outras. O objetivo é definir o número mínimo de escolas necessárias 
satisfazendo às restrições. 
 
Esse é um problema típico de cobertura de conjunto. Para cada cidade x, seja Sx o conjunto de cidades 
distantes 30km dele. Uma escola em x irá essencialmente “cobrir” essas outras cidades. Um modelo 
computacional comum para esse cenário é o uso de grafos: cada conjunto Sx vai ser representado por 
vértices e as distâncias de 30km que unem cada par de cidades por arestas. Considere esse cenário e o 
seguinte algoritmo guloso para ele: Algoritmo guloso Entrada: Um conjunto de elementos B e uma 
coleção S1, …, Sm. 
Saída: A seleção dos Si cuja união é B. 1. Repetir até que todos os elementos de B estejam cobertos. 
2. Pegue o conjunto Si com maior número de elementos não cobertos. 
3. Adicione Si à seleção que será retornada. Analise as afirmativas a seguir: 
I – O algoritmo guloso encontra a solução ótima para o problema. 
II – O primeiro Si selecionado pelo algoritmo corresponde ao vértice "a". 
III – Na segunda iteração, o algoritmo deve escolher entre quatro elementos possíveis. 
IV – O vértice de maior grau compõe a solução ótima para o problema. Quais estão corretas? 
 
II e III. (Alternativa correta) 
 
I e II. 
 
II e IV. 
 
I, II e III. 
 
 
 
	1. Considere o texto "aaaaaaaaaaa". Quantas vezes o padrão "aaa" é encontrado pela busca com o algoritmo de Boyer-Moore?
	2. As árvores geradoras vêm sendo amplamente usadas por sua grande utilidade e contribuições em projetos que buscam alcançar todos os vértices de determinado grafo por meio de um número de arestas menor que o normalmente utilizado no grafo total, send...
	3. O algoritmo de busca tradicional de Boyer-Moore depende de um pequeno número de comparações de caracteres e grandes mudanças realizadas no texto durante a busca. O algoritmo de Boyer-Moore: I. funciona corretamente apenas com a tabela de símbolos r...
	4. Algumas características do algoritmo de Kruskal para o problema da árvore geradora mínima possibilitam que ele seja aplicado em uma grande variedade de cenários. Dentre as mais destacadas, a estratégia de explorar múltiplas árvores em paralelo faz ...
	Nesse contexto, considere a aplicação do algoritmo de Kruskal no grafo a seguir e avalie as afirmativas a respeito:
	I - A aresta de maior peso que compõe a árvore geradora mínima final tem valor 6.
	II - O número de árvores intermediárias geradas e compostas por mais de 1 vértice é, no máximo, 2.
	III - Para as primeiras i iterações, com i = 1, 2 e 3, as arestas de peso i são inseridas na solução nessa ordem.
	IV - O valor do custo total da árvore geradora mínima (soma dos pesos das arestas) é 15. Quais estão corretas?
	5. Junto da escolha do algoritmo, é importante adequar a forma como a entrada de dados será representada. Soluções comuns envolvem o uso de vetores, a lista de adjacência e a matriz de adjacência. Dado o grafo, selecione a alternativa que apresenta a ...
	6. Várias são as estruturas de dados que podem ser empregadas na implementação do algoritmo de Kruskal para o problema da árvore geradora mínima de um grafo. Cada estrutura usada, no entanto, vai impactar de maneira diferente no desempenho computacion...
	1. Busca: Dada uma lista de conjuntos e um elemento x a ser buscado, ela retorna o conjunto da qual x é um elemento. Esse retorno pode ser denotado por Conjunto(x).
	2. União: Dados dois conjuntos disjuntos, ela realiza a união desses dois conjuntos gerando um terceiro a partir da remoção dos dois conjuntos originais. Tendo como base o uso da estrutura de dados União-Busca, assinale a alternativa que preenche corr...
	7. Embora seja um algoritmo tradicional para o problema da árvore geradora mínima de grafos, o algoritmo de Prim tem o seu funcionamento condicionado ao atendimento de certos pré-requisitos. Tanto as características do grafo como as estruturas de dado...
	Julgue V (verdadeiro) ou F (falso) as afirmativas a respeito do comportamento do algoritmo:
	( ) A alteração do peso w(e) de cada aresta e por w(e) * w(e) compromete a obtenção da árvore geradora mínima.
	( ) A solução obtida pelo algoritmo depende da escolha do vértice inicial usado para iniciar a construção da árvore.
	( ) A remoção de 3 arestas de qualquer vértice inviabiliza a obtenção da árvore pelo algoritmo.
	( ) O cuso total da árvore geradora mínima do grafo é inferior à soma dos pesos das arestas do vértice de maior grau. Assinale a alternativa que apresenta a sequência correta.
	8. Assim como os tipos de problemas podem ser diferentes entre um caso e outro, também os algoritmos e técnicas mais adequados para solucionar o problema variam. Um dos algoritmos mais utilizados é o de busca em largura. Assinale a alternativa que des...
	9. Para compreender o conceito de árvores geradoras, é preciso antes entender as definições de grafos e árvores, saber diferenciar o conjunto das arestas e vértices, assim como identificar o contexto de aplicação dessa estrutura de dados, não confundi...
	I. Uma árvore geradora é um subgrafo gerador cíclico, não direcionado e com o menor custo possível.
	II. Uma árvore tem complexidade na ordem de O(N3) e tem ciclo em sua estrutura, por exemplo: ciclo euleriano.
	III. Um corte C (S, V-S) é uma partição no grafo G = (V, E) que busca auxiliar na expansão das arestas da árvore geradora.
	IV. Toda árvore geradora mínima é uma árvore geradora, assim como toda árvore geradora é uma árvore geradora mínima.
	V. Toda árvore é um grafo, porém nem todo grafo pode ser uma árvore, pois este último goza de propriedades mais abrangentes. Quais estão corretos?
	10. Os conceitos que fundamentam a construção de estratégias gulosas são importantes para que uma modelagem precisa possa ser empregada durante a proposição de soluções. Essa análise deve preceder, inclusive, a etapa de projeto de um algoritmo guloso....
	1. Um típico problema em que algoritmos gulosos são aplicados é conhecido como agendamento para minimizar o tempo médio de finalização. Várias estratégias têm sido propostas para oferecer uma solução em tempo computacionalmente viável. Suponha um conj...
	I. () Se as tarefas forem ordenadas pela quantidade de unidades de tempo para serem finalizadas (pi), então a complexidade do algoritmo será O(n log n).
	II. ( ) Um algoritmo guloso que processa as tarefas em ordem crescente de pi obtém a solução ótima para qualquer conjunto de tarefas.
	III. ( ) Considerando S composto apenas de duas tarefas a1 e a2 com p1 = 3 e p2 = 5, o tempo médio de finalização de S é independente da ordem de execução das tarefas.
	IV. ( ) Uma solução gulosa baseada no tempo de processamento de cada tarefa apresenta uma estrutura local ótima em cada iteração. Agora, assinale a alternativa que apresenta a sequência correta.
	2. O algoritmo de Prim é um dos algoritmos mais tradicionais aplicados ao problema da árvore geradora mínima de um grafo. Diversas estruturas de dados podem ser utilizadas tanto na modelagem do grafo como na representação da fila de prioridades usada ...
	I. O maior tamanho alcançado pela fronteira é de 3 vértices.
	II. O último vértice a ser inserido na solução é o d.
	III. Após a terceira iteração, o vértice e se torna parte da solução.
	IV. A soma dos pesos da árvore final tem valor 18. Quais estão corretas?
	3. Dado um grafo não orientado e conexo G = (V, E), pode-se dizer que uma árvore geradora T é um subgrafo que consegue visitar todos os n vértices de G a partir de n - 1 arestas. Dessa forma, um grafo G pode ter muitas árvores geradoras e, mesmo assi...
	A partir do grafo, determine suas árvores geradoras.
	4. É comum encontrar as árvores geradoras T ao ser fornecido um grafo não direcionado e conexo G = (V, E). Entretanto, é possível fazer uma engenharia reversa para encontrar o grafo G = (V, E) a partir de suas árvores geradoras T. As árvores geradoras...
	De acordo com as oito árvores geradoras, determine o grafo G.
	5. A principal finalidade das árvores geradoras é visitar todos os n vértices de determinado grafo – isso a partir de n - 1 arestas. Entretanto, há uma especialidade das árvores geradoras chamadas de árvores geradoras mínimas, sendo classicamente conh...
	​De acordo com a figura, determine as arestas que compõem a árvore geradora mínima deste grafo.
	6. Os algoritmos de Prim e Kruskal constituem estratégias clássicas para a obtenção da árvore geradora mínima de grafos. Ambos podem alcançar bom desempenho computacional desde que suas particularidades sejam levadas em consideração durante a implemen...
	7. O BFS implementa uma fila na qual são inseridos os nós conectados ao nó visitado em cada camada. Esse processo se repete até que nenhum outro nó conste na fila. Dado o grafo, determine a sequência da fila se for executado um algoritmo do tipo BFS:
	8. Os algoritmos de correspondência de strings incluem o algoritmo de força bruta (BF), o algoritmo Knuth-Morris-Pratt (KMP) e o algoritmo Boyer-Moore (BM), alguns dos algoritmos de pesquisa mais famosos. Todos eles executam os passos de busca de padr...
	9. Um problema tradicional em que algoritmos gulosos são aplicados é o de escalonar os intervalos de tempo para uso de determinado recurso. Considerando um conjunto R de n requisições, em que cada requisição i retém o recurso por um intervalo de tempo...
	Nesse cenário, analise as afirmações a seguir e a relação proposta entre elas: I. Um algoritmo guloso que itera sobre R aceitando a primeira requisição i com o menor f(i) possível, retorna um conjunto A com uma solução ótima, considerando que, para to...
	10. Vários são os problemas que podem ser modelados com grafos. Dentre os vários benefícios dessa modelagem, estão o uso de estruturas de dados otimizadas e a possibilidade de projetar algoritmos gulosos adaptados às particularidades do cenário. Um ex...
	Esse é um problema típico de cobertura de conjunto. Para cada cidade x, seja Sx o conjunto de cidades distantes 30km dele. Uma escola em x irá essencialmente “cobrir” essas outras cidades. Um modelo computacional comum para esse cenário é o uso de gra...
	I – O algoritmo guloso encontra a solução ótima para o problema.
	II – O primeiro Si selecionado pelo algoritmo corresponde ao vértice "a".
	III – Na segunda iteração, o algoritmo deve escolher entre quatro elementos possíveis.
	IV – O vértice de maior grau compõe a solução ótima para o problema. Quais estão corretas?