Редактирование: Гипотеза Хивуда

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 4: Строка 4:
 
'''Хроматическим числом поверхности поверхности <tex>S_n</tex>''' или '''<tex>n</tex>-ым числом Хивуда''' называется число <tex>\chi \left( S_n \right)</tex>, равное максимальному хроматическому числу графа, который можно уложить на поверхность <tex>n</tex>-ого рода.
 
'''Хроматическим числом поверхности поверхности <tex>S_n</tex>''' или '''<tex>n</tex>-ым числом Хивуда''' называется число <tex>\chi \left( S_n \right)</tex>, равное максимальному хроматическому числу графа, который можно уложить на поверхность <tex>n</tex>-ого рода.
 
}}
 
}}
 
==Теорема о нижней границе хроматического числа поверхности==
 
  
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=
Теорема Рингеля и Янгса
+
Теорема Хивуда о раскраске карт
 
|statement=
 
|statement=
Для любого положительного целого числа <tex>n</tex> хроматическое число поверхности <tex>n</tex>-ого рода <tex>\chi \left( S_n \right) \geqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>.
+
Для любого положительного целого числа <tex>n</tex> хроматическое число поверхности <tex>n</tex>-ого рода определяется формулой <tex>\chi \left( S_n \right) = \left[ \dfrac{ 7 + \sqrt{1 + 48n} }{ 2 } \right]</tex>
 
|proof=
 
|proof=
  
Воспользуемся формулой Эйлера <tex>V + F - E = 2 - 2n</tex>. Давайте докажем нижнюю границу на <tex>E</tex>. Максимизируем число граней: каждая из них может быть треугольником. Тогда для <tex>E</tex> существует неулучшаемая нижняя граница:
+
Для начала докажем <tex>\chi \left(S_n\right) \leqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>
 
 
<tex>E \geqslant 3 \left( V - 2 + 2n \right)</tex>
 
 
 
<tex>n \geqslant \dfrac{1}{6} E - \dfrac{1}{2} \left( V - 2 \right)</tex>.
 
 
 
Рассмотрим полный граф <tex>K_p</tex>, тогда получаем, что
 
 
 
<tex>\gamma \left( K_p \right) \geqslant \dfrac{1}{6} \dfrac{p (p - 1)}{2} - \dfrac{p - 2}{2}</tex>
 
 
 
<tex>\gamma \left( K_p \right) \geqslant \left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}</tex>, функция монотонно возрастает при <tex>p \geqslant 4</tex>, и для любого <tex>n</tex> наибольшее значение функция <tex>\left\{ \dfrac{(p - 3)(p - 4)}{12} \right\}</tex> достигается при <tex>p=\left[\dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>. Поскольку <tex>\chi\left(K_p\right) = p</tex>, откуда получаем, что <tex>\chi \left( S_n \right) \geqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>.
 
}}
 
 
 
==Теорема о верхней границе хроматического числа поверхности==
 
 
 
