4194
правки
K-Поток: различия между версиями
Материал из WEGA
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером <'''math>k</math>-Поток''' (''<math>k</math>-Flow'') - Пусть для графа <math>G = (V,E)</math> <math>(D,f)</math> ест...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>k</math>-Поток''' (''[[k-Flow|<math>k</math>-Flow]]'') - | |||
Пусть для графа <math>G = (V,E)</math> | Пусть для [[граф|графа]] <math>G = (V,E)</math> | ||
<math>(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> обозначим | ||
| Строка 8: | Строка 8: | ||
<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 | ребра <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.] | ||
