K-Поток: различия между версиями

'''<math>\,k</math>-Поток''' (''[[k-Flow|<math>\,k</math>-Flow]]'') —

Пусть для [[граф|графа]] <math>\,G = (V,E)\,\,(D,f)</math> есть упорядоченная пара такая, что

<math>\,D</math> — [[ориентация графа|ориентация]] <math>\,E(G)</math> и <math>\,f</math>

— весовая функция на <math>E: \, E(G) \rightarrow Z,</math> где <math>\,Z</math> —

::<math> f^{+}(v) = \sum\{f(e)\}, \quad f^{-}(v) = \sum\{f(e)\},</math>

ориентации <math>\,D,</math>) конец (соответственно начало) которых есть <math>\,v.</math> <math>\,k</math>-поток на

<math>\,G</math> есть упорядоченная пара <math>\,(D,f)</math> такая, что <math>\,f^{+}(v) = f^{-}(v)</math>

для каждой [[вершина|вершины]] <math>\,v</math> и <math>\,|f(e)| < k</math> для каждого ориентированного

ребра <math>\,e.</math> Нигде не нулевой <math>\,k</math>-поток ([[nowhere-zero k-flow|nowhere-zero <math>\,k</math>-flow]])

0</math> для всех <math>e \in E.</math>

* [Discrete Math.]