2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 проблема четырёх красок (строгая формулировка условия)
Сообщение07.02.2009, 18:09 
Помогите разобраться в условии проблемы о четырёх красках. Конкретнее дать определение карты и стран.

 
 
 
 
Сообщение07.02.2009, 18:17 
Аватара пользователя
Корректно она называется "Проблема четырех красок".
Посмотрите хоть в википедии. Чтобы не морочиться с фрактальными границами при поиске контрпримера, лучше использовать эквивалентные формулировки задачи.

 
 
 
 
Сообщение07.02.2009, 18:19 
Аватара пользователя
Каждую страну изображаем вершиной графа. Две вершины соединяем ребром тогда и только тогда, когда страны имеют общую границу. Получаем граф, с которым далее и работаем, не заморочиваясь топологическими проблемами устройства границ (а там действительно ситуация весьма неясная). Правда, если ограничиваться связными странами, границы которых состоят из конечного числа прямолинейных отрезков, то особых проблем не будет.

 
 
 
 
Сообщение07.02.2009, 18:27 
Аватара пользователя
Только надо учитывать, вершины этого графа должны лежать на некоторой поверхности. Для тора и сферы разные решения.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group