?

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: vsounder
2010-08-20 05:55 pm (UTC)

Мат Энциклопедия

ЧЕТЫРЕХ КРАСОК ЗАДАЧА: можно ли области любой плоской карты (см. Граф плоский) раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета?
Гипотеза о том, что ответ на Ч. к. з. утвердительный, была сформулирована в сер. 19 в. В 1890 было доказано более слабое утверждение, а именно, что любая плоская карта раскрашивается в пять цветов. Сопоставляя любой плоской карте двойственный ей плоский граф, получают эквивалентную формулировку Ч. к. з. в терминах графов: верно ли, что хроматич. число (см. Графа, раскраска) любого плоского графа G не превосходит Многочисленные попытки решения Ч. к. з. оказали влияние на развитие ряда направлений графов теории. В 1976 анонсировано положительное решение Ч. к. з. с использованием ЭВМ (см. [3]).

Лит.: [1] Xарари Ф., Теория графов, пер. с англ., М., 1973; [2] Ore О., The four-color problem, N. у.- L., 1967; [3] Арреl К., Нakеn W., «III. J. Math.», 1977, v. 21, № 3, p. 429-567.
В. Б. Алексеев.

Членство РАЕН не ничего не значит. Хотя настораживает. Обычно не фрики не рекламируют свое членство.
(Reply) (Thread)
[User Picture]From: vsounder
2010-08-20 05:55 pm (UTC)

Re: Мат Энциклопедия

я кстати не знал.
(Reply) (Parent) (Thread)
[User Picture]From: mario_gutierrez
2010-08-20 08:51 pm (UTC)

Re: Мат Энциклопедия

а это с электронного варианта или в бумажного?

если с электронного - то попрошу ссылочку, мне очень пригодится, и не только в связи с постом.
(Reply) (Parent) (Thread)
[User Picture]From: vsounder
2010-08-21 08:09 am (UTC)

Re: Мат Энциклопедия

электронный... бумажный у меня высоко, надо на стул встать, а потом еще листать...
(Reply) (Parent) (Thread)