Теорема Візінга

Версія від 14:02, 31 липня 2013, створена Igor Yalovecky (обговорення | внесок) (Створена сторінка: В теорії графів, '''теорема Візінга''' (названа на честь Вадим Георгійов...)
(різн.) ← Попередня версія | Поточна версія (різн.) | Новіша версія → (різн.)

В теорії графів, теорема Візінга (названа на честь Вадіма Візінга, який оприлюднив її 1964) стверджує, що ребра кожного неорієнтованого неорієнтованого графу можна пофарбувати, із використанням не більшого числа кольорів ніж найбільший ступінь Δ графу.

Завжди необхідно не менше ніж Δ кольорів, отже неорієнтовані графи можна розділити на два класи: «клас один», для якого достатньо Δ кольорів, і «клас два», для якого необхідно Δ + 1.

Посилання