Лайфхакер
Лайфхакер
Лучшее
Новости
Жизнь
Рецепты
Здоровье
Кино
Технологии
Покупки
Лучшее
Новости
Жизнь
Рецепты
Здоровье
Кино
Технологии
Покупки
Куда поехать на выходные
Сезон распродаж
✍️ Написать
Добрые новости
Есть мнение
Норм или стрём
Личный опыт
Объясняем за минуту
Новости
16:50

Математики нашли быстрый способ решить головоломку, над которой бились 174 года

Оказалось, любую карту можно за секунды раскрасить всего четырьмя цветами.
Фото автора Макс Вильтовский
Макс Вильтовский

Автор Лайфхакера

теорема о четырёх красках

Два профессора из Копенгагенского университета и Технического университета Дании (DTU) вместе с зарубежными коллегами разработали оптимальный алгоритм для быстрого решения задачи о четырёх красках. Математики пытались решить эту теорему 174 года.

✍️ Скоро читатели смогут публиковать свои тексты на Лайфхакере. Станьте первыми!

В 1852 году математик Фрэнсис Гутри заметил, что при составлении карты графств Англии ему хватило всего четырёх цветов, чтобы соседние области не совпадали по окраске, и предположил, что это правило работает для любой карты. Первое обоснование гипотезы представили в 1878‑м, но спустя 11 лет в нём нашли ошибку. Полное доказательство появилось только в 1976‑м, однако оно вызвало споры из-за опоры на сложные компьютерные расчёты, которые другим исследователям было трудно проверить. В 1997‑м учёные предложили более доступный вариант, но его алгоритм работал слишком медленно на крупных картах.

Команда, стоящая за открытием. Фото: Mikkel Thorup

В отличие от прежних подходов, которые лишь доказывали принципиальную возможность раскрасить любую карту четырьмя цветами, новый метод датских исследователей позволяет быстро подобрать оттенки для каждого отдельного региона даже на очень больших картах.

На решение этой задачи у них ушло около десяти лет. Это стало первым крупным прорывом в этой области за последние 30 лет, а начальную часть работы уже отметили наградой за лучшую статью на ведущей конференции по теоретической информатике FOCS 2026.

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

Представьте сводимые конфигурации как ручки, за которые можно ухватиться, чтобы начать раскрашивание в четыре цвета. Мы показали, что в графах есть не одна такая ручка, а множество. Раньше этого никто не знал.

Карстен Томассен

Один из авторов исследования

Теперь исследователи могут находить «маркеры» во многих местах на графе. Благодаря этому подбор цветов можно запускать сразу с разных точек и гораздо быстрее справляться даже с очень большими картами. «Это значит, что если на карте в десять раз больше регионов, вычисления замедляются примерно в десять раз. Со старым алгоритмом скорость падала бы примерно в сто раз», — пояснил Томассен.

Карта общин Словении, раскрашенная в четыре цвета. Изображение: Wikipedia

Миккель Торуп, ещё один из авторов решения, с юмором объяснил многолетнюю одержимость этой задачей, назвав её «болезнью четырёх цветов»: «Болезнь заключается в вере, что у такого простого утверждения должно быть простое доказательство. Я бы предположил, что ею заразились не меньше 1 000 математиков, которые тратили месяцы на попытки решить задачу, но так и не добивались полного успеха».

А на вопрос о том, зачем тратить годы на подобные исследования, профессор ответил: «Потому что математики немного сумасшедшие. Большая часть того, над чем мы работаем, состоит из очень заумных вопросов. Мы становимся одержимы такими проблемами, потому что они бросают вызов человеческому интеллекту».

Новое понимание структуры графов не ограничивается классической задачей о раскраске плоских карт. Оно также применимо, например, к поверхностям с отверстиями, таким как надувной круг для плавания или кусок сыра эмменталь. Поэтому авторы работы считают, что их открытие может иметь значение далеко за пределами теоремы о четырёх красках.

Больше интересного
💡
Крис Эванс заявил, что не будет Капитаном Америкой во «Мстителях: Доктор Дум»
В США создали носки, которые помогают меньше уставать при ходьбе
В Сети назвали 10 мини-сериалов, навсегда изменивших телевидение — в списке «Чернобыль» и «Сёгун»
Обложка: Gemini / Лайфхакер
Если нашли ошибку, выделите текст и нажмите Ctrl + Enter
Это интересно
Давайте посчитаем. Как эффективно вести семейный бюджет

Давайте посчитаем. Как эффективно вести семейный бюджет

