Теорема Визинга: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Теорема Визинга''' (''В.Г.Визинг, 1964'') ''Каков бы ни был граф <math>G</math>, его хром...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Теорема Визинга''' (''В.Г.Визинг, 1964'') | '''Теорема Визинга''' (''[[В.Г.Визинг, 1964]]'') | ||
''Каков бы ни был граф <math>G</math>, его хроматический индекс <math>\chi'(G)</math> удовлетворяет неравенствам'' | ''Каков бы ни был [[граф]] <math>G</math>, его [[хроматический индекс]] <math>\chi'(G)</math> удовлетворяет неравенствам'' | ||
<math>\Delta(G) \leq \chi'(G) \leq \Delta(G) + 1.</math> | <math>\Delta(G) \leq \chi'(G) \leq \Delta(G) + 1.</math> | ||
Версия от 12:37, 4 февраля 2010
Теорема Визинга (В.Г.Визинг, 1964) Каков бы ни был граф [math]\displaystyle{ G }[/math], его хроматический индекс [math]\displaystyle{ \chi'(G) }[/math] удовлетворяет неравенствам
[math]\displaystyle{ \Delta(G) \leq \chi'(G) \leq \Delta(G) + 1. }[/math]
Литература
[Лекции],
[Зыков/69],
[Berge],
[Bondy-Murty]