Редактирование: Верхние и нижние оценки хроматического числа
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 37: | Строка 37: | ||
{{Лемма | {{Лемма | ||
|about = верхняя оценка | |about = верхняя оценка | ||
− | |statement= Пусть <tex>G(V,E)</tex> {{---}} произвольный связный неориентированный граф с <tex>m</tex> ребрами.Тогда, <tex>\chi(G) \leqslant \ | + | |statement= Пусть <tex>G(V,E)</tex> {{---}} произвольный связный неориентированный граф с <tex>m</tex> ребрами.Тогда, <tex dpi=140>\chi(G) \leqslant \frac{1}{2} +\sqrt{2m + \frac{1}{4}}</tex>. |
|proof= | |proof= | ||
Пусть, <tex>V_1,V_2...V_\chi</tex> множеств вершин окрашенных в соответствующие цвета при правильно покраски графа <tex>G</tex>. Заметим, что между любыми двумя различными множествами существует хотя бы одно ребро (в противном случаи эти множества можно было бы покрасить в один цвет). | Пусть, <tex>V_1,V_2...V_\chi</tex> множеств вершин окрашенных в соответствующие цвета при правильно покраски графа <tex>G</tex>. Заметим, что между любыми двумя различными множествами существует хотя бы одно ребро (в противном случаи эти множества можно было бы покрасить в один цвет). | ||
− | Тогда, <tex>\ | + | Тогда, <tex dpi=140>\frac{1}{2}\chi(\chi-1) \leqslant m \Rightarrow (\chi - \frac{1}{2})^2 \leqslant 2m + \frac{1}{4} \Rightarrow \chi(G) \leqslant \frac{1}{2} +\sqrt{2m + \frac{1}{4}} </tex>. |
}} | }} | ||
Строка 46: | Строка 46: | ||
{{Лемма | {{Лемма | ||
|about = нижняя оценка Геллера | |about = нижняя оценка Геллера | ||
− | |statement= Пусть <tex>G(V,E)</tex> {{---}} произвольный связный неориентированный граф с <tex>n</tex> вершинами и <tex>m</tex> ребрами. Тогда, <tex>\ | + | |statement= Пусть <tex>G(V,E)</tex> {{---}} произвольный связный неориентированный граф с <tex>n</tex> вершинами и <tex>m</tex> ребрами. Тогда, <tex dpi=140>\frac{n^2}{n^2 - 2m} \leqslant \chi(G) </tex>. |
|proof= | |proof= | ||
Пусть, <tex>V_1,V_2...V_\chi</tex> множеств вершин окрашенных в соответствующие цвета при правильно покраски графа <tex>G</tex>. | Пусть, <tex>V_1,V_2...V_\chi</tex> множеств вершин окрашенных в соответствующие цвета при правильно покраски графа <tex>G</tex>. | ||
− | <tex>m \leqslant \ | + | <tex dpi=140>m \leqslant \frac{1}{2}n(n - 1) - \frac{1}{2}\sum\limits^{\chi}_{i = 1}|V_i|(|V_i| - 1) \Rightarrow \frac{n^2}{n^2 - 2m} \leqslant \frac{n^2}{n^2 -n(n - 1) + \sum\limits^{\chi}_{i = 1}|V_i|(|V_i| - 1)} = \frac{n^2}{n + \sum\limits^{\chi}_{i = 1}|V_i|(|V_i| - 1)} = \frac{n^2}{\sum\limits^{\chi}_{i = 1}|V_i| + \sum\limits^{\chi}_{i = 1}|V_i|(|V_i| - 1)} = \frac{n^2}{\sum\limits^{\chi}_{i = 1}|V_i|^2} = \frac{(\sum\limits^{\chi}_{i = 1}|V_i|)^2}{\sum\limits^{\chi}_{i = 1}|V_i|^2} \leqslant \chi</tex>. |
}} | }} | ||