?

Log in

No account? Create an account
Научная кунсткамера [entries|archive|friends|userinfo]
Научная кунсткамера

[ website | lj ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Проблема 4 красок [Aug. 20th, 2010|05:35 pm]
Научная кунсткамера

science_freaks

[mario_gutierrez]
мой первый пост здесь, если нарушаю какие-то правила, скажите...

Как известно, проблема 4 красок - одна из многих задач, решенных при помощи компьютера.
Собственно ее общепризнанное доказательство базируется на компьютерных рассчетах и имеет очень большую длину.
Даже само описание алгоритма занимает много страниц. Не знаю, проверял ли кто-либо из математиков это доказательство целиком.
Похоже, что приняли на веру :)

Но это все предисловие. Сказка только начинается.
Когда я сдавал кандидатский минимум в РГТЭУ по специальности 08.00.13, там в одном из билетов было написано: "Решение проблемы 4 красок"
И это была только небольшая часть билета. Я сильно удивился, если честно.
Полез в список литературы, а там есть замечательная книжка по этому билету:
Горбатов В. А. Фундаментальные основы дискретной математики. Информационная математика. — М.: Наука. …
(скачать можно, например, здесь)

В этой книге есть целый раздел, посвященный теории графов и мографов.
И в этом разделе приводится (внимание!) классическое доказательство теоремы о 4 красках, основанное на свойствах мографов
(насколько я понял, мограф - это специально введенное для этого доказательства понятие, по крайней мере нигде в других местах я его не встречал)
Причем утверждается, что автор получил его раньше (!!!) компьютерного доказательства.

Само доказательство достаточно короткое, но объем предшествующего материала, где вводятся определения и доказываются теоремы о мографах и их свойствах, не менее 60 страниц.
Честно говоря, я не сумел найти в этом доказательстве ошибку. Хотя я не специалист в теории графов и потратил на ее поиски всего пару дней.
Закрадывается сомнение в том, что доказательство не содержит изъянов.
Нигде в другой литературе я не нашел ссылок на это доказательство. Даже гугл молчит на этот счет. Единственное, что удалось найти - упоминание в обсуждении к статье "проблема 4 красок" в Википедии.

И главное, что меня настораживает - его членство в РАЕН, как написано в Википедии

Вобщем, вопрос такой - фрик ли этот Горбатов и правильное ли доказательство? Кто-нибудь знает?
LinkReply

Comments:
[User Picture]From: cn_mangetsu
2010-08-20 02:56 pm (UTC)
Однако с интересом почитал. Я и не знал, что есть хоть какое-то доказательство.
(Reply) (Parent) (Thread)
From: sstrukster
2010-08-20 03:03 pm (UTC)
Мнда, википедики такие википедики.
(Reply) (Parent) (Thread)
[User Picture]From: mario_gutierrez
2010-08-20 03:10 pm (UTC)
я это уже читал и сейчас перечитал еще раз :)

ответа на вопрос о корректности доказательства там нет :(

зато пока искал информацию о проблеме 4 красок, много раз читал что она сродни теореме Ферма по количеству неправильных "простых и красивых" доказательств
(Reply) (Parent) (Thread)
[User Picture]From: rwalk
2010-08-20 06:58 pm (UTC)
Учебник в целом достаточно ортодоксальный, хотя и не очень читаемый. Там, где начинаются собственные изыскания автора, почти не читаемый. В частности, формальное определение пресловутых мографов отсутствует. В общем, доводов contra много, а pro нет ни одного...
(Reply) (Parent) (Thread)
[User Picture]From: mario_gutierrez
2010-08-20 08:40 pm (UTC)
кстати, есть там определение мографов - в первой главе, где самое введение в теорию графов дается.

настораживает, что ни в одной другой книге по этой тематике я никаких "мографов" не видел
(Reply) (Parent) (Thread)
[User Picture]From: rwalk
2010-08-21 04:04 am (UTC)
Это я пропустил - поскольку самое раннее обнаруженное мной упоминание мографов в главе 3 никакой ссылки на это определение не содержало. Но общей картины это не меняет, поскольку, хотя из примеров и понятно, что автор имел в виду, к собственно опрделению есть целый ряд вопросов. Или чуть раньше Теорема 1.4 на стр. 37 - формулировка которой совершенно невнятна, а доказательство состоит из одной загадочной фразы. Что любопытно, хотя в формулировке и упоминается число 3, в доказательстве нет ни малейшего намека на его использование. А это уже характеристический признак. Посмотрите "10 признаков того, что провозглашаемое математическое открытие неверно" http://www.scottaaronson.com/blog/?p=304
(Reply) (Parent) (Thread)
[User Picture]From: mario_gutierrez
2010-08-21 04:10 pm (UTC)
посмотрел теорему 1.4
доказательство действительно мутное. особенно понравилась фраза "Тогда теорема очевидна. Действительно, достаточно рассмотреть следующий пример ... ". Новый способ доказательства теорем - приведением примера, подтверждающего истинность доказываемого утверждения :)

за ссылку спасибо, почитал.
(Reply) (Parent) (Thread)