Теорема Візінга: відмінності між версіями

нема опису редагування
Немає опису редагування
Немає опису редагування
В [[теорія графів|теорії графів]], '''теорема Візінга''' (названа на честь [[Вадим Георгійович Візінг|Вадіма Візінга]], який оприлюднив її в [[1964]]) стверджує, що ребра кожного [[неорієнтований граф|неорієнтованого графу]] можна [[Хроматичний індекс|пофарбувати]], із використанням числа кольорів не більшого ніж найбільшанайбільший [[ступіньСтепінь вершини (теорія графів)|ступіньстепінь]] {{math|Δ}} графу плюс 1.
 
Завжди необхідно не менше ніж {{math|Δ}} кольорів, отже неорієнтовані графи можна розділити на два класи: «клас один», для якого достатньо {{math|Δ}} кольорів, і «клас два», для якого необхідно {{math|Δ + 1}}.
11 334

редагування