Просмотр кода страницы Нигде не нулевой поток

'''Нигде не нулевой поток''' в [[Теория графов|теории графов]] — специальный вид [[Транспортная сеть|сетевого потока]], который связан (двойственностью) с [[Раскраска графов|раскраской]] [[Планарный граф|планарных графов]].

== Определение ==
Пусть ''G'' = ''(V,E)'' — [[ориентированный граф]] и пусть ''M'' — [[абелева группа]]. Отображение φ: ''E'' → ''M'' называется '''потоком''' или ''M''-'''потоком''', если для любой вершины ''v'' ∈ ''V'', выполняется
: <math>\sum_{e \in \delta^+(v)} \phi(e) = \sum_{e \in \delta^-(v)} \phi(e),</math>
где ''δ<sup>+</sup>(v)'' обозначает множество исходящих из ''v'' рёбер, а ''δ<sup>-</sup>(v)'' — множество входящих в ''v''.
Иногда это условие трактуется как [[Правила Кирхгофа|правило Кирхгофа]].
Если ''φ(e)'' ≠ 0 для любой вершины ''e'' ∈ ''E'', мы говорим о φ как о '''нигде не нулевом''' потоке. Если ''M'' = '''Z''' — группа целых чисел по сложению и ''k'' — положительное число, такое что -''k'' < ''φ(e)'' < ''k'' для любого ребра ''e'', то ''M''-поток φ называют также ''k''-'''потоком'''.

Пусть ''G'' = ''(V,E)'' — ненаправленный граф. Ориентация дуг в ''E'' называется модульным ''k''-'''потоком''', если
: <math>|\delta^+(v)| \equiv |\delta^-(v)| \pmod{k}</math>
для всех вершин ''v'' ∈ ''V''.

== Свойства ==
Изменим нигде не нулевой поток φ на графе ''G'' путём выбора дуги ''e'', изменения направления дуги и замены ''φ(e)'' на ''-φ(e)''. После таких изменений поток останется нигде не нулевым. Далее, если φ был первоначально ''k''-потоком, то и результирующий поток таковым останется. Таким образом, существование нигде не нулевого ''M''-потока или ''k''-потока не зависит от направлений дуг графа. Мы можем сказать, что неориентированный граф ''G'' имеет нигде не нулевой ''M''- поток или ''k''- поток, если какая-либо (а значит и любая) ориентация дуг графа ''G'' имеет такой поток.

Ещё более удивительно то, что если ''M'' является конечной абелевой группой размера ''k'', то число нигде не нулевых ''M''-потоков на некоторых графах не зависит от структуры ''M'', а только от ''k'', размера ''M''. Более того, существование ''M''-потока совпадает с существованием ''k''-потока. Эти два результата доказаны [[Татт, Уильям Томас|Таттом]] в 1953 году<ref>{{статья
 | автор = William Thomas Tutte
 | год = 1953
 | заглавие = A contribution to the theory of chromatic polynomials
 | url = http://cms.math.ca/cjm/a144778#
}}</ref>.

== Двойственность потоков и раскраски ==
Пусть ''G'' = ''(V,E)'' — ориентированный граф [[Мост (теория графов)|без мостов]], нарисованный на плоскости, и предположим, что области (грани) правильно раскрашены в ''k'' цветов {0, 1, 2, .., ''k'' — 1}. Построим отображение φ: ''E(G)'' → {-(''k'' — 1), …, −1, 0, 1, …, ''k'' — 1} по следующему правилу: если дуга ''e'' имеет цвет ''x'' слева и цвет ''y'' справа, положим ''φ(e)'' = ''x'' — ''y''. Легко проверить, что φ — ''k''-поток. Более того, если области выкрашены правильно, φ нигде не нулевой ''k''-поток. Это следует из построения, поскольку если ''G'' и ''G*'' планарные двойственные графы и ''G*'' — ''k''-раскрашиваем, то ''G'' имеет нигде не нулевой ''k''-поток. Татт доказал, что обратное этому утверждению тоже верно. Таким образом, для планарных графов нигде не нулевые потоки являются двойственными раскраске. Поскольку нигде не нулевые потоки имеют смысл для произвольных графов (не только для тех, что можно нарисовать на плоскости), их изучение можно рассматривать как расширение теории раскраски на непланарные графы.

== Теория ==
{{unsolved|математики|Имеет ли произвольный граф без мостов нигде не нулевой 5-поток? Имеет ли произвольный граф без мостов и без графов Петерсена в качестве миноров нигде не нулевой 4-поток?}}
Поскольку никакой граф с [[Глоссарий теории графов|петлёй]] не имеет правильной раскраски, никакой граф, имеющий [[Мост (теория графов)|мосты]], не может иметь нигде не нулевой поток (в любой группе). Легко показать, что любой граф без мостов имеет нигде не нулевой '''Z'''-поток (из [[Теорема Роббинса|теоремы Роббинса]]), но интересный вопрос возникает при попытке найти нигде не нулевой ''k''-поток для малых значений ''k''. Две элегантные теоремы в этом направлении — теорема Джагера о 4-потоке (любой [[Рёберно k-связный граф|рёберно 4-связный]] граф имеет нигде не нулевой 4-поток)<ref>F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. Theory Set. B, 26 (1979), 205—216.</ref> и теорема Сеймура о 6-потоке (любой граф без мостов имеет нигде не нулевой 6-поток)<ref>P. D. Seymour, Nowhere-zero 6-flows, J. Comb. Theory Ser B, 30 (1981), 130—135.</ref>.

[[Татт, Уильям|Татт]] высказал гипотезу, что любой граф без мостов имеет нигде не нулевой 5-поток<ref>[http://garden.irmacs.sfu.ca/?q=op/5_flow_conjecture 5-flow conjecture], Open Problem Garden.</ref> и что любой граф без мостов, не содержащий [[граф Петерсена]] в качестве [[Минор графа|минора]] имеет нигде не нулевой 4-поток<ref>[http://garden.irmacs.sfu.ca/?q=op/4_flow_conjecture 4-flow conjecture], Open Problem Garden.</ref>. Для [[Кубический граф|кубических графов]], не содержащих минор Петерсена, существование 4-потока следует из [[Снарк (теория графов)|теоремы о снарках]], но для произвольных графов гипотеза остаётся открытой.

== См. также ==
* {{не переведено 5|Пространство циклов|Пространство циклов||Cycle space}}

== Примечания ==
{{примечания}}

== Ссылки ==
* {{книга
| автор  = Cun-Quan Zhang
| заглавие = Integer Flows and Cycle Covers of Graphs
| url = http://www.math.wvu.edu/~cqzhang/book.html
| серия = Chapman & Hall/CRC Pure and Applied Mathematics Series
| год  = 1997
| издательство = Marcel Dekker, Inc.
| isbn = 9780824797904
| lccn = 96037152
}}
* {{книга
 | автор = Cun-Quan Zhang
 | isbn = 978-0-5212-8235-2
 | издательство = Cambridge University Press
 | заглавие = Circuit Double Cover of Graphs
 | год = 2012}}
* T.R. Jensen and B. Toft, Graph Coloring Problems, Wiley-Interscience Serires in Discrete Mathematics and Optimization, (1995)

{{rq|checktranslate|tex|style}}<!--«изменим…», «ещё более удивительно…»-->
[[Категория:Теория графов]]