?

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)
[User Picture]From: termar
2010-08-20 03:30 pm (UTC)
Применение компьютера необходимо было для того, чтобы покрыть все возможные варианты, которых слишком много по сравнению с обычными доказательствами.
Возможно, доказательство Горбатова верно для некоторых случаев. Однако в нём не хватает доказательства, что рассмотрены действительно все возможные случаи.
(Reply) (Thread)
[User Picture]From: mario_gutierrez
2010-08-20 03:49 pm (UTC)
судя по тому, что написано в его книге, Горбатов претендует на то, что его доказательство охватывает все случаи.

меня удивляет то, что книга рекомендована в качестве учебника мин.образования и при этом в ней такие непроверенные доказательства. ни одной ссылки на это доказательства в других книгах по теории графов не видел...
получается какой-то странный гениальный прорыв Горбатова, который никто не опроверг и по которому уже учат студентов...
(Reply) (Parent) (Thread)
[User Picture]From: de_maker
2010-08-20 05:11 pm (UTC)
>учат студентов
Чего уж там мелочиться - кандидатов.
(Reply) (Parent) (Thread)
[User Picture]From: mario_gutierrez
2010-08-20 08:42 pm (UTC)
аспирантов не учат, их просто сдавать по этой книге заставляют :)

кстати интересно как сдают этот билет другие аспиранты в РГТЭУ :)
(Reply) (Parent) (Thread)
From: sstrukster
2010-08-20 06:33 pm (UTC)
А учебники по теологии или физике торсионных взаимодействий не удивляют? ;-)
(Reply) (Parent) (Thread)
[User Picture]From: mario_gutierrez
2010-08-20 08:42 pm (UTC)
к счастью, не попадались :)
(Reply) (Parent) (Thread)
[User Picture]From: altavir
2010-08-20 06:41 pm (UTC)
По теме совсем не специалист, но идиотских книг с такой рекомендацией встречал много. Более того, было несколько скандалов по повожу того, что фразу о рекомендованности книги минобром писали вообще не получая никакую рекомендацию и не проходя никакой экспертизы.
(Reply) (Parent) (Thread)
[User Picture]From: mario_gutierrez
2010-08-20 08:57 pm (UTC)
да, никому нельзя верить..
печально.
(Reply) (Parent) (Thread)
[User Picture]From: buzzing_winnie
2010-08-20 04:48 pm (UTC)

исправьте ошибки

имеет очень большую длинну
я сдавал кандидатский мимниум
немного офигел

ничего личного

(Reply) (Thread)
[User Picture]From: mario_gutierrez
2010-08-20 08:44 pm (UTC)

Re: исправьте ошибки

исправил, спасибо за замечания.
набирал второпях и даже не проверил за собой
(Reply) (Parent) (Thread)
[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)
[User Picture]From: regent_2
2010-08-20 08:20 pm (UTC)

В.Б. не даст соврать.

Тому лет 15.
Некто Кожевников Д.Н. Защитил диссер по педагогике. Там было всякая педагогическая похабень э-э...педагогика + различные модели строения атомов. А среди них-то самая что ни на есть похабень - кольцегранная модель фрика и неуча Кушелева. Так вот, издательством, специализируем... специализируев...тьфу, не выговорить. В общем, издательство выпускало учебные плакаты допущенные мин.образования для школ. Оно и выпустило эти плакаты. Как такое могло прозойти? Элементарно. Научный руководитель этого диссертанта была член-корреспондент РАО, доктор педагогических наук, профессор Назарова Т.С. + куратор этого направления в этом издательстве.
То что ахинея вбивается в головы учащихся её не волновало. Да и врят ли она что-то в этом смыслила.
Отсюда эрго. Титулы и звания ничего не говорят о научной ценности материалов автора.
Цитируемость это да. Диссер Кожевникова помнит только аффтар и Куев, тьфу, Кушелев. Про Горбатова только упоминание В Вики. Ну, дык, и то хлеб.
(Reply) (Thread)
[User Picture]From: mario_gutierrez
2010-08-20 08:57 pm (UTC)

Re: В.Б. не даст соврать.

я так понимаю, в случае с кольцегранной моделью Кушелева все было ясно даже школьным учителям, здесь же случай сложный. для того, чтобы проверить доказательство Горбатова, надо как минимум разбираться в теории графов на приличном уровне.
(Reply) (Parent) (Thread)
[User Picture]From: regent_2
2010-08-20 11:03 pm (UTC)

Ну, ну.

http://www.bookshunt.ru/b31908_fundamentalnie_osnovi_diskretnoj_matematiki
Название: Фундаментальные основы дискретной математики
Автор: Горбатов В.А.
Издательство: Наука. Физматлит
Год издания: 2000
Рекомендовано Министерством общего и профессионального образования Российской Федерации в качестве учебника для студентов высших технических учебных заведений.
***
Я добрался только до Содержания. Судя по нему книга сурьёзная. Но ситуация аналогична описанной мной выше. Когда в большой куче серьёзного материала впихивается проблематичный под видом решённого. Кто-то кого-то протолкнул. То что за десять лет нет никакой критики означает одно - материал недостоин даже критики. ИМХО.
(Reply) (Parent) (Thread)
[User Picture]From: kirilloid
2010-08-21 06:10 am (UTC)
Ура, наконец-то математический фрик.
(Reply) (Thread)
[User Picture]From: mario_gutierrez
2010-08-21 01:46 pm (UTC)
я думаю, что их достаточно много.
правда большинство на теореме Ферма специализируются :)
(Reply) (Parent) (Thread)
[User Picture]From: ausweis_ss
2010-08-21 07:51 am (UTC)
С задачей не знаком, человеком тоже, но вице-президентсво Международной Академии Информатизации - это хуже чем членство РАЕН.
(Reply) (Thread)
[User Picture]From: mario_gutierrez
2010-08-21 03:56 pm (UTC)
да, погуглип про Международную академию информатизации и нагуглил вот это:
"“Слово - это Информация
и Информация - вездесущая.
Бог - это информация
и Информация - это
Бог вездесущий.
Информация - это Вселенная
и Вселенная - это информация
вакуумная, материзованная
и дематеризованная...”"

ужас...
(Reply) (Parent) (Thread)