GeoFAQ siteФОРУМ ПО ГЕО-ИНФОРМАЦИОННЫМ ТЕХНОЛОГИЯМ

GIS, CAD, DTM, SQL, WWW, GPS, ETC.
 - Начало - Регистрация - Ответить - Поиск - Статистика - RSS
Форум GeoFAQ / География и другие гео-науки / Проблема четырех красок
Автор Сообщение
geologic
Участник
# Дата: 15 Дек 2008 15:06 - Поправил: geologic
Ответить 


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

Выяснилось также, что это одна из нерешенных теорем (следующая по притягательности за Ферма), которым в последнее время предложен совершенно иной путь решения - компьютерный. Конкретного описания нет, но судя по всему, это простой перебор, но до умопомрачительных чисел. В самом деле, кого взволнует ошибка в раскраске, если таковая и возникнет, за пределами возможных количеств не только стран, но и районов-городов-а то и песчинок на планете земля? Вполне можно считать доказанным и строить алгоритмы.

И вот что я подумал - аналогичным образом, нельзя ли такое доказать с помощью ГИС? ну хотя бы с пятью красками разобраться? Никто не думал на эту тему...

OleGIS
Участник
# Дата: 15 Дек 2008 20:06
Ответить 


А что это значит "доказать с помощью ГИС"? Неужели скрипт в АркМапе написать?

lalex
Участник
# Дата: 15 Дек 2008 22:19
Ответить 


повторить опыт тех ребят можно. Они ведь просто написали специальную программу. Какой был важный элемент программы? Функция проверки соседей, не прокрасились ли они одной краской. Что это, как не ГИС? Остается досочинить остальное - ну, саму легенду, и перебор вариантов по ней. Времени может уходить уйма, но это вопрос второй - можно процессик некий и на недельку поставить, если будет интересно, и больше :)

Кстати, а кто-нибудь слышал в ГИС про такую функцию? Раскраска по легенде политической карты, но чтобы соседи не совпадали... Это ведь важно, черт побери. Если где-то это есть, то тогда вот и решение - уменьшать число красок, пока не застопорит. Дальше увеличивать число стран, пока не затормозит :D

Василий
Участник
# Дата: 16 Дек 2008 10:26
Ответить 


Есть скрипт на эту тему http://arcscripts.esri.com/details.asp?dbid=10823

geologic
Участник
# Дата: 16 Дек 2008 11:07
Ответить 


Вот это да. Красит до 130000 полигонов, и "был чертовски оптимизирован для этого объема..."
ради такого стоит AV снова поставить ;)

Василий
Участник
# Дата: 16 Дек 2008 14:08
Ответить 


можно глубоко задуматься над модулем и попытаться dll подцепить в аrcgis, если без него уже жизни не видно

geologic
Участник
# Дата: 16 Дек 2008 14:44 - Поправил: geologic
Ответить 


Да к слову, задача имеет важный практический смысл - как без такого инструмента раскрасить политико-административную карту? Россия и Китай, Якутия и Таймыр могут оказаться одного розового цвета, что и бывает если применить обычную Unique Color легенду.

Однако мне больше хотелось подбодрить коллективное серое вещество к новому году - картозадачи такие не стоят политические... ;)

dwarwood2
Участник
# Дата: 16 Дек 2008 16:22 - Поправил: dwarwood2
Ответить 


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


гы-гы. для меня это выяснилось на первых курсах ввуза, токо слова "ГИС" я тогда не знал :-)

geologic
Участник
# Дата: 16 Дек 2008 16:54
Ответить 


Вам, технарям, море по колено в алгоритмах, понятное дело. А от меня коллега-физик тут же потребовал раскрасить его замысловатый рисунок - не поверил в формулировку. Полчаса я голову ломал с карандашами, а был бы скрипт... :)

chechulinvl
Участник
# Дата: 7 Фев 2009 08:39
Ответить 


товв.
4-рескарашиваемость плоских графов была неоднократно доказана в СССР классическим способом, первый доказал это Горбатов. ещё в 1964 г.. кратчайший вариант доказательства занимает 0,5 стр.

chechulinvl
Участник
# Дата: 7 Фев 2009 08:44
Ответить 


см статью в вкикипедии (проблема четырёх красок)

geologic
Участник
# Дата: 8 Фев 2009 22:29 - Поправил: geologic
Ответить 


Приветствую. Со ссылки на статью в википедии эта тема и началась... Насчет работ Горбатова там вот что "В своей книге[4] Горбатов утверждает, что предложил классическое доказательство ещё в 1964, позже был предложен более короткий вариант доказательства [5], однако эти доказательства так и не получили всеобщего признания."

Если вы это как-то можете прокомментировать... Почему не получили? Это вы - автор "Об одном варианте доказательства 4-раскрашиваемости плоских графов" 2006 в Пермском вестнике? Интересно было бы прочесть и то, и это.

chechulinvl
Участник
# Дата: 8 Мар 2009 07:45
Ответить 


В ответ на "Почему не получили? " -- сообщается что это необоснованное мнение редакторов статьи. см. в википедии обсуждение и историю статьи, книга горбатова доступна по ссылке в википедии в электронном виде, но у него доказательство длинное (30 стр. примерно)
Наша работа прореферирована в Реферативном Журнале Математика ВИНИТИ РАН, реферат 2007 г., №8, 07.08-13В.231, Референт: Воблый И.
Если намерены почитать нашу работу укажите адрес электронной почты -- вышлем сканкопию.

geologic
Участник
# Дата: 10 Мар 2009 18:53 - Поправил: geologic
Ответить 


Да, интересно. Работа Горбатова не находится в интернете, и я не уверен, что одолею 30 страниц. Поэтому вашу статью с удовольствием прочту - адрес geologic@mail.ru

chechulinvl
Участник
# Дата: 23 Окт 2009 16:39
Ответить 


Посмотрели стаью?

geologic
Участник
# Дата: 26 Окт 2009 11:31
Ответить 


Да, конечно прочитал, и не один раз. Но сообразить смог только, что чтобы соответствовать теме, надо влезать во всю теорию графов как следует. И как минимум проштудировать сопутствующую вашей статье литературу - статью Горбатова, лекции и "Неоконченную историю...".

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

samsung5550
Участник
# Дата: 26 Фев 2013 22:53
Ответить 


Уважаемый chechulinvl Добрый вечер! Я сейчас готовлюсь к НОУ по теме "Проблема четырех красок". Вы в 2009 году прислали работу этому человеку: geologic:

"Реферативном Журнале Математика ВИНИТИ РАН, реферат 2007 г., №8, 07.08-13В.231, Референт: Воблый И."

Вы не могли бы прислать и мне её пожалуйста....

Ваш ответ
Bold Style  Italic Style  Underlined Style  Image Link  URL Link 

» Логин  » Пароль 
Только зарегистрированные пользователи могут здесь постить. Авторизуйтесь для отправки сообщений, или зарегистрируйтесь сейчас.
 

Поддержка: bulletin board script miniBB™ © 2001-2017