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

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

Определения

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

\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 < | φ ( е )| < k , то φ является k -потоком. ^[1]

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

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

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

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

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

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

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

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

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

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

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

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

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

Двойственность потоковой окраски

Безмостовые планарные графы

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

\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 -поток. Используя индукцию по | Е ( Г ) | Тутте доказал, что обратное тоже верно. Кратко это можно выразить так: ^[1]

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

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

(еще нерешенные задачи по математике)

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

Теорема Джегера о 4-потоках. Любой 4- реберно-связный граф имеет 4-поток. ^[4]

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

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

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

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

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

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

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

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Дистель, Рейнхард (30 июня 2017 г.). Теория графов . ISBN 9783662536216 . OCLC 1048203362 .
^ Тутте, WT (1954). «Вклад в теорию хроматических полиномов». Канадский математический журнал . 6 : 80–91. дои : 10.4153/CJM-1954-010-9 .
^ Для более сильного результата по перечислению $\mathbb {Z}$ -потоки с ограничением максимального объема потока на ребро, снова используя теорему Роббинса о полностью циклических ориентациях, см. Теорему 2 из Кохол, Мартин (2002), «Полиномы, связанные с потоками нигде ненулевыми», Журнал комбинаторной теории , серия B, 84 (2): 260–269, doi : 10.1006/jctb.2001.2081 , MR 1889258
^ Ф. Джегер, Потоки и обобщенные теоремы о раскраске графов, J. Comb. Теоретический набор. Б, 26 (1979), 205–216.
^ П.Д. Сеймур, 6-потоки «Нигде-ноль», Дж. Комб. Теория, серия Б, 30 (1981), 130–135.
^ [1] , Открытый проблемный сад.
^ [2] , Открытый проблемный сад.
^ [3] , Открытый проблемный сад.

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

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

[:0-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж Дистель, Рейнхард (30 июня 2017 г.). Теория графов . ISBN 9783662536216 . OCLC 1048203362 .

[2] Тутте, WT (1954). «Вклад в теорию хроматических полиномов». Канадский математический журнал . 6 : 80–91. дои : 10.4153/CJM-1954-010-9 .

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

[4] Ф. Джегер, Потоки и обобщенные теоремы о раскраске графов, J. Comb. Теоретический набор. Б, 26 (1979), 205–216.

[5] П.Д. Сеймур, 6-потоки «Нигде-ноль», Дж. Комб. Теория, серия Б, 30 (1981), 130–135.

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]