В теорії графів, теорема Візінга (названа на честь (Вадіма Візінга), який оприлюднив її в 1964) стверджує, що ребра кожного неорієнтованого графу можна пофарбувати, із використанням числа кольорів не більшого ніж найбільший степінь Δ графу плюс 1.
Завжди необхідно не менше ніж Δ кольорів, отже неорієнтовані графи можна розділити на два класи: «клас один», для якого достатньо Δ кольорів, і «клас два», для якого необхідно Δ + 1.
Приклади
коли Δ = 1, граф G не має двох суміжних ребер і його хроматичне число — один. Тобто всі графи з Δ(G) = 1 належать до першого класу.
Коли Δ = 2, граф G повинен бути диз'юнктним об'єднанням шляхів і циклів. Якщо всі цикли парні, тоді їх можна розфарбувати двома кольорами, чергуючи їх. Якщо ж існує хоч один непарний цикл, тоді розфарбування 2 кольорами неможливе. Тобто граф з Δ = 2 належить до першого класу тоді і тільки тоді, якщо двочастковий.
Мультиграфи зазвичай не коряться теоремі Візінга. Наприклад, мультиграф утворений подвоєнням кожного ребра у трикутнику має максимальну валентність вершини чотири, але його розфарбування вимагає шість кольорів.
Посилання
- Доведення теореми Візінга на PlanetMath. (англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет