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

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

Определения

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

${\displaystyle \sum _{e\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)\to \{-(k-1),\ldots ,-1,0,1,\ldots ,k-1\}}$

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

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

${\displaystyle \chi (G^{*})=\phi (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 K=\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]

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

• Алгебраическая теория потока
• Цикл пространство
• Гипотеза о двойном покрытии цикла
• Теорема четырех цветов
• Раскраска графика
• Краска окраски
• Полином Тутте

Рекомендации

1. Дистель, Рейнхард, 1959 - Верфассер. (30 июня 2017 г.). Теория графов. ISBN  9783662536216. OCLC  1048203362.
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], Открытый Проблемный сад.

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

• Чжан, Цунь-Цюань (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.