Determine a capacidade máxima de distribuição da seguinte rede.

Análise da Questão de Fluxo Máximo

Alternativa B - 160

Esta questão trata de um problema clássico de Teoria dos Grafos, especificamente o cálculo de Fluxo Máximo em uma rede. O objetivo é determinar a maior quantidade de "fluxo" (seja dados, água, veículos, etc.) que pode sair do ponto de origem (Nó A) e chegar ao ponto de destino (Nó F), respeitando as capacidades máximas de cada conexão.

Passo a Passo do Cálculo

Para resolver, podemos utilizar o método de encontrar caminhos aumentantes (caminhos da origem ao destino com capacidade disponível) e somar o fluxo que passa por eles, atualizando as capacidades conforme usamos as conexões.

1. Caminho 1: $A \to B \to D \to F$

• Capacidades: A \to B (100), B \to D (70), D \to F (60).
• O "gargalo" (menor valor) é 60 (aresta D \to F).
• Enviamos 60 unidades.
• Capacidades Restantes: A \to B sobra 40; B \to D sobra 10; D \to F fica 0 (saturada).

1. Caminho 2: $A \to B \to E \to F$

• Capacidades disponíveis: A \to B (40), B \to E (70), E \to F (120).
• O gargalo agora é 40 (aresta A \to B, que foi parcialmente usada no caminho anterior).
• Enviamos mais 40 unidades.
• Total Acumulado: $60 + 40 = 100$.
• Capacidades Restantes: A \to B fica 0 (saturada); B \to E sobra 30; E \to F sobra 80.

1. Caminho 3: $A \to C \to E \to F$

• Capacidades disponíveis: A \to C (80), C \to E (60), E \to F (80 restantes).
• O gargalo é 60 (aresta C \to E).
• Enviamos mais 60 unidades.
• Total Acumulado: $100 + 60 = 160$.
• Capacidades Restantes: A \to C sobra 20; C \to E fica 0 (saturada); E \to F sobra 20.

1. Verificação Final

• Não existem mais caminhos viáveis da origem ao destino. O caminho pela aresta A \to B está bloqueado (capacidade 0) e o caminho pela aresta C \to E também está bloqueado.
• Fluxo Máximo Total = 160.

Validação pelo Corte Mínimo

Uma forma rápida de confirmar se não estamos perdendo nada é usar o Teorema do Fluxo Máximo e Corte Mínimo. O fluxo máximo é igual à menor capacidade de um corte que separa a origem do destino.

Vamos tentar separar o nó A do nó F cortando apenas algumas arestas:

• Se cortarmos as arestas que saem do conjunto \{A, C\} para o resto da rede:
• Aresta A \to B (Capacidade 100)
• Aresta C \to E (Capacidade 60)
• Soma do Corte: $100 + 60 = 160$.

Como existe um corte de capacidade 160, é impossível enviar mais do que 160 unidades pela rede. Como já conseguimos enviar 160, esta é a resposta exata.

Por que a opção 180 (marcada na imagem) está errada?

A alternativa D (180) é um distrator comum que soma apenas as capacidades de saída da origem ($100 + 80 = 180$) ou de entrada no destino ($60 + 120 = 180$). No entanto, essa abordagem ignora os gargalos internos da rede (como a aresta C \to E limitada a 60 ou D \to F limitada a 60), que impedem que toda a capacidade inicial seja utilizada.

Portanto, a resposta correta é a Alternativa B.