Новое доказательство теоремы о четырёх красках использует 8202 конфигурации с параллельной редукцией
После почти десяти лет работы исследователи представили новое доказательство теоремы о четырёх красках и более быстрый метод раскраски графов, полезный для изучения планарных графов.
Исследователи разработали новое доказательство теоремы о четырёх красках, сообщает chip.pl. Работа началась в 2015 году и заняла почти десять лет. Доказательство опирается на 8202 конфигурации, а авторы также создали заметно более эффективный метод раскраски графов chip.pl
chip.plchip.plОткрыть источник ↗.
Теорема о четырёх красках и прежние доказательства
Теорема гласит: любую карту, разделённую на непересекающиеся области, можно раскрасить не более чем четырьмя цветами так, чтобы никакие две области с общей границей не были окрашены одинаково. Вопрос возник в 1852 году. Британский математик Фрэнсис Гатри, раскрашивая карту графств Англии, заметил, что для различения всех соседних областей хватает четырёх цветов, и задался вопросом, верно ли это для любой возможной карты.
Первую попытку доказательства представил в 1879 году Альфред Брей Кемпе. Одиннадцать лет его решение считали верным, пока Перси Джон Хивуд не нашёл в нём ошибку. Тем не менее часть идей Кемпе легла в основу последующих исследований.
В 1976 году Кеннет Аппель и Вольфганг Хакен представили доказательство, в котором впервые использовался компьютер для проверки огромного числа математических конфигураций. Они свели задачу к 1482 случаям, которые проверили компьютеры Университета Иллинойса. Результат вызвал споры: часть математиков сомневалась, можно ли считать доказательство с помощью компьютера полноценным. В 1997 году появилась усовершенствованная версия, где потребовалось проверить 633 конфигурации chip.pl
chip.plchip.plОткрыть источник ↗.
Параллельная редукция и планарные графы
Новое доказательство вновь подтверждает теорему. В нём используются 8202 конфигурации, которые можно редуцировать параллельно, а не анализировать по одной. Благодаря этому процедура заметно быстрее прежних решений.
Разработанные инструменты могут быть важны и за пределами раскраски карт. Они помогают лучше понять структуру планарных графов — математических моделей из точек, соединённых линиями, которые не пересекаются нигде, кроме общих вершин. Такие графы применяются в информатике, анализе сетей и моделировании различных явлений.
