K-Поток: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>\,G = (V,E)\,\,(D,f)</math> есть упорядоченная пара такая, что | ||
<math>\,D</math> — [[ориентация графа|ориентация]] <math>\,E(G)</math> и <math>\,f</math> | |||
<math>D</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>\,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>\,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.] | ||
Текущая версия от 12:58, 22 июня 2011
[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.]