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

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

Версия от 16:06, 23 декабря 2009

[math]\displaystyle{ k }[/math]-Поток ([math]\displaystyle{ k }[/math]-Flow) - Пусть для графа [math]\displaystyle{ G = (V,E) }[/math] [math]\displaystyle{ (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.]