Определение сети, потока

Определение сети

Определение:

Сетью называется взвешенный ориентированный граф [math]G=(V,E,c)[/math], где [math]c\colon E\to R[/math] - весовая функция.

Определение потока

Определение:

Потоком [math]f[/math] в сети [math]G=(V,E,c)[/math] называется функция [math]f\colon E\to R[/math], удоволетворяющая условиям: 1) [math]0\le f(e)\le c(e)[/math] для всех [math]e\in E[/math]; 2) [math]f(v-) = f(v+)[/math] для всех [math]v\in V, v\ne s, v\ne t[/math], где [math]f(v-)=\sum\limits_{w\in v-} f(w, v), f(v+)=\sum\limits_{w\in v+} f(v, u)[/math]. Здесь [math]s[/math] - источник, а [math]t[/math] - сток сети [math]G[/math]; через [math]v+[/math] обозначено множество вершин, к которым идут дуги из вершины [math]v[/math]; через [math]v-[/math] обозначено множество вершин, из которых идут дуги в вершину [math]v[/math]; [math]c(e)[/math] называется пропускной способностью дуги [math]e[/math] и неотрицательно.