Аноним

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

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


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


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