K-Поток

[math]\displaystyle{ \,k }[/math]-Поток ([math]\displaystyle{ \,k }[/math]-Flow) — Пусть для графа [math]\displaystyle{ \,G = (V,E)\,\,(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.]