Определение сети, потока — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Определение сети, потока == {{Определение |definition= Сетью называется взвешенный ориентиров…»)
(нет различий)

Версия 17:43, 12 декабря 2010

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

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