Vés al contingut

Problema del flux màxim

De la Viquipèdia, l'enciclopèdia lliure
(S'ha redirigit des de: Flux màxim)

En optimització i teoria de grafs, el problema de flux màxim serveix per trobar la quantitat màxima de flux que pot passar per una xarxa de flux, des d'una sola font fins a un sol pou.

El problema de flux màxim pot ser vist com un cas especial d'altres problemes de xarxes més complexes, com ara el problema de circulació. El valor màxim d'un flux s-t és igual a la capacitat mínima d'un tall s-t a la xarxa, tal com demostra el teorema de flux màxim tall mínim.

Definició matemàtica

[modifica]

Sigui una xarxa en què els vèrtexs són la font i el pou de , respectivament.

La capacitat d'una aresta ve donada per la funció , denominada o . Representa la quantitat màxima de flux que pot passar a través de l'aresta.
El flux ve donat per la funció , denominat o , i subjecte a les següents restriccions:
1. , per cada (restricció de capacitat)
2. , per cada (conservació del flux)
El valor del flux es defineix com , on és la font de . Representa la suma total de flux que passa des de la font fins al pou.

El problema de flux màxim pretén maximitzar , és a dir, enviar tant flux com sigui possible des de fins .