Нигде-нулевой поток

Понятие в теории графов

В теории графов поток нигде не равен нулю или поток NZ — это сетевой поток , который нигде не равен нулю. Он тесно связан (по двойственности) с раскраской планарных графов .

Определения

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

${\displaystyle \sum _{e\in \delta ^{+}(v)}\varphi (e)=\sum _{e\in \delta ^{-}(v)}\varphi (e),}$

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

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

Другие понятия

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

${\displaystyle |\delta ^{+}(v)|\equiv |\delta ^{-}(v)|{\bmod {k}}.}$

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

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

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

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

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

Пусть — число M -потоков на G. Оно удовлетворяет формуле удаления-сжатия : ^[1] ${\displaystyle N_{M}(G)}$

${\displaystyle N_{M}(G)=N_{M}(G/e)-N_{M}(G\setminus e).}$

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

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

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

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

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

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

${\displaystyle \phi :E(G)\to \{-(k-1),\ldots ,-1,0,1,\ldots ,k-1\}}$

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

Итак, если G и G* — планарные двойственные графы , а G* является k -раскрашиваемым (существует раскраска граней G ), то G имеет NZ k -поток. Используя индукцию по | E ( G )|, Тутт доказал, что обратное также верно. Это можно выразить кратко как: ^[1]

${\displaystyle \chi (G^{*})=\phi (G),}$

где правая часть — это число потока , наименьшее k, для которого G допускает k -поток.

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

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

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

• Определим , где r ₁ — грань слева от e , а r ₂ — справа. ${\displaystyle \phi _{c}(e)=c(r_{1})-c(r_{2})}$

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

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

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

Приложения

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

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

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

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

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

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

Нерешенная задача по математике :

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

(еще нерешенные проблемы по математике)

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

Теорема Йегера о 4-потоке. Каждый 4- рёберно-связный граф имеет 4-поток. ^[4]

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

Гипотезы 3-потока, 4-потока и 5-потока

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

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

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

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

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

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

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

Ссылки

1. Дистель, Рейнхард (30 июня 2017 г.). Теория графов . Springer. ISBN 9783662536216. OCLC  1048203362.
2. Tutte, WT (1954). «Вклад в теорию хроматических многочленов». Canadian Journal of Mathematics . 6 : 80–91. doi :10.4153/CJM-1954-010-9.
3. Более сильный результат по перечислению -потоков с ограничением на максимальный объем потока на ребро, снова используя теорему Роббинса о полностью циклических ориентациях, см. теорему 2 из Kochol, Martin (2002), "Polynomials associated with nowhere-zero flows", Journal of Combinatori Theory , Series B, 84 (2): 260–269, doi : 10.1006/jctb.2001.2081 , MR  1889258 ${\displaystyle \mathbb {Z} }$
4. Ф. Йегер, Потоки и обобщенные теоремы о раскраске в графах, J. Comb. Theory Set. B, 26 (1979), 205–216.
5. PD Seymour, Nowhere-zero 6-flows, J. Comb. Theory Ser B, 30 (1981), 130–135.
6. [1], Открытый проблемный сад.
7. [2], Открытый проблемный сад.
8. [3], Открытый проблемный сад.

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

• Чжан, Цунь-Цюань (1997). Целочисленные потоки и циклические покрытия графов . Серия Chapman & Hall/CRC Pure and Applied Mathematics. Marcel Dekker, Inc. ISBN 9780824797904. LCCN  96037152.
• Чжан, Цунь-Цюань (2012). Двойная обложка Circuit of Graphs . Cambridge University Press. ISBN 978-0-5212-8235-2.
• Jensen, TR; Toft, B. (1995). "13 ориентаций и потоков". Проблемы раскраски графов . Wiley-Interscience Serires in Discrete Mathematics and Optimization. стр. 209–219. ISBN 9780471028659.
• Якобсен, Йеспер Ликке; Салас, Хесус (2013). «Является ли гипотеза о пяти потоках почти ложной?». Журнал комбинаторной теории . Серия B. 103 (4): 532–565. arXiv : 1009.4062 . doi :10.1016/j.jctb.2013.06.001. MR  3071381. S2CID  41483928.