Обзор TCL TAB A1 Plus NXTPAPER — нового планшета c «бумажным» экраном для работы и развлечений

Обзор TCL TAB A1 Plus NXTPAPER — нового планшета c «бумажным» экраном для работы и развлечений

Реклама
«Чародейка» — новый бьюти-бокс от «Горящей избы» и TRENDY BOX. Порадуйте вашу внутреннюю волшебницу!

«Чародейка» — новый бьюти-бокс от «Горящей избы» и TRENDY BOX. Порадуйте вашу внутреннюю волшебницу!

Как конкурс «Наука. Территория героев» помогает молодым людям делать первые открытия

Как конкурс «Наука. Территория героев» помогает молодым людям делать первые открытия

Комментарии
Авторизуйтесь, чтобы оставить комментарий

Станьте первым, кто оставит комментарий

Что вы могли пропустить
Крис Эванс заявил, что не будет Капитаном Америкой во «Мстителях: Доктор Дум»
Крис Эванс заявил, что не будет Капитаном Америкой во «Мстителях: Доктор Дум»
0
15:41
Кино
Новости
В США создали носки, которые помогают меньше уставать при ходьбе
В США создали носки, которые помогают меньше уставать при ходьбе
0
15:10
Новости
Новости
В Сети назвали 10 мини-сериалов, навсегда изменивших телевидение — в списке «Чернобыль» и «Сёгун»
В Сети назвали 10 мини-сериалов, навсегда изменивших телевидение — в списке «Чернобыль» и «Сёгун»
0
14:43
Кино
Новости
Учёные нашли на Марсе гигантские ледники, замаскированные под каменные обрывы
Учёные нашли на Марсе гигантские ледники, замаскированные под каменные обрывы
0
13:41
Новости
Новости
Rollme показала недорогой фитнес-браслет без экрана — он умеет снимать ЭКГ и работает до 15 дней
Rollme показала недорогой фитнес-браслет без экрана — он умеет снимать ЭКГ и работает до 15 дней
0
12:48
Новости
Устройства
Microsoft закроет таск-менеджер To Do — обычные пользователи останутся без альтернативы
Microsoft закроет таск-менеджер To Do — обычные пользователи останутся без альтернативы
0
12:10
Новости
Технологии
Мэрилин Монро, Том Хэнкс и Зендея: Variety назвал 100 величайших кинозвёзд всех времён
Мэрилин Монро, Том Хэнкс и Зендея: Variety назвал 100 величайших кинозвёзд всех времён
0
11:25
Кино
Новости
Звезда «Стражей Галактики» сыграет путешественника во времени в фильме авторов «Пункта назначения»
Звезда «Стражей Галактики» сыграет путешественника во времени в фильме авторов «Пункта назначения»
0
10:30
Кино
Новости
Apple выбрала 45 претендентов на звание лучших приложений и игр 2026 года
Apple выбрала 45 претендентов на звание лучших приложений и игр 2026 года
0
09:51
iOS
Новости
«Форсаж» подождёт: Вин Дизель сыграет смотрителя кладбища в новом боевике
«Форсаж» подождёт: Вин Дизель сыграет смотрителя кладбища в новом боевике
0
Вчера
Кино
Новости
Недорогие смартфоны Samsung могут подорожать почти на 19%
Недорогие смартфоны Samsung могут подорожать почти на 19%
0
Вчера
Новости
Технологии
Создатель The Sims готовит ИИ-игру с миром, который строится на воспоминаниях игроков
Создатель The Sims готовит ИИ-игру с миром, который строится на воспоминаниях игроков
0
Вчера
Игры
Новости
Боевик российского режиссёра вошёл в топ лучших фильмов с «дрожащей камерой»
Боевик российского режиссёра вошёл в топ лучших фильмов с «дрожащей камерой»
0
Вчера
Кино
Новости
«Вояджер-1» удалился от Земли на световой день — у него на борту послание внеземным цивилизациям
«Вояджер-1» удалился от Земли на световой день — у него на борту послание внеземным цивилизациям
0
Вчера
Новости
Новости

Новые комментарии

Аватар автора комментария
Alexandr Al3 часа назад

0 / 0

Был вполне приличный, еще со времен Wunderlist. Но сам давно пользуюсь Tick-Tick
Microsoft закроет таск-менеджер To Do — обычные пользователи останутся без альтернативы
Аватар автора комментария
Борис Кравченко3 часа назад

0 / 0

