Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Ніде́ не нульови́й поті́к у теорії графів — особливий вид мережевого потоку, який пов'язаний (двоїстістю) з розфарбуванням планарних графів.
Визначення
Нехай 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 року.
Двоїстість потоків і розфарбування
Нехай 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-потік) і теорема Сеймура про 6-потік (будь-який граф без мостів має ніде не нульовий 6-потік).
Татт висловив гіпотезу, що будь-який граф без мостів має ніде не нульовий 5-потік і що будь-який граф без мостів, що не містить графа Петерсена як мінора має ніде не нульовий 4-потік. Для кубічних графів, що не містять мінора Петерсена, існування 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) — .
- Cun-Quan Zhang. Circuit Double Cover of Graphs. — Cambridge University Press, 2012. — .
- T.R. Jensen and B. Toft, Graph Coloring Problems, Wiley-Interscience Serires in Discrete Mathematics and Optimization, (1995)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Nide ne nulovi j poti k u teoriyi grafiv osoblivij vid merezhevogo potoku yakij pov yazanij dvoyististyu z rozfarbuvannyam planarnih grafiv ViznachennyaNehaj G V E oriyentovanij graf i nehaj M abeleva grupa Vidobrazhennya f E M nazivayut potokom abo M potokom yaksho dlya bud yakoyi vershini v V vikonuyetsya e d v ϕ e e d v ϕ e displaystyle sum e in delta v phi e sum e in delta v phi e de d v poznachaye mnozhinu reber sho vihodyat iz v a d v mnozhinu reber sho vhodyat u v Inodi cyu umovu traktuyut yak pravilo Kirhgofa Yaksho f e 0 dlya bud yakoyi vershini e E mi govorimo pro f yak pro nide ne nulovij potik Yaksho M Z grupa cilih chisel za dodavannyam i k dodatne chislo take sho k lt f e lt k dlya bud yakogo rebra e to M potik f nazivayut takozh k potokom Nehaj G V E nenapryamlenij graf Oriyentaciyu dug v E nazivayut modulnim k potokom yaksho d v d v mod k displaystyle delta v equiv delta v pmod k dlya vsih vershin v V VlastivostiZminimo nide ne nulovij potik f na grafi G vibravshi dugu e zminivshi napryam dugi i zaminivshi f e na f e Pislya takih zmin potik zalishitsya nide ne nulovim Dali yaksho f buv spochatku k potokom to j otrimanij potik takim zalishitsya Takim chinom isnuvannya nide ne nulovogo M potoku abo k potoku ne zalezhit vid napryamkiv dug grafa Mi mozhemo skazati sho neoriyentovanij graf G maye nide ne nulovij M potik abo k potik yaksho yaka nebud a otzhe j bud yaka oriyentaciya dug grafa G maye takij potik She divnishe te sho yaksho M ye skinchennoyu abelevoyu grupoyu rozmiru k to chislo nide ne nulovih M potokiv na deyakih grafah ne zalezhit vid strukturi M a tilki vid k rozmiru M Bilsh togo isnuvannya M potoku zbigayetsya z isnuvannyam k potoku Ci dva rezultati doviv Tatt 1953 roku Dvoyistist potokiv i rozfarbuvannyaDiv takozh Kolove rozfarbovuvannya Nehaj G V E oriyentovanij graf bez mostiv namalovanij na ploshini i pripustimo sho oblasti grani pravilno rozfarbovani v k koloriv 0 1 2 k 1 Pobuduyemo vidobrazhennya f E G k 1 1 0 1 k 1 za takim pravilom yaksho duga e maye kolir x livoruch i kolir y pravoruch poklademo f e x y Legko pereviriti sho f k potik Bilsh togo yaksho oblasti pofarbovano pravilno f nide ne nulovij k potik Ce viplivaye z pobudovi oskilki yaksho G i G planarni dvoyisti grafi i G k rozfarbovuvanij to G maye nide ne nulovij k potik Tatt doviv sho zvorotne comu tverdzhennyu tezh istinne Takim chinom dlya planarnih grafiv nide ne nulovi potoki ye dvoyistimi Oskilki nide ne nulovi potoki mayut sens dlya dovilnih grafiv ne tilki dlya tih sho mozhna namalyuvati na ploshini yih vivchennya mozhna rozglyadati yak rozshirennya teoriyi rozfarbovuvannya na neplanarni grafi TeoriyaNerozv yazana problema matematiki Chi maye dovilnij graf bez mostiv nide ne nulovij 5 potik Chi maye dovilnij graf bez mostiv i bez grafiv Petersena yak minoriv nide ne nulovij 4 potik bilshe nerozv yazanih problem matematiki Oskilki niyakoyi graf z petleyu ne maye pravilnogo rozfarbuvannya niyakoyi graf sho maye mosti ne mozhe mati nide ne nulovogo potoku v bud yakij grupi Legko pokazati sho bud yakij graf bez mostiv maye nide ne nulovij Z potik z teoremi Robbinsa ale cikave pitannya vinikaye za sprobi znajti nide ne nulovij k potik dlya malih znachen k Dvi elegantni teoremi v comu napryamku teorema Dzhagera pro 4 potik bud yakij reberno 4 zv yaznij graf maye nide ne nulovij 4 potik i teorema Sejmura pro 6 potik bud yakij graf bez mostiv maye nide ne nulovij 6 potik Tatt visloviv gipotezu sho bud yakij graf bez mostiv maye nide ne nulovij 5 potik i sho bud yakij graf bez mostiv sho ne mistit grafa Petersena yak minora maye nide ne nulovij 4 potik Dlya kubichnih grafiv sho ne mistyat minora Petersena isnuvannya 4 potoku viplivaye z teoremi pro snarki ale dlya dovilnih grafiv gipoteza zalishayetsya vidkritoyu Div takozhProstir ciklivPrimitkiWilliam Thomas Tutte A contribution to the theory of chromatic polynomials 1953 28 chervnya 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 PosilannyaCun Quan Zhang Integer Flows and Cycle Covers of Graphs Marcel Dekker Inc 1997 Chapman amp 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