Гипотеза Хивуда
| НЕТ ВОЙНЕ |
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России |
| Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению. |
| meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки. |
| Определение: |
| Хроматическим числом поверхности поверхности или -ым числом Хивуда называется число , равное максимальному хроматическому числу графа, который можно уложить на поверхность -ого рода. |
Теорема о нижней границе хроматического числа поверхности
| Теорема (Теорема Рингеля и Янгса): |
Для любого положительного целого числа хроматическое число поверхности -ого рода . |
| Доказательство: |
|
Воспользуемся формулой Эйлера . Давайте докажем нижнюю границу на . Максимизируем число граней: каждая из них может быть треугольником. Тогда для существует неулучшаемая нижняя граница:
. Рассмотрим полный граф , тогда получаем, что , функция монотонно возрастает при , и для любого наибольшее значение функция достигается при . Поскольку , откуда получаем, что . |
Теорема о верхней границе хроматического числа поверхности
| Теорема (Гипотеза Хивуда): |
Для любого положительного целого числа хроматическое число поверхности -ого рода . |
| Доказательство: |
|
Пусть задан граф с вершина, рёбрами и гранями, также будем считать, что — триангуляция (добавляя таким образом рёбра мы всё ещё получаем граф, который можно уложить на поверхности -ого рода). Обозначим за — среднюю степень вершины графа , тогда должно быть справедливым следующее равенство:
Воспользуемся формулой Эйлера , откуда и и подставляя в первое равенство получаем
Поскольку , то
Найдём единственный положительный корень неравенства
Обозначим за . Если , то тогда граф очевидно можно раскрасить в цветов и неравенство верное. Допустим, что , тогда Значит в такое графе существует хотя бы одна вершина степени не больше , стянем её с любой соседней и получим новый граф с вершинами. Если , то граф можно раскрасить в цветов, значит и сам граф можно также раскрасить в цветов, если , то опять найдём вершину степени и снова стянем её и будем продолжать так до тех пор, пока не получим желаемый граф. |
Из всего выше сказанного получаем, что в точности равно .
Проблема четырёх красок
Заметим, что теорема Хивуда не работает при , поэтому проблема четырёх красок не может быть доказана с помощью этой теоремы, однако при подстановке получаем .
См. также
Источники информации
- Wikipedia — Heawood conjecture
- Последовательность чисел Хивуда
- Ф.Харари «Теория графов» — М.: Мир, 1973 г. — стр. 162 - 164
