Теорема Візінга: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Lidaz (обговорення | внесок) Немає опису редагування |
Немає опису редагування |
||
| Рядок 1: | Рядок 1: | ||
В [[теорія графів|теорії графів]], '''теорема Візінга''' (названа на честь [[Вадим Георгійович Візінг|Вадіма Візінга]], який оприлюднив її в [[1964]]) стверджує, що ребра кожного [[неорієнтований граф|неорієнтованого графу]] можна [[Хроматичний індекс|пофарбувати]], із використанням числа кольорів не більшого ніж |
В [[теорія графів|теорії графів]], '''теорема Візінга''' (названа на честь [[Вадим Георгійович Візінг|Вадіма Візінга]], який оприлюднив її в [[1964]]) стверджує, що ребра кожного [[неорієнтований граф|неорієнтованого графу]] можна [[Хроматичний індекс|пофарбувати]], із використанням числа кольорів не більшого ніж найбільший [[Степінь вершини (теорія графів)|степінь]] {{math|Δ}} графу плюс 1. |
||
Завжди необхідно не менше ніж {{math|Δ}} кольорів, отже неорієнтовані графи можна розділити на два класи: «клас один», для якого достатньо {{math|Δ}} кольорів, і «клас два», для якого необхідно {{math|Δ + 1}}. |
Завжди необхідно не менше ніж {{math|Δ}} кольорів, отже неорієнтовані графи можна розділити на два класи: «клас один», для якого достатньо {{math|Δ}} кольорів, і «клас два», для якого необхідно {{math|Δ + 1}}. |
||
Версія за 15:51, 24 січня 2016
В теорії графів, теорема Візінга (названа на честь Вадіма Візінга, який оприлюднив її в 1964) стверджує, що ребра кожного неорієнтованого графу можна пофарбувати, із використанням числа кольорів не більшого ніж найбільший степінь Δ графу плюс 1.
Завжди необхідно не менше ніж Δ кольорів, отже неорієнтовані графи можна розділити на два класи: «клас один», для якого достатньо Δ кольорів, і «клас два», для якого необхідно Δ + 1.
Приклади
коли Δ = 1, граф G не має двох суміжних ребер і його хроматичне число — один. Тобто всі графи з Δ(G) = 1 належать до першого класу.
Коли Δ = 2, граф G повинен бути диз'юнктним об'єднанням шляхів і циклів. Якщо всі цикли парні, тоді їх можна розфарбувати двома кольорами, чергуючи їх. Якщо ж існує хоч один непарний цикл, тоді розфарбування 2 кольорами неможливе. Тобто граф з Δ = 2 належить до першого класу тоді і тільки тоді, якщо дводольний.
Мультиграфи зазвичай не коряться теоремі Візінга. Наприклад, мультиграф утворений подвоєнням кожного ребра у трикутнику має максимальну валентність вершини чотири, але його розфарбування вимагає шість кольорів.
Посилання
- Доведення теореми Візінга на PlanetMath. (англ.)