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