K-Поток

<math>k</math>-Поток ([math]\displaystyle{ k }[/math]-Flow) - Пусть для графа [math]\displaystyle{ G = (V,E) }[/math] [math]\displaystyle{ (D,f) }[/math] есть упорядоченная пара такая, что [math]\displaystyle{ D }[/math] --- ориентация [math]\displaystyle{ E(G) }[/math] и [math]\displaystyle{ f }[/math] --- весовая функция на [math]\displaystyle{ E: \, E(G) \rightarrow Z }[/math], где [math]\displaystyle{ Z }[/math] --- множество целых чисел. Для каждой [math]\displaystyle{ v \in V(G) }[/math] обозначим

[math]\displaystyle{ f^{+}(v) = \sum\{f(e)\}, \quad f^{-}(v) = \sum\{f(e)\}, }[/math]

где суммирование ведется по всем ориентированным ребрам (при ориентации [math]\displaystyle{ D }[/math]), конец (соответственно начало) которых есть [math]\displaystyle{ v }[/math]. [math]\displaystyle{ k }[/math]-поток на [math]\displaystyle{ G }[/math] есть упорядоченная пара [math]\displaystyle{ (D,f) }[/math] такая, что [math]\displaystyle{ f^{+}(v) = f^{-}(v) }[/math] для каждой вершины [math]\displaystyle{ v }[/math] и [math]\displaystyle{ |f(e)| \lt k }[/math] для каждого ориентированного ребра [math]\displaystyle{ e }[/math]. Нигде не нулевой [math]\displaystyle{ k }[/math]-поток (nowhere-zero [math]\displaystyle{ k }[/math]-flow) есть поток такой, что [math]\displaystyle{ f(e) \neq 0 }[/math] для всех [math]\displaystyle{ e \in E }[/math].

Литература

[Discrete Math.]