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

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

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

Сетью называется взвешенный ориентированный граф [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]f_{uv}=-f_{vu}[/math] (антисимметричность); 2) [math]f_{uv}\le c_{uv}[/math] (подчинение пропускным способностям), если ребра нет, то [math]c_{uv}=0[/math]; 3) [math]\sum\limits_v f_{uv}=0[/math] для всех вершин [math]u[/math], кроме [math]s[/math] и [math]t[/math] (закон сохранения потока).

Шаблон:Альтернативное определение (по Асанову) Число [math]f(v,w)[/math] можно интерпретировать, например, как количество жидкости, поступающей из [math]v[/math] в [math]w[/math] по дуге [math](v,w)[/math]. С этой точки зрения значение [math]f(v-)[/math] может быть интерпретировано как поток, втекающий в вершину [math]v[/math], а [math]f(v+)[/math] - вытекающий из [math]v[/math]. Условие 1) называется условием ограничения по пропускной способности, а условие 2) - условием сохранения потока в вершинах; иными словами, поток, втекающий в вершину [math]v[/math], отличную от [math]s[/math] или [math]t[/math], равен вытекающему из неё потоку.