Xarxa de flux: diferència entre les revisions

En [[teoria de grafs]], una '''xarxa de flux''' és un [[graf dirigit]] en que cada aresta està ponderada amb un '''flux''' i una '''capacitat'''. La suma del flux d'una aresta no pot ser superior a la seva capacitat. Moltes vegades s'anomena al graf dirigit, '''xarxa''', als vertexs, '''nodes''', i a les arestes, '''arcs'''. La suma de flux que entra en un node ha de ser igual a la suma de flux que en surt, a excepció de les '''fonts''', que tenen més flux sortint, o els '''pous''', que tenen més flux entrant. Una xarxa pot ser utilitzada per modelitzar el tràfic en un sistema de carreteres, líquids dins de canyeries, corrents en un circuit elèctric, o qualsevol cosa que viatgi a través d'una xarxa de nodes.

| '''ConstantRestricció de capacitat''': || <math>\ f(u,v) \le c(u,v)</math>. El flux que travessa una aresta no pot excedir la seva capacitat.