{{Теорема
 
|about=
 
Гипотеза Хивуда
 
|statement=
 
Для любого положительного целого числа <tex>n</tex> хроматическое число поверхности <tex>n</tex>-ого рода <tex>\chi \left( S_n \right) \leqslant \left[ \dfrac{ 7 + \sqrt{1 + 48n} }{ 2 } \right]</tex>.
 
|proof=
 
  
Пусть задан граф <tex>G</tex> с <tex>V</tex> вершина, <tex>E</tex> рёбрами и <tex>F</tex> гранями, также будем считать, что <tex>G</tex> {{---}} триангуляция (добавляя таким образом рёбра мы всё ещё получаем граф, который можно уложить на поверхности <tex>n</tex>-ого рода). Обозначим за <tex>d</tex> {{---}} среднюю степень вершины графа <tex>G</tex>, тогда должно быть справедливым следующее равенство:
+
Пусть задан граф <tex>G</tex> с <tex>V</tex> вершина, <tex>E</tex> рёбрами и <tex>F</tex> гранями, также будем считать, что <tex>G</tex> <tex>-</tex> триангуляция (добавляя таким образом рёбра мы всё ещё получаем граф, который можно уложить на поверхности <tex>n</tex>-ого рода). Обозначим за <tex>d</tex> <tex>-</tex> среднюю степень вершины графа <tex>G</tex>, тогда должно быть справедливым следующее равенство:
  
<tex>dV = 2E = 3F</tex>  
+
<tex>dV = 2E = 3F</tex>.
  
Воспользуемся [[формула Эйлера | формулой Эйлера]] <tex>V - E + F = 2 - 2 n</tex>, откуда
+
Воспользуемся следующей формулой Эйлера
  
<tex>E = V + F + 2 (n - 1)</tex> и <tex>F = 2 V + 4 (n - 1)</tex>
+
<tex>V - E + F = 2 - 2 n</tex>
  
и подставляя в первое равенство получаем
+
Откуда <tex>E = V + F + 2 (n - 1)</tex> и <tex>F = 2 V + 4 (n - 1)</tex> и подставляя в первое равенство получаем
  
 
<tex>dV = 6V + 12(n - 1)</tex>  
 
<tex>dV = 6V + 12(n - 1)</tex>  
Строка 50: Строка 28:
 
<tex>d = 6 + \dfrac{12(n - 1)}{V}</tex>
 
<tex>d = 6 + \dfrac{12(n - 1)}{V}</tex>
  
Поскольку <tex>d \leqslant V - 1</tex>, то
+
Поскольку <tex>d \leqslant V - 1</tex>, то получаем, что
  
<tex>V - 1\geqslant 6 + \dfrac{12(n - 1)}{V}</tex>
+
<tex>V - 1\geqslant 6 + \dfrac{12(n - 1)}{V}</tex>.
  
Найдём единственный положительный корень неравенства
+
Найдя единственный положительный корень неравенства получаем
  
 
<tex>V \geqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>
 
<tex>V \geqslant \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>
  
Обозначим за <tex>H(n) = \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>. Если <tex> V \leqslant H(n)</tex>, то тогда граф <tex>G</tex> очевидно можно раскрасить в <tex>H(n)</tex> цветов и неравенство верное. Допустим, что <tex>V > H(n)</tex>, тогда
+
Обозначим за <tex>H(n) = \left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>. Если <tex> V \leqslant H(n)</tex>, то тогда граф <tex>G</tex> очевидно можно раскрасить в <tex>H(n)</tex> цветов и неравенство верное. Допустим, что <tex>V > H(n)</tex>, тогда  
  
 
<tex> d < 6 + \dfrac{12(n - 1)}{H(n)} = H(n) - 1</tex>
 
<tex> d < 6 + \dfrac{12(n - 1)}{H(n)} = H(n) - 1</tex>
  
Значит в такое графе существует хотя бы одна вершина степени не больше <tex>H(n) - 2</tex>, стянем её с любой соседней и получим новый граф <tex>G'</tex> с <tex>V - 1</tex> вершинами. Если <tex>V - 1 = H(n)</tex>, то граф <tex>G'</tex> можно раскрасить в <tex>H(n)</tex> цветов, значит и сам граф <tex>G</tex> можно также раскрасить в <tex>H(n)</tex> цветов, если <tex>V - 1 > H(n)</tex>, то опять найдём вершину степени <tex>H(n) - 2</tex> и снова стянем её и будем продолжать так до тех пор, пока не получим желаемый граф.
+
Значит в такое графе существует хотя бы одна вершина степени не больше <tex>H(n) - 2</tex>, стянем её с любой соседней и получим новый граф <tex>G'</tex> с <tex>V - 1</tex> вершинами. Если <tex>V - 1 = H(n)</tex>, то граф <tex>G'</tex> можно раскрасить в <tex>H(n)</tex> цветов, значит и сам граф <tex>G</tex> можно также раскрасить в <tex>H(n)</tex> цветов, иначе снова повторим наш алгоритм.
}}
+
 
 +
Осталось доказать нижнюю границу для <tex>\chi \left(S_n\right)</tex>, для этого воспользуемся неравенством
  
Из всего выше сказанного получаем, что <tex>\chi \left(S_n\right)</tex> в точности равно <tex>\left[ \dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>.
+
<tex>n \geqslant \gamma\left(K_p\right) = \left\{\frac{(p - 3)(p - 4)}{12}\right\}</tex>, функция монотонно возрастает при <tex>p \geqslant 4</tex>, и для любого <tex>n</tex> наибольшее значение функция <tex>\left\{\frac{(p - 3)(p - 4)}{12}\right\}</tex> достигается при <tex>p=\left[\dfrac{7 + \sqrt{1 + 48n}}{2} \right]</tex>. Поскольку <tex>\chi\left(K_p\right) = p</tex>, откуда получаем, что <tex>H(n)</tex> неулучшаемая нижняя граница для числа <tex>\chi\left(S_n\right)</tex>.
  
==Проблема четырёх красок==
+
}}
Заметим, что теорема Хивуда не работает при <tex>n = 0</tex>, поэтому [[проблема четырёх красок]] не может быть доказана с помощью этой теоремы, однако при подстановке <tex>n = 0</tex> получаем <tex>\chi \left( S_0 \right) = 4</tex>.
 
  
 
==См. также==
 
==См. также==
Строка 78: Строка 56:
 
* [https://en.wikipedia.org/wiki/Heawood_conjecture Wikipedia {{---}} Heawood conjecture]
 
* [https://en.wikipedia.org/wiki/Heawood_conjecture Wikipedia {{---}} Heawood conjecture]
 
* [https://oeis.org/A000934 Последовательность чисел Хивуда]
 
* [https://oeis.org/A000934 Последовательность чисел Хивуда]
* Ф.Харари «Теория графов» {{---}} М.: Мир, 1973 г. {{---}} стр. 162 - 164
+
* Харари - Теория графов (стр. 162 - 164)

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: