Транспортная сеть

---

В теории графов транспортная сеть — ориентированный граф ${\displaystyle G=(V,E)}$ , в котором каждое ребро ${\displaystyle (u,v)\in E}$ имеет неотрицательную пропускную способность ${\displaystyle c(u,v)\geqslant 0}$ и поток ${\displaystyle f(u,v)}$. Выделяются две вершины: источник ${\displaystyle s}$ и сток ${\displaystyle t}$ такие, что любая другая вершина сети лежит на пути из ${\displaystyle s}$ в ${\displaystyle t}$, при этом ${\displaystyle s\neq t}$. Транспортная сеть может быть использована для моделирования, например, дорожного трафика.

Целочисленная транспортная сеть — транспортная сеть, все пропускные способности рёбер которой — целые числа.

Транспортная сеть (flow network) — ориентированный граф ${\displaystyle G(V,E),}$ в котором

Поток (flow) — функция ${\displaystyle f\colon V\times V\rightarrow \mathbb {R} _{+}}$ (в некоторых источниках также ${\displaystyle f\colon E\rightarrow \mathbb {R} _{+}}$) со следующими свойствами:

Величина потока (value of flow) — сумма потоков из источника или сумма потоков в сток ${\displaystyle |f|=\sum _{v\in V}f(s,v)=\sum _{v\in V}f(v,t)}$.

---