Diferenças
Aqui você vê as diferenças entre duas revisões dessa página.
| Ambos lados da revisão anterior Revisão anterior Próxima revisão | Revisão anterior | ||
| grafos:maxfluxmincut [2022/06/03 16:52] – edição externa 127.0.0.1 | grafos:maxfluxmincut [2022/06/03 17:37] (atual) – edição externa 127.0.0.1 | ||
|---|---|---|---|
| Linha 3: | Linha 3: | ||
| <WRAP group> | <WRAP group> | ||
| <WRAP half column> | <WRAP half column> | ||
| - | ** Resumo: ** Suponha que tenhamos, entre um reservatório de água e um grande consumidor de água, um sistema de encanamentos. Os canos (arestas) tem uma certa capacidade (em L/s) de fluxo suportada. No que segue, vamos argumentar que o maior fluxo possível, da fonte para o consumidor, corresponde a menor capacidade conjunta de um conjunto de canos que corresponde a um corte do grafo, com a fonte em uma partição e o consumidor em outra. A notação será inspirada por mecânica dos fluidos, | + | ** Resumo: ** Suponha que tenhamos, entre um reservatório de água e um grande consumidor de água, um sistema de encanamentos. Os canos (arestas) tem uma certa capacidade (em L/s) de fluxo suportada. No que segue, vamos argumentar que o maior fluxo possível, da fonte para o consumidor, corresponde a menor capacidade conjunta de um conjunto de canos que corresponde a um corte do grafo, com a fonte em uma partição e o consumidor em outra. A notação será motivada pelo [[http://en.wikipedia.org/wiki/Divergence_theorem|Teorema da divergência]]. |
| Para tornar o que dissemos acima preciso, precisamos fixar algumas definições, | Para tornar o que dissemos acima preciso, precisamos fixar algumas definições, | ||
| Linha 21: | Linha 21: | ||
| <WRAP center round tip 90%> | <WRAP center round tip 90%> | ||
| - | * Interpretando $f$ como "kg de fluido por segundo atravessando uma seção transversal do cano", podemos interpretar o segundo axioma como a lei de preservação de massa, pois \nabla \cdot f(x)$ seria menos a taxa de acúmulo de massa em um vértice. | + | * Interpretando $f$ como "kg de fluido por segundo atravessando uma seção transversal do cano", podemos interpretar o segundo axioma como a lei de preservação de massa, pois $\nabla \cdot f(x)$ seria menos a taxa de acúmulo de massa em um vértice. |
| * Interpretando como " | * Interpretando como " | ||
| * Interpretando como corrente de cargas num circuito elétrico, é supor o não acúmulo de cargas (Coulomb) e nenhum ponto. | * Interpretando como corrente de cargas num circuito elétrico, é supor o não acúmulo de cargas (Coulomb) e nenhum ponto. | ||