Теорема о четырёх красках: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
MBH (обсуждение | вклад) |
м →Преамбула: пунктуация, оформление |
||
Строка 7:
|оригинал = Graph Theory
|место = М.
|издательство = [[Мир (издательство)|
|год = 1973
|страницы = 17—18
}}
</ref> (то есть область не может состоять из двух и более отдельных
В [[1852 год]]у {{не переведено 5|Гутри, Фрэнсис|Фрэнсис Гутри||Francis Guthrie}}, составляя карту графств Англии, обратил внимание, что для такой цели хватает четырёх красок
Для простых карт достаточно и трёх цветов, а четвёртый цвет начинает требоваться, например, когда имеется одна область, окружённая нечётным числом других, которые соприкасаются друг с другом, образуя цикл. [[Теорема о пяти красках]], утверждающая, что достаточно пяти цветов, имела короткое несложное доказательство и была доказана в конце XIX века, но доказательство теоремы для случая четырёх цветов столкнулось со значительными трудностями.
Строка 19:
Теорема о четырёх красках была доказана в [[1976 год в науке|1976 году]] {{не переведено|Аппель, Кеннет|Кеннетом Аппелем|en|Kenneth Appel}} и {{не переведено|Хакен, Вольфганг|Вольфгангом Хакеном|en|Wolfgang Haken}} из [[Иллинойский университет в Урбана-Шампейн|Иллинойского университета]]. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация существования определённого набора из 1936 карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Авторы использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из 1936 карт. Доказательство этого факта заняло сотни страниц. После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контрпримера к теореме, потому что иначе он должен был бы содержать какую-нибудь из этих 1936 карт, чего нет. Это противоречие говорит о том, что контрпримера нет вообще.
Изначально доказательство было принято не всеми математиками, поскольку его невозможно проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения. Чтобы развеять оставшиеся сомнения, в 1997 году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в 2005 году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения ([[Coq]] v7.3.1)<ref>{{Cite web |url=http://www2.tcs.ifi.lmu.de/~abel/lehre/WS07-08/CAFR/4colproof.pdf |title=A computer-checked proof of the Four Colour Theorem |lang=en |author=Georges Gonthier |website= |date=2005 |publisher=Microsoft Research Cambridge |archive-url=https://web.archive.org/web/20220605124139/http://www2.tcs.ifi.lmu.de/~abel/lehre/WS07-08/CAFR/4colproof.pdf |archive-date=2022-06-05 |dead-url=no}}</ref>.
== Эквивалентные формулировки ==
| |||