Нигде-нулевой поток - Википедия - Nowhere-zero flow

В теория графов, а нигде-нулевой поток или же Поток Новой Зеландии это сетевой поток что нигде ноль. Это тесно связано (двойственностью) с раскраска планарные графы.

Определения

Позволять грамм = (V,E) быть диграф и разреши M быть абелева группа. Карта φ: E → M является M-циркуляция если для каждого вершина v ∈ V

{ displaystyle sum _ {е in delta ^ {+} (v)} phi (e) = sum _ {e in delta ^ {-} (v)} phi (e),}

куда δ⁺(v) обозначает множество ребер из v и δ⁻(v) обозначает множество ребер в v. Иногда это состояние называют Закон Кирхгофа.

Если φ(е) ≠ 0 для каждого е ∈ E, мы называем φ а нигде-нулевой расход, ан M-поток, или НЗ-поток. Если k целое число и 0 < |φ(е)| < k тогда φ это k-поток.^[1]

Прочие понятия

Позволять грамм = (V,E) быть неориентированный граф. Ориентация E это модульный k-поток если для каждой вершиныv ∈ V у нас есть:

{ displaystyle | delta ^ {+} (v) | Equiv | delta ^ {-} (v) | { bmod {k}}.}

Характеристики

Набор M-потоки не обязательно образуют группу, поскольку сумма двух потоков на одном ребре может составлять 0.

(Тутт 1950) График грамм имеет M-поток тогда и только тогда, когда он имеет |M| -поток. Как следствие, ${ displaystyle mathbb {Z} _ {k}}$ поток существует тогда и только тогда, когда k-поток существует.^[1] Как следствие грамм признает k-поток, то он допускает час-поток где ${ displaystyle h geq k}$ .

Независимость от ориентации. Изменить нигде-нулевой поток φ на графике грамм выбрав край е, перевернув его, а затем заменив φ(е) с -φ(е). После этой настройки φ по-прежнему нигде-нулевой поток. Кроме того, если φ изначально был k-поток, то полученный φ также k-поток. Таким образом, существование нигде-нуля M-поток или нигде-ноль k-поток не зависит от ориентации графа. Таким образом, неориентированный граф грамм говорят, что нигде-ноль M-поток или никуда-ноль k-потока, если некоторая (а значит, любая) ориентация грамм имеет такой поток.

Полином потока

Позволять ${ Displaystyle N_ {M} (G)}$ быть числом M-токи на грамм. Это удовлетворяет формула удаления-сокращения:^[1]

{ Displaystyle N_ {M} (G) = N_ {M} (G / e) -N_ {M} (G setminus e).}

Комбинируя это с индукцией, мы можем показать ${ Displaystyle N_ {M} (G)}$ является многочленом от ${ displaystyle | M | -1}$ куда ${ displaystyle | M |}$ это порядок группы M. Мы называем ${ Displaystyle N_ {M} (G)}$ то полином потока из грамм и абелева группа M.

Из вышесказанного следует, что две группы равного порядка имеют равное количество потоков NZ. Порядок - единственный параметр группы, который имеет значение, а не структура M. Особенно ${ Displaystyle N_ {M_ {1}} (G) = N_ {M_ {2}} (G)}$ если ${ displaystyle | M_ {1} | = | M_ {2} |.}$

Приведенные выше результаты были подтверждены Тутте в 1953 году, когда он изучал Полином Тутте, обобщение полинома потока.^[2]

Раскрашивающая двойственность потока

Планарные графы без мостов

Есть двойственность между k-лицо раскраски и k-потоки для без моста планарные графы. Чтобы увидеть это, позвольте грамм - ориентированный планарный граф без мостов с собственным kраскраска лица красками ${ Displaystyle {0,1, ldots, k-1 }.}$ Построить карту

{ Displaystyle phi: E (G) к {- (k-1), ldots, -1,0,1, ldots, k-1 }}

по следующему правилу: если край е имеет цветное лицо Икс слева и лицо цвета у вправо, тогда пусть φ(е) = Икс – у. потом φ является (NZ) k-поток с Икс и у должны быть разных цветов.

Так что если грамм и ГРАММ* плоские двойственные графы и ГРАММ* является k-окрашиваемый (есть раскраска лиц грамм), тогда грамм имеет новозеландский k-поток. Индукцией по |E(грамм) | Тутте доказал, что верно и обратное. Кратко это можно выразить так:^[1]

{ Displaystyle чи (G ^ {*}) = фи (G),}

где RHS - это номер потока, наименьший k для которого грамм позволяет k-поток.

Общие графики

Двойственность верна для общего M-потоки:

Позволять ${ displaystyle c}$ функция раскраски лиц со значениями в M.

Определять ${ displaystyle phi _ {c} (e) = c (r_ {1}) - c (r_ {2})}$ куда р₁ лицо слева от е и р₂ находится справа.

Для каждого M-циркуляция ${ displaystyle phi}$ есть функция раскраски c такой, что ${ displaystyle phi = phi _ {c}}$ (доказано по индукции).

c это |E(грамм) | -раскраска лица тогда и только тогда, когда ${ displaystyle phi _ {c}}$ Новая Зеландия M-поток (простой).

Двойственность следует из объединения двух последних пунктов. Мы можем специализироваться на ${ Displaystyle M = mathbb {Z} _ {k}}$ чтобы получить аналогичные результаты для k-потоки, рассмотренные выше. Учитывая эту двойственность между NZ-потоками и раскрасками, и поскольку мы можем определить NZ-потоки для произвольных графов (не только планарных), мы можем использовать это для расширения раскраски граней на неплоские графы.^[1]