Sea Battle Duo ещё прикольная, без интернета и рекламы
В самолёт и поезд: 30 бесплатных мобильных игр, которым не нужен интернет
Аватар автора комментария
Victor_Kfis5 часов назад

0 / 0

Отличный подход у С. Гайза )) Я сам делаю, что-то похожее, но менее минималистично. Если кому-нибудь интересно ниже даю описание примерно на страничку. Общее представление. Может, будет полезно . Мой подход родился, кстати, таким путём: просто экспериментировал → прочитал книгу "Как привести дела в порядок" (GTD) → соединил старые эксперименты с идеями из книги (в целом, не зря читал и ещё вернусь к ней). В основе у меня такие списки: "сделать в срок", "делать (сделать) в настоящем и "делать (сделать) в будущем". По названиям, легко понять, что это за списки. Но вот кратко о них на ключевых примерах. "Разобрать вещи в шкафу до Нового года". А сейчас – только лето – нужно как-то иметь это в виду долгое время. В итоге: в шкафу беспорядок, не спеша можно разобрать; плюс в данном случае: легко запомнить срок и начать год с большим порядком в жизни – приятно. Или: "отправить материалы для участия в конкурсе до 5 мая". Позже значит не успеть... "Научиться запекать курицу в духовке ". Просто в свободном порядке в настоящем времени. Если есть желание что-то поделать, это ХОРОШИЙ ВАРИАНТ (выходит отчасти даже не как план, а "меню" дел). Или: "Перечитать места, которые мне были непонятны в книге" (или, может, в договоре). "Посетить Эрмитаж". Если не имеется в виду, что это "в свободном порядке" (как только настроюсь – поеду) или в следующем году, то это дело на "когда-нибудь ". Или даже "может быть". К этим основным спискам добавляю "различные размышления неыормального характера" и "другие вещи для управления делами". В "других вещах" у меня, в частности, расписание. В расписании просто ряд недель (использую Obsidian, плагин "Calendar") и заношу часть дел в день или неделю: конкретное время дня, часть дня, весь день, вся неделя, часть недели. Ещё в других вещах я называю свои системы напоминания, вроде, "рабочее место", "полка перед зеркалом " или "напоминания в Google Keep". Чтобы просто иметь их в виду; иметь системное представление. А "различные размышления ", в основном, служат для генерирования дел. Размышляю о том, кем хочу стать, где хочу быть, о больших целях, зонах внимания (они же сферы жизни и т.д.) и прочее. Разумеется, ещё есть гибкий Inbox, чтобы просто "захватить" мысль – хочу / нужно / надо сделать – не задумываясь хотя бы на полминуты. И ещё забыл про доску. У меня тоже есть доска на всякий случай. Например, там можно написать "экстренные" дела или составить списк "сделать и забыть" (пакет лёгких дел, чтобы закрыть много и сразу). А что касается списков – извините за сумбур в моём описании – то их использую активно и для дел в настоящем и для дел в будущем. На примерах. Есть список "делать (сделать) в настоящем". В нём два раздела "общий список" и "частные списки". И вот "частные списки " это почти по GTD. Объединяю дела по разных критериям (можно просто оставить в общем списке). Например, "прочитать / посмотреть / послушать за 5-30 минут". Так, у меня есть вариант для неожиданных (и ожидаемых) окон. Или "купить книги" – частный список в "делать (сделать) в будущем". Готов к возможной распродаже или просто к настрою побродить по маркетплейсам, авито и т.п. (там что-то появляется, исчезает, снова появляется...)
Простая система планирования для тех, кому надоели тайм-менеджмент, цели и списки дел
Аватар автора комментария
Олег Рудаков6 часов назад

0 / 0

Сберу, как крупному участнику банковского рынка, важно поддерживать совместимость своих сервисов с общими платёжными стандартами. Для клиента удобнее, когда разные решения работают согласованно
Что такое «СБПэй» и как им пользоваться
Давайте посчитаем. Как эффективно вести семейный бюджет

Давайте посчитаем. Как эффективно вести семейный бюджет

Лайфхакер
Информация
О проектеРубрикиРекламаРедакцияВакансииО компании
Подписка
TelegramВКонтактеTwitter (X)PinterestYouTubeИнициалRSS
Правила
Пользовательское соглашениеПолитика обработки персональных данныхПравила применения рекомендательных технологийПравила сообществаСогласие на обработку персональных данныхСогласие для рекламных рассылокСогласие для информационной программы
18+Копирование материалов запрещено.
Издание может получать комиссию от покупки товаров, представленных в публикациях