K-Поток

Материал из WikiGrapp
Версия от 12:58, 22 июня 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

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

 f^{+}(v) = \sum\{f(e)\}, \quad f^{-}(v) = \sum\{f(e)\},

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

Литература

  • [Discrete Math.]