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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение потока)
(Определение сети)
Строка 4: Строка 4:
 
|definition=
 
|definition=
 
<b>Сетью</b> называется взвешенный ориентированный граф <tex>G=(V,E,c)</tex>, где <tex>c\colon E\to R</tex> - весовая функция.
 
<b>Сетью</b> называется взвешенный ориентированный граф <tex>G=(V,E,c)</tex>, где <tex>c\colon E\to R</tex> - весовая функция.
 +
}}
 +
 +
{{Определение
 +
|definition=
 +
<b>Транспортная сеть</b> (flow network) <tex>G=(V,E)</tex> представляет собой ориентированный граф, в котором каждое ребро <tex>(u,v)\in E</tex> имеет неотрицательную <b>пропускную способность</b> (capacity) <tex>c(u,v)>0</tex>. Если <tex>(u,v)\notin E</tex>, предполагается что <tex>c(u,v)=0</tex>. В транспортной сети выделяются две вершины: <b>источник</b> <tex>s</tex> и <b>сток</b> <tex>t</tex>.
 
}}
 
}}
  

Версия 14:56, 19 декабря 2010

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

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


Определение:
Транспортная сеть (flow network) [math]G=(V,E)[/math] представляет собой ориентированный граф, в котором каждое ребро [math](u,v)\in E[/math] имеет неотрицательную пропускную способность (capacity) [math]c(u,v)\gt 0[/math]. Если [math](u,v)\notin E[/math], предполагается что [math]c(u,v)=0[/math]. В транспортной сети выделяются две вершины: источник [math]s[/math] и сток [math]t[/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[/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]s[/math] имеет нулевую степень захода, а [math]t[/math] имеет нулевую степень исхода); через [math]v+[/math] обозначено множество вершин, к которым идут дуги из вершины [math]v[/math]; через [math]v-[/math] обозначено множество вершин, из которых идут дуги в вершину [math]v[/math]; [math]c(e)[/math] называется пропускной способностью дуги [math]e[/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], равен вытекающему из неё потоку.