Приложения

грамм является 2-гранным раскрашиваемым тогда и только тогда, когда каждая вершина имеет четную степень (рассмотрим NZ 2-потоки).^[1]

Позволять ${ Displaystyle К = mathbb {Z} _ {2} times mathbb {Z} _ {2}}$ быть Группа Клейн-4. Затем кубический граф имеет K-поток тогда и только тогда, когда он равен 3-крашеный. Как следствие, кубический граф, раскрашиваемый по 3 ребрам, раскрашивается по 4 граням.^[1]

Граф является 4-гранным раскрашиваемым тогда и только тогда, когда он допускает NZ 4-поток (см. Теорема четырех цветов ). В Граф Петерсена не имеет NZ 4-потока, и это привело к гипотезе о 4-потоках (см. ниже).

Если грамм это триангуляция, тогда грамм является 3- (вершиной) раскрашиваемым тогда и только тогда, когда каждая вершина имеет четную степень. Согласно первому пункту дуальный граф грамм* двухцветный и, следовательно, двудольный и плоская кубическая. Так грамм* имеет NZ 3-поточный и, следовательно, 3-сторонний окрашиваемый, что делает грамм 3-вершинная раскрашиваемая.^[1]

Так же, как нет графика с петля ребро имеет правильную раскраску вершин, нет графа с мост может иметь NZ M-поток для любой группы M. И наоборот, каждые безмостовой граф имеет новозеландский ${ Displaystyle mathbb {Z}}$ -поток (форма Теорема Роббинса ).^[3]

Существование k-потоки

Нерешенная проблема в математике:

Каждый ли граф без мостов имеет нигде нулевой 5-поток? Каждый ли граф без мостов, в котором нет графа Петерсена в качестве второстепенного, имеет нигде нулевой 4-поток?

(больше нерешенных задач по математике)

Интересные вопросы возникают при попытке найти нигде-ноль k-потоки для малых значений k. Доказано следующее:

Теорема Йегера о четырех потоках. Каждые 4-реберный Граф имеет 4-поточный.^[4]

Сеймур Теорема о шести потоках. Каждый граф без мостов имеет 6-поток.^[5]

3-х, 4-х и 5-ти потоковые гипотезы

По состоянию на 2019 год следующие вопросы не решены (из-за Тутте ):

Гипотеза о трех потоках. В каждом 4-реберно-связном графе есть 3-поток, нигде не нулевой.^[6]

Гипотеза о 4-потоках. Каждый граф без мостов, не имеющий Граф Петерсена как незначительный есть некуда-ноль 4-х потоков.^[7]

Гипотеза 5-потоков. Каждый граф без мостов имеет 5-поток с нулевым нигде.^[8]

Обратное к гипотезе о 4-потоках неверно, поскольку полный график K₁₁ содержит граф Петерсена и 4-хпоточный.^[1] Для безмостовых кубические графы без минора Петерсена существуют 4-потоки теорема Снарка (Сеймур и др., 1998 г., еще не опубликовано). В теорема четырех цветов эквивалентно утверждению, что никакой снарк не является плоским.^[1]

Смотрите также

дальнейшее чтение

Чжан, Цунь-Цюань (1997). Целочисленные потоки и покрытия циклов графов. Чепмен и Холл / CRC Чистая и прикладная математика. Марсель Деккер, Inc. ISBN 9780824797904. LCCN 96037152.
Чжан, Цунь-Цюань (2012). Схема двойного покрытия графов. Издательство Кембриджского университета. ISBN 978-0-5212-8235-2.
Jensen, T. R .; Тофт, Б. (1995). «13 ориентаций и течений». Проблемы с раскраской графиков. Серия Wiley-Interscience по дискретной математике и оптимизации. стр.209 –219.
Якобсен, Джеспер Ликке; Салас, Хесус (2013). «Гипотеза пяти потоков почти ложна?». Журнал комбинаторной теории. Серия Б. 103 (4): 532–565. arXiv:1009.4062. Дои:10.1016 / j.jctb.2013.06.001. МИСТЕР 3071381.

[:0-1] а ^б ^c ^d ^е ^ж ^грамм ^час ^я ^j Дистель, Рейнхард, 1959 - Верфассер. (30 июня 2017 г.). Теория графов. ISBN 9783662536216. OCLC 1048203362.CS1 maint: несколько имен: список авторов (связь)

[2] Тутте, Уильям Томас (1953). «Вклад в теорию хроматических многочленов». Цитировать журнал требует | журнал = (помощь)

[3] Для более сильного результата по перечислению ${ Displaystyle mathbb {Z}}$ -потоков с ограничением максимального количества потока на ребро, снова используя теорему Роббинса о полностью циклических ориентациях, см. теорему 2 из Кохол, Мартин (2002), "Полиномы, связанные с потоками нигде-нулем", Журнал комбинаторной теории, Серия B, 84 (2): 260–269, Дои:10.1006 / jctb.2001.2081, МИСТЕР 1889258

[4] F. Jaeger, Потоки и обобщенные теоремы о раскраске в графах, J. Comb. Набор теорий. В, 26 (1979), 205–216.

[5] П. Д. Сеймур, 6-потоки в нигде-нуль, J. Comb. Теория Сер. Б., 30 (1981), 130–135.

[6] [1], Открытый Проблемный сад.

[7] [2], Открытый Проблемный сад.

[8] [3], Открытый Проблемный сад.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]