Ніде не нульовий потік
Ніде́ не нульови́й поті́к у теорії графів — особливий вид мережевого потоку, який пов'язаний (двоїстістю) з розфарбуванням планарних графів.
Нехай G = (V, E) — орієнтований граф і нехай M — абелева група. Відображення φ: E → M називають потоком або M-потоком, якщо для будь-якої вершини v ∈ V, виконується
де δ+(v) позначає множину ребер, що виходять із v, а δ-(v) — множину ребер, що входять у v. Іноді цю умову трактують як правило Кірхгофа. Якщо φ(e) ≠ 0 для будь-якої вершини e ∈ E, ми говоримо про φ як про ніде не нульовий потік. Якщо M = Z — група цілих чисел за додаванням і k — додатне число, таке що -k < φ(e) < k для будь-якого ребра e, то M-потік φ називають також k-потоком.
Нехай G = (V, E) — ненапрямлений граф. Орієнтацію дуг в E називають модульним k-потоком, якщо
для всіх вершин v ∈ V.
Змінимо ніде не нульовий потік φ на графі G, вибравши дугу e, змінивши напрям дуги і замінивши φ(e) на -φ(e). Після таких змін потік залишиться ніде не нульовим. Далі, якщо φ був спочатку k-потоком, то й отриманий потік таким залишиться. Таким чином, існування ніде не нульового M-потоку або k-потоку не залежить від напрямків дуг графа. Ми можемо сказати, що неорієнтований граф G має ніде не нульовий M-потік або k-потік, якщо яка-небудь (а отже й будь-яка) орієнтація дуг графа G має такий потік.
Ще дивніше те, що якщо M є скінченною абелевою групою розміру k, то число ніде не нульових M-потоків на деяких графах не залежить від структури M, а тільки від k, розміру M. Більш того, існування M-потоку збігається з існуванням k-потоку. Ці два результати довів Татт 1953 року[1].
Нехай G = (V, E) — орієнтований граф без мостів, намальований на площині, і припустимо, що області (грані) правильно розфарбовані в k кольорів {0, 1, 2, .., k — 1}. Побудуємо відображення φ: E(G) → {-(k — 1), …, −1, 0, 1, …, k — 1} за таким правилом: якщо дуга e має колір x ліворуч і колір y праворуч, покладемо φ(e) = x — y. Легко перевірити, що φ — k-потік. Більш того, якщо області пофарбовано правильно, φ ніде не нульовий k-потік. Це випливає з побудови, оскільки якщо G і G* планарні двоїсті графи і G* — k-розфарбовуваний, то G має ніде не нульовий k-потік. Татт довів, що зворотне цьому твердженню теж істинне. Таким чином, для планарних графів ніде не нульові потоки є двоїстими. Оскільки ніде не нульові потоки мають сенс для довільних графів (не тільки для тих, що можна намалювати на площині), їх вивчення можна розглядати як розширення теорії розфарбовування на непланарні графи.
![]() |
Нерозв'язана проблема математики: Чи має довільний граф без мостів ніде не нульовий 5-потік? Чи має довільний граф без мостів і без графів Петерсена як мінорів ніде не нульовий 4-потік? (більше нерозв'язаних проблем математики)
|
Оскільки ніякої граф з петлею не має правильного розфарбування, ніякої граф, що має мости, не може мати ніде не нульового потоку (в будь-якій групі). Легко показати, що будь-який граф без мостів має ніде не нульовий Z-потік (з теореми Роббінса), але цікаве питання виникає за спроби знайти ніде не нульовий k-потік для малих значень k. Дві елегантні теореми в цьому напрямку — теорема Джагера про 4-потік (будь-який реберно 4-зв'язний граф має ніде не нульовий 4-потік)[2] і теорема Сеймура про 6-потік (будь-який граф без мостів має ніде не нульовий 6-потік)[3].
Татт висловив гіпотезу, що будь-який граф без мостів має ніде не нульовий 5-потік[4] і що будь-який граф без мостів, що не містить графа Петерсена як мінора має ніде не нульовий 4-потік[5]. Для кубічних графів, що не містять мінора Петерсена, існування 4-потоку випливає з теореми про снарки, але для довільних графів гіпотеза залишається відкритою.
- ↑ William Thomas Tutte. A contribution to the theory of chromatic polynomials. — 1953. — 28 червня.
- ↑ F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. Theory Set. B, 26 (1979), 205—216.
- ↑ P. D. Seymour, Nowhere-zero 6-flows, J. Comb. Theory Ser B, 30 (1981), 130—135.
- ↑ 5-flow conjecture, Open Problem Garden.
- ↑ 4-flow conjecture, Open Problem Garden.
- Cun-Quan Zhang. Integer Flows and Cycle Covers of Graphs. — Marcel Dekker, Inc, 1997. — (Chapman & Hall/CRC Pure and Applied Mathematics Series) — ISBN 9780824797904.
- Cun-Quan Zhang. Circuit Double Cover of Graphs. — Cambridge University Press, 2012. — ISBN 978-0-5212-8235-2.
- T.R. Jensen and B. Toft, Graph Coloring Problems, Wiley-Interscience Serires in Discrete Mathematics and Optimization, (1995)