Теорема о 4-х красках

Irenas

 Математические этюды выпустили еще одно приложение для iГаджетов: "4 краски". Русская и бесплатная версия здесь, с бОльшим количеством карт и двуязычная тут.
Игрушка посвящена теореме о 4-х красках, доказанной в 1976 году математиками Кеннетом Аппелем (Kenneth Appel — он, к слову, на днях помер) и Вольфгангом Хакеном (Wolfgang Haken):
— Любую карту на плоскости можно раскрасить в четыре цвета так, что никакие области, имеющие общую границу (отличную от точки не были раскрашены в один цвет.
Мы предлагаем забавы ради раскрасить некоторые карты. На реальных географических картах сделаны краткие подсказки по регионам.

ruslan80

доказанной в 1976 году математиками Кеннетом Аппелем (Kenneth Appel — он, к слову, на днях помер) и Вольфгангом Хакеном (Wolfgang Haken)
А "доказанной" уже без кавычек? К ним же куча вопросов была.

wawa321

как её доказательство примерно выглядит, или хотя бы какими методами она решается?

BSCurt

Я погулглю за тебя.
"Now the four-color conjecture has been proved by two University of Illinois mathematicians, Kenneth Appel and Wolfgang Haken. They had an invaluable tool that earlier mathematicians lacked—modern computers. Their present proof rests in part on 1,200 hours of computer calculation during which about ten billion logical decisions had to be made. The proof of the four-color conjecture is unlikely to be of applied significance. Nevertheless, what has been accomplished is a major intellectual feat. It gives us an important new insight into the nature of two-dimensional space and of the ways in which such space can be broken into discrete portions."
Кеннет Аппель[en] и Вольфганг Хакен[en] из Иллинойского университета доказали в 1976 году, что так можно раскрасить любую карту. Это была первая[источник не указан 125 дней] крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница); впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок[1]. Проблема четырёх красок является одним из известнейших прецедентов неклассического доказательства в современной математике.

blackout

Ничего, скоро люди станут компьютерами и эта теорема будет доказываться "простым перебором".

Irenas

Мы не проверяли доказательства.
Говорят, что Mathematical Intelligencer попросил их выпустить статью, отвечающую на замечания. Они написали книгу, про критику по существу к которой мне не известно.

ruslan80

Я знаю только стандартные факты: все карты были разбиты на овер 9000 типов (на самом деле около 2000, насколько я помню для каких-то из них было получено математическое доказательство, для оставшихся был устроен перебор на компах.

wawa321

т.е. все возможные бесконечные мозаики свелись к конечному набору разных типов, часть из них доказали, а часть прогнали на компе? интересно, как свели к конечному числу?

ruslan80

Это уже вопросы не ко мне, проблема четырёх красок как-то обошла меня стороной, несмотря на то, что приходилось доказывать теорему о пяти красках, как и всем олимпиадникам.

wawa321

как доказываются пять?

wawa321

Вот эта часть не особо понятна, что такое К5 и почему среди v1, v2,…,v5 существуют две несмежные вершины:
===
2) Deg(v) = 5. Если смежные с v вершины v1, v2,…,v5 имеют в совокупности r ≤ 4 красок, то вершину v можно раскрасить в оставшийся цвет. Пусть теперь вершины v1, v2,…,v5 окрашены в 5 цветов C1, C2,…,C5 соответственно. Натянем на вершины v1, v2,…,v5 из G подграф H, соединив v1, v2,…,v5 в H ребрами так, как они соединены в G. Подграф H – планарный ⇒ H не содержит K5, значит в H среди вершин v1, v2,…,v5 существуют две несмежные вершины, ибо если все вершины v1, v2,…,v5 смежны, то граф H содержит K5, чего нет. Пусть для определенности вершины v1,v2 не смежны. Склеим v1, v2 с вершиной v. Полученный связный граф по предположению индукции 5-раскрашиваем. При этом 4 вершины v, v3, v5 получат: r ≤ 4 краски.
Расклеим назад v1, v2, v. Вершины v1, v2 оставим их прежний цвет (как у v). Тогда вершины v1, v2,…,v5 [v1, v2 – одинаково раскрашены] имеют r ≤ 4 цвета. Вершину v перекрасим в один из оставшихся цветов. Шаг индукции установлен. Теорема доказана.
===
И вот это утверждение тоже: "Т.к. граф G связен и планарен, то он имеет вершину v степени S ≤ 5. "

ruslan80

Вот эта часть не особо понятна, что такое К5 и почему среди v1, v2,…,v5 существуют две несмежные вершины:
К5 - полный граф с пятью вершинами, он не планарен.
И вот это утверждение тоже: "Т.к. граф G связен и планарен, то он имеет вершину v степени S ≤ 5. "
В вики вкратце рассказано о планарных графах, в том числе и о К5 и этой лемме:
http://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%B0%D0%BD%D0%B0%...

h_alishov

Скачал двуязычную версию. В целом, прикольно и раскрашивать удобно. Пара замечаний:
1. Сейчас игра не дружелюбна к детям-дошколятам. Если вместо всплывающего сообщения с сухим поздравлением сделать какой-нибудь спецэффект, дети с гораздо большим рвением будут раскрашивать карты. Такие вещи важны, правда.
2. Игра называется four colours (british english) и стоит на шестом месте по запросу four colors (american english). Есть хороший шанс, что вас не все люди смогут найти.

Irenas

Спасибо за замечание. Гарднера получилось раскрасить? :)
"Four colors" кто-то заранее себе зарегистрировал. Приложения такого еще нет (на момент нашей регистрации а название зарезервировано.

stm7543347

FOR KALLAZ
Оставить комментарий
Имя или ник:
Комментарий: