Ніде не нульовий потік

Ніде́ не нульови́й поті́к у теорії графів — особливий вид мережевого потоку, який пов'язаний (двоїстістю) з розфарбуванням планарних графів.

Визначення

Нехай 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 = Z — група цілих чисел за додаванням і k — додатне число, таке що -k < φ(e) < k для будь-якого ребра e, то M-потік φ називають також k-потоком.

Нехай G = (V, E) — ненапрямлений граф. Орієнтацію дуг в E називають модульним k-потоком, якщо

$|{\delta }^{+}(v)|\equiv |{\delta }^{-}(v)|(\mathrm{mod}k)$

для всіх вершин v ∈ V.

Властивості

Змінимо ніде не нульовий потік φ на графі G, вибравши дугу e, змінивши напрям дуги і замінивши φ(e) на -φ(e). Після таких змін потік залишиться ніде не нульовим. Далі, якщо φ був спочатку k-потоком, то й отриманий потік таким залишиться. Таким чином, існування ніде не нульового M-потоку або k-потоку не залежить від напрямків дуг графа. Ми можемо сказати, що неорієнтований граф G має ніде не нульовий M-потік або k-потік, якщо яка-небудь (а отже й будь-яка) орієнтація дуг графа G має такий потік.

Ще дивніше те, що якщо M є скінченною абелевою групою розміру k, то число ніде не нульових M-потоків на деяких графах не залежить від структури M, а тільки від k, розміру M. Більш того, існування M-потоку збігається з існуванням k-потоку. Ці два результати довів Татт 1953 року.

Двоїстість потоків і розфарбування

Шаблон:Див. також Нехай 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-потік. Татт довів, що зворотне цьому твердженню теж істинне. Таким чином, для планарних графів ніде не нульові потоки є двоїстими. Оскільки ніде не нульові потоки мають сенс для довільних графів (не тільки для тих, що можна намалювати на площині), їх вивчення можна розглядати як розширення теорії розфарбовування на непланарні графи.

Теорія

Шаблон:Нерозв'язаноОскільки ніякої граф з петлею не має правильного розфарбування, ніякої граф, що має мости, не може мати ніде не нульового потоку (в будь-якій групі). Легко показати, що будь-який граф без мостів має ніде не нульовий Z-потік (з теореми Роббінса), але цікаве питання виникає за спроби знайти ніде не нульовий k-потік для малих значень k. Дві елегантні теореми в цьому напрямку — теорема Джагера про 4-потік (будь-який реберно 4-зв'язний граф має ніде не нульовий 4-потік) і теорема Сеймура про 6-потік (будь-який граф без мостів має ніде не нульовий 6-потік).

Татт висловив гіпотезу, що будь-який граф без мостів має ніде не нульовий 5-потік і що будь-який граф без мостів, що не містить графа Петерсена як мінора має ніде не нульовий 4-потік. Для кубічних графів, що не містять мінора Петерсена, існування 4-потоку випливає з теореми про снарки, але для довільних графів гіпотеза залишається відкритою.

Див. також

• Простір циклів

Посилання

• Шаблон:Книга
• Шаблон:Книга
• T.R. Jensen and B. Toft, Graph Coloring Problems, Wiley-Interscience Serires in Discrete Mathematics and Optimization, (1995)