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

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

редагувань