Questão 1 - Explorando os Limites do DFS em Grafos Direcionados


Considere o grafo direcionado abaixo, representado por sua lista de adjacência:

Grafo G:
a → b, d  
b → e  
c → f  
d →  
e → g  
f → f  
g → d

Sabendo que:

  • O algoritmo DFS é executado com os vértices em ordem alfabética (a, b, c, d, e, f, g),

  • O grafo é direcionado,

  • Não há arestas paralelas nem pesos,

  • O algoritmo DFS registra os tempos de descoberta (d) e finalização (f),

  • Com base nesses tempos, é possível classificar as arestas em: tree, forward, backward e cross,

Após a execução completa do DFS, qual das seguintes afirmações é falsa?

A) A aresta f → f é uma aresta backward, indicando a presença de um ciclo.
B) A aresta g → d é classificada como uma forward edge.
C) A árvore de recursão de DFS terá duas árvores distintas (floresta), uma começando por a e outra por c.
D) A aresta c → e será classificada como uma cross edge, já que e já foi finalizado quando c é visitado.

Comentários

Postar um comentário

Postagens mais visitadas deste blog

Questão 3 - Quiz sobre Fluxo em Redes

NATO Logistics Flow — Quiz Question NATO is coordinating the shipment of military supplies to reinforce its eastern flank. Units are produced in the United States and Germany , entering Europe through the ports of Rotterdam and Naples . From there, they move to the logistics hubs of Rotterdam and the Czech Republic , with final delivery to three defense lines: Baltic States (demand 50) , Eastern Poland (demand 60) , and Romania (demand 40) . Capacities (in units/week): US → Rotterdam : 15 US → Naples : 15 Germany → Rotterdam : 15 Germany → Czech Republic : 15 Rotterdam → Baltics : 20 Rotterdam → Eastern Poland : 15 Czech Republic → Eastern Poland : 15 Czech Republic → Romania : 15 Naples → Romania : 10 Based on the maximum flow model in directed graphs : What is the maximum supply that can reach Romania ? Why can Eastern Poland not receive more than 30 units, even if production is sufficient at the sources? If the Baltic States demand 50 but can o...
Leia mais

Questão 2 – Quiz sobre Interpretação de Estrutura

No grafo de emendas parlamentares, você encontra que apenas 10% dos vértices estão em SCCs com mais de 3 nós, e os outros 90% estão em SCCs unitários. Analise as afirmações: A rede apresenta alta reciprocidade estrutural, já que a maioria dos nós pertence a SCCs. O fato de existirem muitos SCCs unitários indica baixa reciprocidade estrutural. Apenas olhar o grau de entrada e saída dos nós seria suficiente para explicar essa distribuição de SCCs. Emendas que formam SCCs maiores podem indicar blocos fechados de influência política. Qual alternativa está correta? A) Apenas 1 e 2 são verdadeiras. B) Apenas 2 e 4 são verdadeiras.  C) Apenas 1, 3 e 4 são verdadeiras. D) Apenas 2, 3 e 4 são verdadeiras. E) Nenhuma das anteriores.
Leia mais

Fofoca, Vinho e Redes

Nos últimos dias, fiquei com uma dúvida interessante ao ler um exemplo do livro de redes: a história da festa em que alguém descobre qual é o melhor vinho e essa informação acaba se espalhando entre os convidados. A minha primeira interpretação foi: “ah, claro, isso mostra como a fofoca se espalha rápido”. Mas, na aula, o professor me corrigiu — e aí começou meu aprendizado. O que eu entendi depois? O texto, na verdade, está descrevendo o modelo de redes aleatórias (Erdős–Rényi). Nesse modelo: As conexões entre as pessoas surgem ao acaso. A propagação da informação só decola quando a rede atinge um limiar crítico de conectividade . Nesse ponto, aparece a chamada componente gigante — e qualquer informação consegue se espalhar para quase todos. Esse é o momento em que a rede “ganha vida” : de repente, ela deixa de ser um conjunto de pares isolados e passa a funcionar como um todo conectado. As redes aleatórias são a base, mas na realidade não descrevem as redes sociais humanas. Isso por...
Leia mais