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

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

Определения

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

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

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

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

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

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

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

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

Позволять быть числом M-токи на грамм. Это удовлетворяет формула удаления-сокращения:[1]

Комбинируя это с индукцией, мы можем показать является многочленом от куда это порядок группы M. Мы называем то полином потока из грамм и абелева группа M.

Из вышесказанного следует, что две группы равного порядка имеют равное количество потоков NZ. Порядок - единственный параметр группы, который имеет значение, а не структура M. Особенно если

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

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

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

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

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

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

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

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

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

  • Позволять функция раскраски лиц со значениями в M.
  • Определять куда р1 лицо слева от е и р2 находится справа.
  • Для каждого M-циркуляция есть функция раскраски c такой, что (доказано по индукции).
  • c это |E(грамм) | -раскраска лица тогда и только тогда, когда Новая Зеландия M-поток (простой).

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

Приложения

  • грамм является 2-гранным раскрашиваемым тогда и только тогда, когда каждая вершина имеет четную степень (рассмотрим NZ 2-потоки).[1]
  • Позволять быть Группа Клейн-4. Затем кубический граф имеет K-поток тогда и только тогда, когда он равен 3-крашеный. Как следствие, кубический граф, раскрашиваемый по 3 ребрам, раскрашивается по 4 граням.[1]
  • Граф является 4-гранным раскрашиваемым тогда и только тогда, когда он допускает NZ 4-поток (см. Теорема четырех цветов ). В Граф Петерсена не имеет NZ 4-потока, и это привело к гипотезе о 4-потоках (см. ниже).
  • Если грамм это триангуляция, тогда грамм является 3- (вершиной) раскрашиваемым тогда и только тогда, когда каждая вершина имеет четную степень. Согласно первому пункту дуальный граф грамм* двухцветный и, следовательно, двудольный и плоская кубическая. Так грамм* имеет NZ 3-поточный и, следовательно, 3-сторонний окрашиваемый, что делает грамм 3-вершинная раскрашиваемая.[1]
  • Так же, как нет графика с петля ребро имеет правильную раскраску вершин, нет графа с мост может иметь NZ M-поток для любой группы M. И наоборот, каждые безмостовой граф имеет новозеландский -поток (форма Теорема Роббинса ).[3]

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

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Каждый ли граф без мостов имеет нигде нулевой 5-поток? Каждый ли граф без мостов, в котором нет графа Петерсена в качестве второстепенного, имеет нигде нулевой 4-поток?
(больше нерешенных задач по математике)

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

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

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

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

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

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

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

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

  1. ^ а б c d е ж грамм час я j Дистель, Рейнхард, 1959 - Верфассер. (30 июня 2017 г.). Теория графов. ISBN  9783662536216. OCLC  1048203362.CS1 maint: несколько имен: список авторов (связь)
  2. ^ Тутте, Уильям Томас (1953). «Вклад в теорию хроматических многочленов». Цитировать журнал требует | журнал = (помощь)
  3. ^ Для более сильного результата по перечислению -потоков с ограничением максимального количества потока на ребро, снова используя теорему Роббинса о полностью циклических ориентациях, см. теорему 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], Открытый Проблемный сад.

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