Изменения

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

Хроматическое число планарного графа

5004 байта добавлено, 19:32, 29 декабря 2016
→‎Раскраска в 4 цвета
{{Лемма
|id=5deg_vertex_lemma
|statement=В любом планарном графе <tex> G </tex> существует вершина [[Основные определения теории графов#def_undirected_graph_2 | степени]] не больше <tex>5</tex>.
|proof=
Предположим это не так. Для любой вершины <tex> u_i </tex> графа <tex> G </tex> верно <tex> \mathrm{deg} \; u_i \geqslant 6 </tex>. Если сложить это неравенство для всех <tex> i </tex>, получим <tex> 2E \geqslant 6V </tex>. Но по [[Формула_Эйлера#EulerFormulaCons|следствию из теоремы Эйлера]] <tex> E \leqslant 3V-6 </tex>. Пришли к противоречию.
== Раскраска в 4 цвета ==
Данная теорема {{Теорема|about=Проблема четырех красок|statement='''Теорема о четырёх красках''' — утверждение о том, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке общей границей для них не считаются.}}[[Файл:Map of Russia(four colour).png|230px|thumb|right|карта России раскрашенная в <tex>4</tex> цвета]]Теорема о четырёх красках была доказана в <tex>1976</tex> году Кеннетом Аппелем и Вольфгангом Хакеномиз Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация того, что существует определенный набор из <tex>1936</tex> карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Аппель и Хакен использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из <tex>1936</tex> карт. Доказательство этого факта заняло сотни страниц. Их После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контрпримера к теореме, потому что иначе он должен бы содержать, хотя не содержит, какую-нибудь из этих <tex>1936</tex> карт. Это противоречие говорит о том, что вообще не существует контрпримера. Изначально доказательство сводилось к рассмотрению порядка 2000 графовне было принято всеми математиками, поскольку его невозможно было проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения. Чтобы развеять оставшиеся сомнения, в <tex>1997</tex> году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, 4но по-раскрашиваемость которых была проверена при помощи прежнему проделанное с помощью компьютера. Подробнее [httpКроме того, в <tex>2005</tex> году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения (Coq v7.3.1) == Эквивалентные формулировки ==В теории графов утверждение теоремы четырёх красок имеет следующие формулировки:* Хроматическое число планарного графа не превосходит <tex>4<//entex>.* Рёбра произвольной триангуляции сферы можно раскрасить в три краски так, что все стороны каждого треугольника были раскрашены в разные цвета. == Ложное доказательство ==Ошибочным мнением считается, что решением проблемы четырех красок является - доказательство того, что невозможно начертить карту, на которой было бы всего лишь пять стран и каждая из этих стран примыкала бы к четырем остальным странам.wikipediaНетрудно доказать, что такую карту начертить нельзя.org/wiki/Four_color_theorem смМожно предположить, что отсюда автоматически следует решение проблемы четырех красок для всех карт, но такое заключение неверно.{| cellpadding="0"| [[Файл:False disproof left. здесьpng|230px]]|| [[Файл:False disproof right.png|230px]]|-  |}Карта(слева) окрашена пятью цветами, и нужно изменить как минимум <tex>4</tex> из <tex>10</tex> регионов, чтобы получить окраску в четыре цвета(справа)
== Источники информации ==
Topaevtimur
40
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/50583...58419»

Навигация