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

Материал из Викиконспекты
Версия от 17:45, 12 декабря 2010; Tsar (обсуждение | вклад) (Определение сети, потока)
Перейти к: навигация, поиск

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

Определение:
Сетью называется взвешенный ориентированный граф [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] и неотрицательно.